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 1 of 5: Assume equal residue sets

Previous step Next step

\{r_0,\ldots,r_a\}=\{0,\ldots,a\}\Longrightarrow\gcd(b,c)=1

Detailed analysis

Assume the two sets are equal. Then the residues r_0,…,r_a are all distinct, so gcd(b,c)=1; otherwise multiplication by b modulo c would repeat a residue before the range ends.