ユークリッドの互除法 - FC2

ユークリッドの互除法
数学 I・A 補完ノート
http://mhidet.web.fc2.com/text/
1 割り算と最大公約数
2 つの自然数と最大公約数について，次のことが成り立つ．
✓
✏
2 つの自然数 a，b について，a を b で割った時の商を q ，余りを r とすると，a と b の最大公約数は b と r
の最大公約数に等しい．
✒
✑
(証明)：
条件より
a = bq + r
だから，
r = a − bq
である．a と b の最大公約数を m，b と r の最大公約数を n とする．このとき m は a と b の公約数で
あるから，r = a − bq より，m は r の約数である．つまり，m は b と r の約数である．
b と r の最大公約数は n であるから m ≦ n
一方，n は b と r の公約数だから，a = bq + r より，n は a の約数である．よって，n は b と a の公約
数である．
a と b の最大公約数は m であるから，n ≦ m
したがって，m = n である．■
2 ユークリッドの互除法
a と b の最大公約数を
gcd(a, b)
のように書く．ここで，2 つの自然数 a，b について，a を b で割った時の商を q ，余りを r とすると，
gcd(a, b) = gcd(b, r)
である．これを逐次繰り返して最大公約数を求める方法をユークリッドの互除法という．
• 247 と 91 の最大公約数を求めてみよう．
247 を 91 で割った余りは 65 なので
gcd(274, 91) = gcd(91, 65)
1
91 を 65 で割った余りは 26 なので
gcd(91, 65) = gcd(65, 26)
65 を 26 で割った余りは 13 だから
gcd(65, 26) = gcd(26, 13)
したがって，
gcd(26, 13) = 13
である．
3 最大公約数を表す式
たとえば，177 と 52 をユークリッドの互除法により最大公約数を求めると，次のようになる．
gcd(177, 52) = gcd(52, 21)
= gcd(21, 10)
= gcd(10, 1)
=1
である．これより最大公約数 1 を 177 と 52 で表すことができる．すなわち，ユークリッドの互除法を逆にたど
れば，
1 = 21 − 10 · 2
= 21 − (52 − 21 · 2) · 2
= 21 · 5 − 52 · 2
= (177 − 52 · 3) · 5 − 52 · 2
= 177 · 5 − 52 · 17
= 177 · 5 + 52 · (−17)
このように互除法の計算を利用すると整数 a，b の最大公約数を d を適当な整数 p，q を用いて，
d = ap + bq
と書くことができる．特に a と b が互いに素であるとき
ap + bq = 1
を満たす整数 p と q が存在する．両辺に整数 c を掛けると，
a(pc) + b(qc) = c
以上のことより，次のことが言える．
✓
✏
2 つの整数 a，b が互いに素であるとき，任意の整数 c について，ax + by = c を満たす整数 x，y が存在
する．
✒
✑
• 27x + 16y = 1 を満たす整数 x，y の組を 1 つ求めてみよう．
2
ユークリッドの互除法により
gcd(27, 16) = gcd(16, 11)
= gcd(11, 5)
= gcd(5, 1)
=1
27 と 16 は互いに素である．したがって，これを逆にたどると，
1 = 11 − 5 · 2
= 11 − (16 − 11 · 1) · 2
= −16 · 2 + 11 · 3
= 16 · (−2) + 11 · 3
= 16 · (−2) + (27 − 16 · 1) · 3
= 27 · 3 + 16 · (−5)
したがって，求める (x, y) の組の 1 つは (x, y) = (3, −5) である．
• 27x + 16y = 2 を満たす整数 x，y の組を 1 つ求めてみよう．
先ほどの結果より，両辺に 2 を掛けると，
27 · (3 · 2) + 16 · (−5 · 2) = 2
だから，求める (x, y) の組の 1 つは (x, y) = (6, −10) である．
4 演習問題
1. 次の整数の組の最大公約数をユークリッドの互除法により求めよ．
(a) 611,564
(b) 5217,2961
(c) 779,391
2. a，b を自然数とし，等式
ax + by = 1
を満たす整数 x，y が存在するとき，a と b は互いに素であることを証明せよ．
3. 次の等式を満たす整数 x，y の組を 1 つ求めよ．
(a) 23x + 16y = 1
(b) 67x + 20y = 2
(c) 60x + 41y = 3
3

Download Report