高校数学解説

(高校生むけ)合同式の基本

合同式

337

合同式の基本

(※今回の記事は生徒に解説するために作ったので,100％高校範囲です.)

断りがなければ, $a, b, c$ を整数, $k, n, m$ を0以上の整数とします.

1.合同式とは

合同式とは,整数の剰余(あまりのことね.)に着目した式のことです.
例えば, $a$ と $b を m$ で割った剰余が等しいことを

$a \equiv b (\mod n)$

と書きます.
これを $a, b$ は $n$ を法として合同( $a$ and $b$ are congruent modulo $n$ )と言います.
(modulo【前】:〜を法として)
例えば,
$57 \equiv 7 (\mod 5), 57 \equiv 2 (\mod 5), 57 \equiv - 3 (\mod 5)$
です.
これは適切な整数 $K$ を用いて $57$ を,

$57 = 5 K + 7, 57 = 5 K + 2, 57 = 5 K - 3$

と表せることに対応していますね.

2.合同式の性質1

合同式の性質1

$(i) a \equiv a (\mod n)$ (反射律)
$(ii) a \equiv b (\mod n) ⟹ b \equiv a (\mod n)$ (対称律)
$(iii) a \equiv b (\mod n) かつ b \equiv c (\mod n) ⟹ a \equiv c (\mod n)$ (推移律)

合同式の性質2-1

任意の整数 $a, b, c, d$ に対し, $a \equiv b (\mod n), c \equiv d (\mod n) のとき,$

$(I) a + c \equiv b + d (\mod n)$ (加法)
$(II) a - c \equiv b - d (\mod n)$ (減法)
$(III) a c \equiv b d (\mod n)$ (乗法)

合同式の性質2-2

$(I)$
条件より,
$a + c \equiv b + c (\mod n), b + c \equiv b + d (\mod n)$
推移律 $(iii)$ より,
$∴ a + c \equiv b + c \equiv b + d (\mod n) .$

$(II)$
条件より, $c, d$ は任意なので $c \to - c, d \to - d$ と置き換えて, $(I)$ より,
$∴ a - c \equiv b - d (\mod n) .$

$(III)$
条件と $(I)$ より,
$a c \equiv b c (\mod n), b c \equiv b d (\mod n)$
推移律 $(iii)$ より,
$∴ a c \equiv b c \equiv b d (\mod n) .$

これで合同式においても等式と同様に加減乗が保障されました.
難しかったら最悪 $a = b + n k, c = d + n l$ と置けば証明できます.

合同式の性質2-2

$(IV)$ 任意の整数 $a, b$ に対し, $a c \equiv b c (\mod n)$ で $c$ と $n$ が互いに素のとき, $a \equiv b (\mod n)$ (除法)

合同式の性質2-2

$(IV)$

$a c \equiv b c (\mod n)$ 即ち $(a - b) c \equiv 0 (\mod n)$ より, $(a - b) c$ は $n$ の倍数.
$c$ と $n$ が互いに素ゆえ, $(a - b)$ は $n$ の倍数となるから
$∴ a \equiv b (\mod n)$ .

条件付きで加減乗(除)が保障されました.

べき乗

$(V)$ $a \equiv b (\mod n) ⟹ a^{m} \equiv b^{m} (\mod n)$

べき乗

$(V)$
数学的帰納法を用いる.
$(i) m = 1$ のときは自明.
$(ii) m = k$ のとき $a^{k} \equiv b^{k} (\mod n)$ と仮定すると, $m = k + 1$ のとき $a^{k + 1} \equiv b^{k + 1} (\mod n)$ を示す.
仮定と条件より,
$a^{k} \cdot a \equiv b^{k} \cdot a (\mod n), a \cdot b^{k} \equiv b \cdot b^{k} (\mod n)$ だから,
$∴ a^{k + 1} \equiv a \cdot b^{k} \equiv b^{k + 1} (\mod n) \dots m = k + 1$ でも成立.
以上により,題意は示された.

$(III)$ を使ってもよいならもっと簡単に示せますね.

フェルマーの小定理

$(VI)$ $p$ を素数とすると,
$a^{p} \equiv a (\mod p)$
$(VII)$ $p$ が素数, $a, p$ が互いに素のとき,
$a^{p - 1} \equiv 1 (\mod p)$

フェルマーの小定理

$(VI)$
$k = 1, . . ., p - 1$ のとき,
$k_{p} C_{k} = p_{p - 1} C_{k - 1}$ 　, $p, k$ は互いに素より,
$_{p} C_{k}$ は $p$ の倍数だから,二項定理より,

$a^{p} = [(a - 1) + 1]^{p} = (a - 1)^{p} +_{p} C_{1} (a - 1)^{p - 1} + . . . +_{p} C_{p - 1} (a - 1) + 1 \equiv (a - 1)^{p} + 1 (\mod p)$

よって,これを繰り返すと,

$a^{p} \equiv (a - 1)^{p} + 1 \equiv (a - 2)^{p} + 2 \equiv . . . \equiv 1^{p} + a - 1 \equiv a (\mod p)$

を得る.

$(VII)$
条件より $(IV)$ が使えるので, $(VI)$ の両辺を $a$ で割ると,
$∴ a^{p - 1} \equiv 1 (\mod p) .$

3.使用例1:ユークリッドの互除法

合同式を使うと,次のようになります.

ユークリッドの互除法

$0 < r_{k} < . . . < r_{1} < b$
$a \equiv r_{1} (\mod b), b \equiv r_{2} (\mod r_{1}), . . ., r_{k - 1} \equiv 0 (\mod r_{k}) ⟹ gcd (a, b) = r_{k}$

$\frac{10033}{12877}$ を約分せよ.(数検1級 2010/4)

互除法で最大公約数を求める.

$12877 \equiv 2844 (\mod 10033)$
$10033 \equiv 1501 (\mod 1244)$
$2844 \equiv 1343 (\mod 1501)$
$1501 \equiv 158 (\mod 1343)$
$1343 \equiv 79 (\mod 158)$
$158 \equiv 0 (\mod 79)$

より, $gcd (10033, 12877) = 79$ だから,
$∴ \frac{10033}{12877} = \frac{10033 / 79}{12877 / 79} = \frac{127}{163} .$

4.使用例2:一次不定方程式

次の方程式の整数解をすべて求めよ.
$72 x + 32 y = 3$

小さい方の係数を法として計算

$71 x + 32 y \equiv 71 x \equiv 7 x \equiv 3 (\mod 32) . . . (1)$
$3 \equiv 35 (\mod 32)$ ( $(1)$ より,右辺が $7$ の倍数になるようにする)より,
$7 x \equiv 35 (\mod 32)$
$7$ と $32$ は互いに素だから,
$x \equiv 5 (\mod 32)$
よって, $x = 32 k + 5 (k \in Z)$ と表せるから,
$32 y = - 71 x + 3 = - 71 (32 k + 5) + 3 = - 71 \cdot 32 k - 352$
故に,
$∴ x = 32 k + 5, y = - 71 k - 11 (k \in Z) .$

特殊解を求めなくても一次不定方程式を解くことができました.

4.演習問題

$(1) 2^{50}$ を7で割った余りを求めよ.(易)
$(2) 17^{50}$ を9で割った余りを求めよ.(易)
$(3) 23^{100}$ を19で割った余りを求めよ.(易)
$(4) n^{5} - n$ が $30$ の倍数になることを示せ.(普)
$(5) n$ が自然数のとき, $2^{6 n - 5} + 3^{2 n}$ が $11$ の倍数となることを示せ.(普)
$(6) n$ が自然数のとき, $5^{2 n - 1} + 7^{2 n - 1} + 23^{2 n - 1}$ が $35$ の倍数となることを示せ.(普)
$(7)$ $\sum_{k = 1}^{n} k!$ が平方数となるような $n$ を全て求めよ.(難)
(ヒント: $0$ から $9$ までの平方の $1$ の位に注目せよ.)
$(8)$ 整式 $x^{2023} - 1$ を整式 $x^{4} + x^{3} + x^{2} + x + 1$ で割ったときの余りを求めよ.(難)
(ヒント: $x^{4} + x^{3} + x^{2} + x + 1 \equiv 0 (\mod x^{4} + x^{3} + x^{2} + x + 1)$ より, $x^{5} - 1 \equiv 0 (\mod x^{4} + x^{3} + x^{2} + x + 1)$ )
$(9)$ 自然数 $n$ に対し, $n^{2} + 2, n^{4} + 2, n^{6} + 2$ の最大公約数を求めよ.(難)
(ヒント: $n^{4} + 2, n^{6} + 2$ と $n^{2} + 2$ でそれぞれ互除法.)

投稿日：2023年8月2日

この記事を高評価した人

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

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

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

ドジコジ

5315

東北大学工学研究科出身できるだけ受け売りはせず，自分で思いついた解法や妄想を備忘録がてら書き綴っていこうと思います．

他の人のコメント

コメントはありません。

読み込み中

ドジコジ

(高校生むけ)合同式の基本

合同式の基本
1.合同式とは
2.合同式の性質1
3.使用例1:ユークリッドの互除法
4.使用例2:一次不定方程式
4.演習問題