Question

りんご

解答の赤い蛍光マーカーのところが何故かよく分からないです、教えてくださいm(_ _)m

指針 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 が求
えとなる。
新学期

57.
(6
正の整数とnの最大公約数を効率よく求めるには, mをnで割ったときの余りをr
としたとき,mとnの最大公約数とnとrの最大公約数が等しいことを用いるとよい。
たとえば, 455と208 の場合,次のように余りを求める計算を3回行うことで最大公約
数13 を求めることができる。
208÷39=5 13,
455-208=2 … 39,
...
39÷13=3 ･･･ 0
このように余りを求める計算をして最大公約数を求める方法をユークリッドの互除法と
いう。
(1)
のような大きな数の場合であっても, ユークリッドの互除法を用い
20711と15151
ることで,最大公約数が『であることを比較的簡単に求めることができる。
100 以下の正の整数とn (ただし>n とする) の最大公約数をユークリッドの
互除法を用いて求めるとき, 余りを求める計算の回数が最も多く必要になるのは,
=[
m=
n="
のときである。
[23 慶応大・環境情報〕

Answer 1

✨ ベストアンサー ✨

和

たとえば89を43で割ることを考えると、
89 = 43×2 +3
43 = 3×14 +1
3 = 1×3
のようになり、3回で終わります
早めに終わるのは、商2や14が大きめだからです

89 = 43×2 +3は、
89から、割る数43のかたまりを2個分も
ごっそり取り去り、余り3しか残しません
この「2」が商です

余りが0まで減れば終わってしまうので、
割り算の回数Nをなるべく多くするには、
なるべく、割る数のかたまりを1個分ずつ
減らしていきたいのです

つまり、基本的に商は小さくしたいのです

りんご

なるほど！分かりやすく教えていただきありがとうございました！