合同式の性質とその証明

高校数学

3360

概要

本稿では，整数の合同に関する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$を満たすとき，以下が成り立つ:

$a+c\equiv b+d$
$a-c\equiv b-d$
$ac\equiv bd$

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

$a+c=(b+nk)+(d+nl)=n(k+l)+b+d$より$a+c\equiv b+d$である．
$a-c=(b+nk)-(d+nl)=n(k-l)+b-d$より$a-c\equiv b-d$である．
$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$より

$7001+43\equiv1+1\ \mathrm{mod}\ 7$すなわち$7044\equiv2\ \mathrm{mod}\ 7$であるから，$7044$を$7$で割ったときの余りは$2$である．
$7001-43\equiv1-1\ \mathrm{mod}\ 7$すなわち$6958\equiv0\ \mathrm{mod}\ 7$であるから，$6958$は$7$で割り切れる．
$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$が成り立つ．

数学的帰納法

$m=2$のときは，命題2の3において$c=a,d=b$とすることにより成り立つ．
ある$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$である．