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 2 of 5: Encode the residues

Previous step Next step

f(x)=\sum_{j=0}^{a}x^{jb}-\sum_{j=0}^{a}x^j,\quad x^c-1\mid f(x)

Detailed analysis

Define $f(x)=1+x^b+\cdots+x^{ab}-(1+x+\cdots+x^a)$ . Equality of the residue sets means each exponent $jb$ can be replaced by its residue modulo $c$ , so $x^c-1$ divides $f(x)$ .