連続する整数の倍数を自然数で割ったときの余りの性質 ~ 数学について考えてみる

　互いに素な整数$A$と$2$以上の自然数$B$について、
連続する$B$個の$A$の倍数をそれぞれ$B$で割ったときの余りを一列に並べたものは$0, 1, 2, \cdots,$ $B-3, B-2, B-1$の並び替えである。

という性質があります。

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

　任意の整数を$k$として、連続する$B$個の$A$の倍数を

\[kA, (k+1)A, (k+2)A, \cdots, (B+k-3)A, (B+k-2)A, (B+k-1)A\]

ととることができます。（例えば、$k=1$ならば$A, 2A, 3A, \cdots,$ $(B-2)A, (B-1)A, BA$）

そして、$0, 1, 2, \cdots,$ $B-3, B-2, B-1$の並び替えということは、連続する$B$個の$A$の倍数をそれぞれ$B$で割ったとき、どの余りも重複しないことを意味します。

以上のことに着目し、$k$以上$B+k-1$以下の整数$m, n$（ただし、$m>n$）をもちいた$A$の倍数$mA, nA$をそれぞれ$B$で割ったときの余りが等しいと仮定し、背理法によって証明してみます。

　まず、$mA$を$B$で割ったときの商を$s$、余りを$r_1$とすると

\[mA=sB +r_1\]

と書け、$r_1$について解くと

\[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$の倍数、$s-t$は$A$の倍数であることがわかります。

　ここで、$m, n$は$k$以上$B+k-1$以下の整数なので、$m-n$のとりうる値の範囲は

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

で、さらに$m>n$より$m-n>0$なので

\[\Rightarrow 0<m-n\leqq B-1\]

となり、$m-n$は$B-1$以下の自然数であることがわかります。
$B$未満の自然数の中に$B$の倍数はないので、$m-n$は$B$の倍数でないことがわかります。

したがって、$m-n$が$B$の倍数か否かという点で矛盾が生まれるため、仮定は誤り、すなわち連続する$B$個の$A$の倍数をそれぞれ$B$で割ったとき、どの余りも重複しないことがわかります。

　ところで、どの整数を$B$で割ったとしても、余りは必ず$0, 1, 2, \cdots,$ $B-3, B-2, B-1$の$B$個の中のいずれか1つとなります。

よって、上記の背理法の結論と合わせて

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

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

余りの周期性

　連続する$B$個の$A$の倍数の中では、$B$で割ったときの余りが重複しないことがわかりましたが、$A$の倍数全体の中で$B$で割ったときの余りが等しくなる条件はあるのでしょうか？

　整数$m, n$（ただし、$m>n$）をもちいた$A$の倍数$mA, nA$をそれぞれ$B$で割ったときの余りが等しいものとします。

$mA$を$B$で割ったときの商を$s$、余りを$r_1$とすると

\[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$より$m-n>0$なので、$m-n$は$B$の正の倍数であることがわかります。

逆に、$m-n$が$B$の正の倍数ならば、$(m-n)A=mA -nA$も$B$の正の倍数となります。

したがって、$mA, nA$をそれぞれ$B$で割ったときの余りが等しいときとは、$m-n$が$B$の正の倍数のときであることがわかります。

　$m-n$は、連続する$A$の倍数の並びにおいて、$(n+1)A$から$mA$までの$A$の倍数の個数を表し、これを間隔と呼ぶことにします。そして、$B$の正の倍数で最小のものは$B$です。

すると、連続する$A$の倍数をそれぞれ$B$で割ったときの余りを一列に並べたとき、どの余りにおいても、同じ余りが現れる最小の間隔は$B$個となります。

したがって、$0, 1, 2, \cdots,$ $B-3, B-2, B-1$を並び替えたものが周期的に現れることがわかります。

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

(2026/8)内容を修正しました。