合同式の性質とその証明

高校数学

5235

概要

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

合同式の定義

合同式

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

合同式の性質とその証明

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

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

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

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

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

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

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

$a + c = (b + n k) + (d + n l) = n (k + l) + b + d$ より $a + c \equiv b + d$ である．
$a - c = (b + n k) - (d + n l) = n (k - l) + b - d$ より $a - c \equiv b - d$ である．
$a c = (b + n k) (d + n l) = n (n k l + b l + d k) + b d$ より $a c \equiv b d$ である．

$7001 \equiv 1 \mod 7$ ， $43 \equiv 1 \mod 7$ より

$7001 + 43 \equiv 1 + 1 \mod 7$ すなわち $7044 \equiv 2 \mod 7$ であるから， $7044$ を $7$ で割ったときの余りは $2$ である．
$7001 - 43 \equiv 1 - 1 \mod 7$ すなわち $6958 \equiv 0 \mod 7$ であるから， $6958$ は $7$ で割り切れる．
$7001 \cdot 43 \equiv 1 \cdot 1 \mod 7$ すなわち $301043 \equiv 1 \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 \cdot 17 + 1$ より $120 \equiv 1 \mod 7$ であるから，命題3より $120^{100} \equiv 1^{100} \mod 7$ が成り立つ．従って， $120^{100}$ を $7$ で割ったときの余りは $1$ である．

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

合同式の除法

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

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

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

問題の解答例

問題1

$7777 \equiv 210 \equiv 0 \mod 7$ ， $13 \equiv 6 \mod 7$ より $7777 + 210 + 13 \equiv 0 + 0 + 6 \mod 7$ すなわち $8000 \equiv 6 \mod 7$ であるから， $8000$ を $7$ で割ったときの余りは $6$ である．