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 4 of 5: Compare exponents modulo c

Previous step Next step

\{ab+b+1,b,a+1\}\equiv\{ab+b,a+b+1,1\}\pmod c

Detailed analysis

Reducing F modulo x^c−1 turns each monomial into x raised to its exponent modulo c. The three positive and three negative terms must therefore give the congruent multisets {ab+b+1,b,a+1} and {ab+b,a+b+1,1} modulo c.