倍数を互いに素な自然数で割ったときの余りの性質 ~ 数学について考えてみる

　互いに素な整数

A

$A$ と自然数

B

$B$ について

A, 2 A, \dots, (B - 1) A, B A

$A,2A,\cdots,(B-1)A,BA$ をそれぞれ

B

$B$ で割ったときの余りを一列に並べたものは

0, 1, \dots, B - 2, B - 1

$0,1,\cdots,B-2,B-1$ の並び替えである

という性質があります。

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

　上記の性質は

A, 2 A, \dots, (B - 1) A, B A

$A,2A,\cdots,(B-1)A,BA$ の

B

$B$ 個の

A

$A$ の倍数をそれぞれ

B

$B$ で割ったときにどの余りも重複しないことを主張しています。

そこで、上記の性質があることを確かめるために

1

$1$ 以上

B

$B$ 以下の自然数

m, n

$m,n$ （ただし、

m > n

$m>n$ ）をもちいて表される

A

$A$ の倍数

m A, n A

$mA,nA$ それぞれ

B

$B$ で割ったときの余りが等しいと仮定します。

m A

$mA$ を

B

$B$ で割ったときの商を

s

$s$ 、余りを

r_{1}

$r_1$ とすると

m A = s B + r

$mA=sB+r$

と書け、変形すると

r_{1} = m A - s B

$r_1=mA-sB$

となります。

同様に

n A

$nA$ を

B

$B$ で割ったときの商を

t

$t$ 、余りを

r_{2}

$r_2$ とすると

r_{2} = n A - t B

$r_2=nA-tB$

と書けます。

仮定より

r_{1} = r_{2}

$r_1=r_2$ なので

m A - s B = n A - t B

$mA-sB=nA-tB$

であり、

\begin{aligned} m A - n A & = s B - t B \\ (m - n) A & = (s - t) B \end{aligned}

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

となります。

A, B

$A,B$ は互いに素なので

m - n

$m-n$ が

B

$B$ の倍数であることがわかります。

しかし、

m, n

$m,n$ は

1

$1$ 以上

B - 1

$B-1$ 以下の自然数かつ

m > n

$m>n$ なので

m - n

$m-n$ が

B

$B$ の倍数になることはありません。

\begin{aligned} 1 ≦ m ≦ B, & 1 ≦ n ≦ B \\ \Rightarrow & 1 - B ≦ m - n ≦ B - 1 \end{aligned}

$\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$ より

m - n > 0

$m-n>0$ なので

0 < m - n ≦ B - 1

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

m - n

$m-n$ は

B - 1

$B-1$ 以下の自然数なので

B

$B$ の倍数でない。

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

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

上記のことから、

A, 2 A, \dots, (B - 1) A, B A

$A,2A,\cdots,(B-1)A,BA$ の

B

$B$ 個の

A

$A$ の倍数をそれぞれ

B

$B$ で割ったときの余りは

0, 1, \dots, B - 2, B - 1

$0,1,\cdots,B-2,B-1$ の

B

$B$ 個の中から重複せずに1つずつ現れる、すなわち

A, 2 A, \dots, (B - 1) A, B A

$A,2A,\cdots,(B-1)A,BA$ をそれぞれ

B

$B$ で割ったときの余りを一列に並べたものは

0, 1, \dots, B - 2, B - 1

$0,1,\cdots,B-2,B-1$ の並び替えである

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

　互いに素な整数

A

$A$ と自然数

B

$B$ について

連続した

B

$B$ 個の

A

$A$ の倍数をそれぞれ

B

$B$ で割ったときの余りを一列に並べたものは

0, 1, \dots, B - 2, B - 1

$0,1,\cdots,B-2,B-1$ の並び替えである

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

k

$k$ 以上

B + k - 1

$B+k-1$ 以下の整数

m, n

$m,n$ （

k :

$k:$ 任意の整数；

m > n

$m>n$ ）をもちいて表される

A

$A$ の倍数

m A, n A

$mA,nA$ それぞれ

B

$B$ で割ったときの余りが等しいと仮定します。

m A, n A

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

\begin{aligned} r_{1} & = m A - s B \\ r_{2} & = n A - t B \end{aligned}

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

と書けます。

仮定より

r_{1} = r_{2}

$r_1=r_2$ なので

\begin{aligned} m A - n A & = s B - t B \\ (m - n) A & = (s - t) B \end{aligned}

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

A, B

$A,B$ は互いに素なので

m - n

$m-n$ が

B

$B$ の倍数であることがわかります。

しかし、

m, n

$m,n$ は

k

$k$ 以上

B + k - 1

$B+k-1$ 以下の整数かつ

m > n

$m>n$ なので

m - n

$m-n$ が

B

$B$ の倍数になることはありません。

\begin{aligned} k ≦ m ≦ B + k - 1, & k ≦ n ≦ B + k - 1 \\ \Rightarrow & 1 - B ≦ m - n ≦ B - 1 \end{aligned}

$\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$ より

m - n > 0

$m-n>0$ なので

0 < m - n ≦ B - 1

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

m - n

$m-n$ は

B - 1

$B-1$ 以下の自然数なので

B

$B$ の倍数でない。

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

連続した

B

$B$ 個の

A

$A$ の倍数をそれぞれ

B

$B$ で割ったときの余りを一列に並べたものは

0, 1, \dots, B - 2, B - 1

$0,1,\cdots,B-2,B-1$ の並び替えである

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

　では、

B

$B$ で割ったときの余りが等しくなる

A

$A$ の倍数の条件は何でしょうか？

任意の整数

m, n

$m,n$ （ただし、

m > n

$m>n$ ）をもちいて表される

A

$A$ の倍数

ｍ A, n A

$ｍA,nA$ それぞれについて

\begin{aligned} r_{1} & = m A - s B \\ r_{2} & = n A - t B \end{aligned}

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

と書けます。

r_{1} = r_{2}

$r_1=r_2$ のとき

\begin{aligned} m A - n A & = s B - t B \\ (m - n) A & = (s - t) B \end{aligned}

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

A, B

$A,B$ は互いに素なので

m - n

$m-n$ は

B

$B$ の倍数であることがわかります。
したがって、

A

$A$ の倍数

m A, n A

$mA,nA$ の差が

B

$B$ の倍数となるとき、

B

$B$ で割ったときの余りが等しくなります。

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

例として連続した

22

$22$ の倍数（

22 k

$22k$ の項目）をそれぞれ

13

$13$ で割ったときの余り（

mod 13

$\text{mod}\ 13$ の項目）を見てみると、13個の余りの並びは

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12

$0,1,2,3,4,5,6,7,8,9,10,11,12$ を並び替えたもので、しかも繰り返し現れていることがわかります。

数学について考えてみる

2024年12月15日

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

不正行為を報告

Labels

Blog Archive

PR

Popular Posts(Weekly)

Link

About