4
高校数学解説
文献あり

合同式の性質とその証明

3282
0
$$$$

概要

本稿では,整数の合同に関する5つの基本的な性質の証明を与える.

合同式の定義

合同式

整数$a,b$を正の整数$n$で割ったときの余りが一致することを
$$ a\equiv b\ \mathrm{mod}\ n $$
と書く.

合同式の性質とその証明

以下,正の整数$n$をひとつ固定する.特に断りのない限り,$a\equiv b$と書いた場合は$a\equiv b\ \mathrm{mod}\ n$を意味するものとする.

整数$a,b$$a\equiv b$を満たすとき,$a-b\equiv0$が成り立つ.

$a,b$$n$で割ったときの商をそれぞれ$q,q'$とする.さらに,$a\equiv b$であることに注意して,$a,b$$n$で割ったときの余りを$r$とする.このとき$a-b=(nq+r)-(nq'+r)=n(q-q')$であるから$a-b\equiv0$が成り立つ.

合同式の加法・減法・乗法

整数$a,b,c,d$$a\equiv b$かつ$c\equiv d$を満たすとき,以下が成り立つ:

  1. $a+c\equiv b+d$
  2. $a-c\equiv b-d$
  3. $ac\equiv bd$

補題1および$a\equiv b$かつ$c\equiv d$より,$a-b$$c-d$はともに$n$で割り切れるから,整数$k,l$を用いて$a-b=nk,c-d=nl$と表せる.

  1. $a+c=(b+nk)+(d+nl)=n(k+l)+b+d$より$a+c\equiv b+d$である.
  2. $a-c=(b+nk)-(d+nl)=n(k-l)+b-d$より$a-c\equiv b-d$である.
  3. $ac=(b+nk)(d+nl)=n(nkl+bl+dk)+bd$より$ac\equiv bd$である.

$7001\equiv 1\ \mathrm{mod}\ 7$$43\equiv 1\ \mathrm{mod}\ 7$より

  1. $7001+43\equiv1+1\ \mathrm{mod}\ 7$すなわち$7044\equiv2\ \mathrm{mod}\ 7$であるから,$7044$$7$で割ったときの余りは$2$である.
  2. $7001-43\equiv1-1\ \mathrm{mod}\ 7$すなわち$6958\equiv0\ \mathrm{mod}\ 7$であるから,$6958$$7$で割り切れる.
  3. $7001\cdot43\equiv1\cdot1\ \mathrm{mod}\ 7$すなわち$301043\equiv1\ \mathrm{mod}\ 7$であるから,$301043$$7$で割ったときの余りは$1$である.

$8000=7777+210+13$と合同式を用いて,$8000$$7$で割ったときの余りを求めよ.

合同式の累乗

整数$a,b$$a\equiv b$を満たすとき,任意の$2$以上の整数$m$に対して$a^m\equiv b^m$が成り立つ.

数学的帰納法
  1. $m=2$のときは,命題2の3において$c=a,d=b$とすることにより成り立つ.
  2. ある$2$以上の整数$m$に対して$a^m\equiv b^m$であると仮定する.このとき,命題2の3において$c=a^m,d=b^m$とすることにより$a^{m+1}\equiv b^{m+1}$が得られる.

以上より,任意の$2$以上の整数$m$に対して$a^m\equiv b^m$が成り立つ.

整数の累乗の余り

$120^{100}$$7$で割ったときの余りを求めよう.$120=7\cdot17+1$より$120\equiv1\ \mathrm{mod}\ 7$であるから,命題3より$120^{100}\equiv1^{100}\ \mathrm{mod}\ 7$が成り立つ.従って,$120^{100}$$7$で割ったときの余りは$1$である.

$120^{100}$$11$で割ったときの余りを求めよ.

合同式の除法

整数$a,b,c$$ab\equiv ac$を満たすとき,$a$$n$が互いに素ならば$b\equiv c$が成り立つ.

補題1および$ab\equiv ac$より,$ab-ac=a(b-c)$$n$で割り切れるから,整数$k$を用いて$a(b-c)=nk$と表せる.よって,$a$$n$が互いに素ならば,ある整数$k'$が存在して$b-c=nk'$であるから$b\equiv c$が成り立つ.

「整数$a,b,c$$ab\equiv ac$を満たすとき,$a$$n$の倍数でなければ$b\equiv c$」は成り立つか.成り立つ場合は証明し,成り立たない場合は反例を挙げよ.

問題の解答例

問題1

$7777\equiv210\equiv0\ \mathrm{mod}\ 7$$13\equiv6\ \mathrm{mod}\ 7$より$7777+210+13\equiv0+0+6\ \mathrm{mod}\ 7$すなわち$8000\equiv6\ \mathrm{mod}\ 7$であるから,$8000$$7$で割ったときの余りは$6$である.

問題2

$120=11^2-1$より$120\equiv-1\ \mathrm{mod}\ 11$であるから,命題3より$120^{100}\equiv(-1)^{100}\ \mathrm{mod}\ 11$が成り立つ.従って,$120^{100}$$11$で割ったときの余りは$1$である.

問題3

成り立たない.実際,$n=9,a=3,b=1,c=4$とすると,$3\cdot1\equiv3\cdot4\ \mathrm{mod}\ 9$かつ$3$$9$の倍数ではないが,$1\equiv4\ \mathrm{mod}\ 9$は成り立たない.

参考文献

投稿日:20201216

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

電気魚
電気魚
21
24766

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中