MathDB

Subsets of {1,...,2004} with a & b such that 2004 | a^2-b^2

Source: XIII Rioplatense Mathematical Olympiad (2004), Level 3

July 26, 2011

modular arithmeticnumber theory unsolvednumber theory

Problem Statement

Find the smallest integer

n

such that each subset of

\{1,2,\ldots, 2004\}

with

n

elements has two distinct elements

a

and

b

for which

a^2-b^2

is a multiple of

2004