第5問

0<a<c-1

および

1<b<c

を満たす整数

a,b,c

を取る。各

k

(

0\le k\le a

) に対し、

kb

を

c

で割った余りを

r_k

(

0\le r_k<c

) とする。2つの集合

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

と

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

が異なることを証明せよ。

ステップ 5/5: 矛盾に到達する

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

詳しい解説

合同な多重集合で b は 1 とは一致できない（1<b<c）し、a+b+1 とも一致できない（0<a+1<c）。従って b≡ab+b (mod c)。gcd(b,c)=1 なので a≡0 (mod c) となるが、0<a<c−1 に反する。よって余り集合は異なる。