Problem 5

Let

a,b,c

be integers satisfying

0<a<c-1

and

1<b<c

. For each

k

0\le k\le a

, let

r_k

0\le r_k<c

, be the remainder of

kb

when divided by

c

. Prove that the two sets

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

and

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

are different.

Step 5 of 5: Reach the contradiction

Previous step Next step

b\not\equiv1,a+b+1\pmod c\Longrightarrow b\equiv ab+b\pmod c\Longrightarrow a\equiv0\pmod c

Detailed analysis

In the congruent multisets, b cannot match 1 because 1<b<c, and cannot match a+b+1 because 0<a+1<c. Thus b≡ab+b modulo c. Since gcd(b,c)=1, this implies a≡0 modulo c, contradicting 0<a<c−1. Hence the residue sets are different.