互いに素な整数$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$で割ったときの余りを一列に並べたものは$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$を$B$で割ったときの商を$s$、余りを$r_1$とすると
\[mA=sB+r\]
と書け、変形すると
\[r_1=mA-sB\]
となります。
同様に$nA$を$B$で割ったときの商を$t$、余りを$r_2$とすると
\[r_2=nA-tB\]
と書けます。
仮定より$r_1=r_2$なので
$A,B$は互いに素なので$m-n$が$B$の倍数であることがわかります。
\[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$のとき
したがって、$A$の倍数$mA,nA$の差が$B$の倍数となるとき、$B$で割ったときの余りが等しくなります。
\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$を並び替えたものが繰り返し現れるということです。
Share:
