54) ユークリッドの互除法
(職進の会宝不
(1) 957 と 754の最大公約数を求めよ。
(2) 2つの整数 2n+30 と n+3の最大公約数が3となるような 30 以下の
自然数nをすべて求めよ。
(解答
(1) 957 を754 で割ると商が1で余りが 203 になる。次に, 754を203 で割る.これ
を続けると,
957=754·1+203
これらの計算は,次のような筆算を使うと便利である
754=203-3+145
2
1
29)58 )145 )203 ) 754 ) 957
58 116 145 609 754
3
203=145·1+58
145=58·2+29
0
29
58 145 203
58=29·2+0
よって, aとbの最大公約数を gcd (a, b) と表すと,
gcd(957, 754)=gcd(754, 203)=gcd(203, 145)=gcd(145, 58)=gcd(58, 29)=D29
が成り立つから, 957 と 754 の最大公約数は,58 と 29 の最大公約数と等しく, 29
(2) 2n+30 をn+3 で割ると,商が2で余りが24 となる.つまり,
2n+30=(n+3)·2+24
が成り立っていて, ユークリッドの互除法より,
gcd(2n+30, n+3)=gcd(n+3, 24)
である。よって,条件から,
gcd(n+3, 24)=3
であるが,24=2°·3 に注意すると, ①が成り立つ条件は,
n+3 が3の倍数であり,かつ,2の倍数でないこと
である。1<n<30 より, 4Sn+3<33 であるから,②を満たす整数n+3 は,
LOS
…D
…の
n+3=9, 15, 21, 27, 33
.n=6, 12, 18, 24, 30
