「桁数がすごく大きい数字同士の最大公約数（GCD）なんて、素因数分解していたらいつまで経っても終わらない……」
「『ユークリッドの互除法』の仕組みって、なんで余りで割り続けるとうまくいくの？」
高校数学Aのもう一つの重要単元「整数の性質」の第1回は、すべての整数論の土台となる「約数・倍数の性質」と、桁の大きい数の最大公約数を一撃で求める最強のアルゴリズム「ユークリッドの互除法」を徹底解説します！
整数の割り算がもつ美しい構造を紐解き、複雑な計算を劇的にシンプルにするテクニックをマスターしましょう！
1. 整数の割り算と最大公約数・最小公倍数の基本
整数を別の整数で割ったときの「商と余り」の関係式と、基本的な用語を確認します。
💡 【整数の除法の定理】
整数 $a$ と正の整数 $b$ について、$a$ を $b$ で割ったときの商を $q$、余りを $r$ とすると、次の一意的な関係が成り立ちます。
$$\mathbf{a = bq + r} \quad (0 \le r < b)$$
【最大公約数（GCD）と最小公倍数（LCM）の性質】
2 つの正の整数 $a, b$ の最大公約数を $g$ とすると、$a = gx, \ b = gy$（$x, y$ は互いに素な整数）とおくことができます。
このとき、最小公倍数 $l$ との間には次の重要な関係が成り立ちます：
$$\mathbf{l = gxy} \quad \text{かつ} \quad \mathbf{ab = gl}$$
2. ユークリッドの互除法（最大の武器）
桁数が大きい 2 つの整数の最大公約数を求めるとき、素因数分解する代わりに「割り算の余り」を次々に利用して数値を小さくしていく方法をユークリッドの互除法といいます。
💡 【ユークリッドの互除法の原理と手順】**
整数 $a$ と $b$（$a > b$）の最大公約数を求めたいとき：
- $a$ を $b$ で割った余りを $r_1$ とする（$a = bq_1 + r_1$）。このとき、$\text{GCD}(a, b) = \text{GCD}(b, r_1)$ が成り立つ。
- 今度は $b$ を $r_1$ で割った余り $r_2$ を求める（$b = r_1 q_2 + r_2$）。すると、$\text{GCD}(b, r_1) = \text{GCD}(r_1, r_2)$ となる。
- この割り算を繰り返し、余りが $0$ になったときの「割る数（直前の余り）」が求める最大公約数となる！
3. 【実践例題】ユークリッドの互除法の活用
【例題1】大きな数字の最大公約数を求める
1173 と 1361 の最大公約数をユークリッドの互除法を用いて求めよ。 解答・解説を表示する1. 割り算を順番に実行する $1361 \div 1173$ を計算する：
$1361 = 1173 \times 1 + 188$ （余りは $188$） 次に、割る数 $1173$ を余り $188$ で割る：
$1173 = 188 \times 6 + 45$ （余りは $45$） さらに、割る数 $188$ を余り $45$ で割る：
$188 = 45 \times 4 + 8$ （余りは $8$） さらに、割る数 $45$ を余り $8$ で割る：
$45 = 8 \times 5 + 5$ （余りは $5$） さらに、割る数 $8$ を余り $5$ で割る：
$8 = 5 \times 1 + 3$ （余りは $3$） さらに、割る数 $5$ を余り $3$ で割る：
$5 = 3 \times 1 + 2$ （余りは $2$） さらに、割る数 $3$ を余り $2$ で割る：
$3 = 2 \times 1 + 1$ （余りは $1$） 最後に、割る数 $2$ を余り $1$ で割る：
$2 = 1 \times 2 + 0$ （余りが $0$ になった！） 2. 結論を導く
余りが $0$ になったときの「割る数（直前の余り）」は $1$ である。
したがって、1173 と 1361 は互いに素であり、最大公約数は $1$ である。【答え】 最大公約数は 1
【例題2】互除法の逆算（一次不定方程式への布石）
ユークリッドの互除法を逆にたどることで、次の等式を満たす整数 $x, y$ の一組を求めよ。
$$29x + 19y = 1$$ 解答・解説を表示する1. まず 29 と 19 で互除法を行う $29 = 19 \times 1 + 10 \implies 10 = 29 – 19 \times 1$ ① $19 = 10 \times 1 + 9 \implies 9 = 19 – 10 \times 1$ ② $10 = 9 \times 1 + 1 \implies 1 = 10 – 9 \times 1$ ③ 2. 下の式から逆に代入して「1」の形を作る（逆算）
式③に式②を代入する： $$1 = 10 – 9 \times 1 = 10 – (19 – 10 \times 1) = 10 \times 2 – 19 \times 1$$ さらに式①（$10 = 29 – 19$）を代入する： $$1 = (29 – 19) \times 2 – 19 \times 1 = 29 \times 2 – 19 \times 2 – 19 \times 1 = 29 \times 2 + 19 \times (-3)$$3. 係数を比較する
$29(2) + 19(-3) = 1$ となるため、一組の整数解は $(x, y) = (2, -3)$ と求まる。【答え】 $(x, y) = (2, -3)$
4. まとめ
- 除法の定理： $a = bq + r \ (0 \le r < b)$ の形に必ず落とし込める！
- ユークリッドの互除法： 大きな数の最大公約数を求めるには、「余りが 0 になるまで割り算を繰り返す」！
- 逆算のテクニック： 互除法の式を下から逆に代入していくことで、不定方程式の整数解を一発で発見できる！
- 最小公倍数との関係： $ab = gl$（最大公約数 $\times$ 最小公倍数 ＝ 2数の積）の公式も常に強力な武器になる！
整数の性質の基本となる除法の原理と、ユークリッドの互除法の仕組みがすっきりと整理できました！
次回は「【数A：第2回】整数の割り算の余りと合同式｜整数の性質②（あまりの世界の計算術）」を解説します！
コメント