ユークリッドの互除法
大きな数の GCD を効率よく求めるアルゴリズムです。
互除法の原理
GCD(a, b) = GCD(b, a mod b)（a を b で割った余りを r とすると GCD(a,b)=GCD(b,r)）
r=0 になったとき b が GCD
📘 例題①（互除法の計算）
GCD(323, 187) を求めよ。
323 = 187×1 + 136
187 = 136×1 + 51
136 = 51×2 + 34
51 = 34×1 + 17
34 = 17×2 + 0
解答：GCD(323, 187) = 17
GCD(323, 187) を求めよ。
323 = 187×1 + 136
187 = 136×1 + 51
136 = 51×2 + 34
51 = 34×1 + 17
34 = 17×2 + 0
解答：GCD(323, 187) = 17
📘 例題②（互いに素の判定）
GCD(35, 24) を求めよ。
35 = 24×1 + 11
24 = 11×2 + 2
11 = 2×5 + 1
2 = 1×2 + 0
GCD = 1 → 35 と 24 は互いに素
GCD(35, 24) を求めよ。
35 = 24×1 + 11
24 = 11×2 + 2
11 = 2×5 + 1
2 = 1×2 + 0
GCD = 1 → 35 と 24 は互いに素
💡 ポイント
- 互除法：大きい数÷小さい数の余りを計算して繰り返す
- 余りが0になったとき、最後の割る数がGCD
- GCD(a,b)=1 ⟺ a と b は互いに素
練習問題
- ユークリッドの互除法で GCD(273, 91) を求めよ。
- ユークリッドの互除法で GCD(437, 209) を求めよ。
- GCD(n, 12)=4 を満たす 20 以下の自然数 n をすべて求めよ。
解答・解説
- 273=91×3+0 → GCD=91
- 437=209×2+19、209=19×11+0 → GCD=19
- n=4k（4の倍数）かつ GCD(n,12)=4 → k と 3 が互いに素（k:3の倍数でない）。n≤20 → k=1,2,4,5 → n=4,8,16,20（20=4×5、GCD(20,12)=4 ✓）→ 4, 8, 16, 20