第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\}

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

ステップ 1/5: 余り集合が等しいと仮定する

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

詳しい解説

2つの集合が等しいと仮定する。このとき余り r_0,…,r_a はすべて異なるので gcd(b,c)=1 である。そうでなければ c を法とする b の乗法で範囲内に同じ余りが現れる。