ユークリッドの互除法 添付についてですが、g(24337, 158)=g(158, 5)=1 という

ユークリッドの互除法
添付についてですが、g(24337, 158)=g(158, 5)=1
というのはどうやって求めているのでしょうか？

質問者からの補足コメント

• 問題です

  
    補足日時：2022/10/24 14:46

No.2 ベストアンサー 回答者： tknakamuri 回答日時： 2022/10/24 17:09

割る数、余りをスライドさせてゆくだけなんだが

教科書にも載ってるよね?

24337÷158=154 あまり5
158÷5=31 あまり3
5÷3=1あまり2
3÷2=1あまり1
2÷1=2あまり0 → 最大公約数 1(あまり0の時の割る数)

割られる数と割る数の最大公約数は
最後まで変わらないから

158と5の段階で
最大公約数が1だとわかるので
打ちきっているのでしょうね。

No.1 回答者： mtrajcp 回答日時： 2022/10/24 15:41

24337を158で割ると商は154余りは5だから

24337=158*154+5
24337-158*154=5…(1)
だから
158と24337の最大公約数g(24337,158)=dとすると
158=ad
24337=bd
となる整数a,bがある
これを(1)に代入すると
bd-154ad=5
(b-154a)d=5
だから
dは5の約数で
dは158の約数だから
dは158と5の公約数だから
dは158と5の最大公約数g(158,5)の約数
158と5は互いに素だから
g(158,5)=1
dはg(158,5)=1の約数だから
d=g(158,5)=1
g(24337,158)=dだから
∴
g(24337,158)=g(158,5)=1