MathDB

a problem with residues

Source: APMO 2008 problem 5

March 22, 2008

modular arithmeticinequalitiesgeometric seriesnumber theory proposednumber theoryresidue

Problem Statement

Let

a, b, c

be integers satisfying 0 < a < c \minus{} 1 and

1 < b < c

. For each

k

0\leq k \leq a

, Let

r_k,0 \leq r_k < c

be the remainder of

kb

when divided by

c

. Prove that the two sets

\{r_0, r_1, r_2, \cdots , r_a\}

and

\{0, 1, 2, \cdots , a\}

are different.