倍数を互いに素な自然数で割ったときの余りの性質

　互いに素な整数$A$と自然数$B$について
$A,2A,\cdots,(B-1)A,BA$をそれぞれ$B$で割ったときの余りを一列に並べたものは$0,1,\cdots,B-2,B-1$の並び替えである

という性質があります。

これが成り立つことを確かめてみます。

　上記の性質は$A,2A,\cdots,(B-1)A,BA$の$B$個の$A$の倍数をそれぞれ$B$で割ったときにどの余りも重複しないことを主張しています。

そこで、上記の性質があることを確かめるために$1$以上$B$以下の自然数$m,n$（ただし、$m>n$）をもちいて表される$A$の倍数$mA,nA$それぞれ$B$で割ったときの余りが等しいと仮定します。
$mA$を$B$で割ったときの商を$s$、余りを$r_1$とすると

$$mA=sB+r$$

と書け、変形すると

$$r_1=mA-sB$$

となります。

同様に$nA$を$B$で割ったときの商を$t$、余りを$r_2$とすると

$$r_2=nA-tB$$

と書けます。

仮定より$r_1=r_2$なので

$$mA-sB=nA-tB$$

であり、

$$\begin{align*}mA-nA&=sB-tB\\[0.5em](m-n)A&=(s-t)B\end{align*}$$

となります。
$A,B$は互いに素なので$m-n$が$B$の倍数であることがわかります。

しかし、$m,n$は$1$以上$B-1$以下の自然数かつ$m>n$なので$m-n$が$B$の倍数になることはありません。

$$\begin{align*}1\leqq m\leqq B,\ &1\leqq n\leqq B\\[0.5em]\Rightarrow &1-B\leqq m-n\leqq B-1\end{align*}$$

$m>n$より$m-n>0$なので

$$0<m-n\leqq B-1$$

$m-n$は$B-1$以下の自然数なので$B$の倍数でない。

したがって、仮定は誤り、すなわち$A,2A,\cdots,(B-1)A,BA$をそれぞれ$B$で割ったときに等しい余りが現れないことがわかります。

ところで、整数を$B$で割ったときの余りは$0,1,\cdots,B-2,B-1$の$B$個の中のいずれか1つです。

上記のことから、$A,2A,\cdots,(B-1)A,BA$の$B$個の$A$の倍数をそれぞれ$B$で割ったときの余りは$0,1,\cdots,B-2,B-1$の$B$個の中から重複せずに1つずつ現れる、すなわち

$A,2A,\cdots,(B-1)A,BA$をそれぞれ$B$で割ったときの余りを一列に並べたものは$0,1,\cdots,B-2,B-1$の並び替えである

という性質があることがわかります。

　互いに素な整数$A$と自然数$B$について

連続した$B$個の$A$の倍数をそれぞれ$B$で割ったときの余りを一列に並べたものは$0,1,\cdots,B-2,B-1$の並び替えである

という性質があることも同様の方法で確かめることもできます。

$k$以上$B+k-1$以下の整数$m,n$（$k:$任意の整数；$m>n$）をもちいて表される$A$の倍数$mA,nA$それぞれ$B$で割ったときの余りが等しいと仮定します。

$mA,nA$それぞれについて

$$\begin{align*}r_1&=mA-sB\\[0.5em]r_2&=nA-tB\end{align*}$$

と書けます。

仮定より$r_1=r_2$なので

$$\begin{align*}mA-nA&=sB-tB\\[0.5em](m-n)A&=(s-t)B\end{align*}$$

$A,B$は互いに素なので$m-n$が$B$の倍数であることがわかります。

しかし、$m,n$は$k$以上$B+k-1$以下の整数かつ$m>n$なので$m-n$が$B$の倍数になることはありません。

$$\begin{align*}k\leqq m\leqq B+k-1,\ &k\leqq n\leqq B+k-1\\ \Rightarrow &1-B\leqq m-n\leqq B-1\end{align*}$$

$m>n$より$m-n>0$なので

$$0<m-n\leqq B-1$$

$m-n$は$B-1$以下の自然数なので$B$の倍数でない。

したがって、仮定は誤り、すなわち

連続した$B$個の$A$の倍数をそれぞれ$B$で割ったときの余りを一列に並べたものは$0,1,\cdots,B-2,B-1$の並び替えである

という性質があることがわかります。

　では、$B$で割ったときの余りが等しくなる$A$の倍数の条件は何でしょうか？

任意の整数$m,n$（ただし、$m>n$）をもちいて表される$A$の倍数$ｍA,nA$それぞれについて

$$\begin{align*}r_1&=mA-sB\\[0.5em]r_2&=nA-tB\end{align*}$$

と書けます。

$r_1=r_2$のとき

$$\begin{align*}mA-nA&=sB-tB\\[0.5em](m-n)A&=(s-t)B\end{align*}$$

$A,B$は互いに素なので$m-n$は$B$の倍数であることがわかります。
したがって、$A$の倍数$mA,nA$の差が$B$の倍数となるとき、$B$で割ったときの余りが等しくなります。

これはすなわち、連続する$A$の倍数をそれぞれ$B$で割ったときの余りを一列に並べると同じ余りが$B-1$個おきに現れるということであり、$0,1,\cdots,B-2,B-1$を並び替えたものが繰り返し現れるということです。

例として連続した$22$の倍数（$22k$の項目）をそれぞれ$13$で割ったときの余り（$\text{mod}\ 13$の項目）を見てみると、13個の余りの並びは$0,1,2,3,4,5,6,7,8,9,10,11,12$を並び替えたもので、しかも繰り返し現れていることがわかります。

関連：互いに素とは？

関連：ある素数未満の自然数の倍数をある素数で割ったときの余りの性質

マスター オブ 整数-大学への数学

Amazonで見る楽天市場で見るYahoo!ショッピングで見る