指針 57 〈ユークリッドの互除法〉
(2) 回目の余りを求める計算における商を gk, 余りをとして,k がなるべく小さくな
条件を考える。 N回目で終わるとき, N-2> PN-1>YN= 0 に注意する。
(1)2071115151 にユークリッドの互除法を用いると
20711=15151・1+5560
151515560.2+4031
5560=4031・1 + 1529
4031=1529・2+973
1529973・1 +556
973=556・1+417
556=417・1+139
417139・3
よって, 2071115151の最大公約数は 139
(2)mnに対してユークリッドの互除法を用いたとき, 回目の余
りを求める計算における商を gk, 余りを とする。
余りを求める計算がN回目で終わるとすると, 余りを求める計算
は以下のようになる。
m=ng tr
n=rig2+r2
min
ン
+
utv
r1=r293+r3
rn-3=rn-29N-1+rn-1
YN-2=PN-19N
ここで, 割り算の性質により
n>>> rs >...... > N-1 >0
(割る数)> (余り)
また,Nを大きくするためには,gn (k=1, 2,......, N) をなるべ
く小さくすればよいから, それぞれのk に対する の最小値は,
N-2 > YN-1 に注意すると
g1=92=......=QN-1=1,Qv=2
gx = 1 としてしまうと
N-1 が最小となるとき, Nは最大となるから, N-1 = 1 として余
りを求める計算を逆順にたどり, 左辺を求めていくと
PN-2 = YN-1QN より
N-2 = N-1 となり
N-2 >
N-1 に反する。
1.2=2
2.1+1=3
3・1+2=5
5.1+3=8
ある
8・1+5=13
13.1+8=21
21・1+13=34
34・1+21=55
55・1+34= 89
89・1+55=144
したがって,=89, n=55のとき,N = 9 となり Nは最大とな
る。
144は3桁の数であ
計算はここで終わり
の2数 89,55 が求
えとなる。
新学期
