Question

④

ユークリッドの互除法をわかりやすく教えてほしいです。

Answer 1

✨ ベストアンサー ✨

一輝

（基礎）ユークリッドの互助法

2つの自然数 a、bについて
aをbで割ったときの余りをrとする時、最大公約数を求める計算方法です。

例題 247と221の最大公約数を求めよの場合
①247（a）を221(b)で割ると余りは26(r)になる
②221（b）を26（r）で割ると余りは13（新しいr）
③26（旧r）を13（新r）で割ると余りは0になったので計算終了
したがって247と221の最大公約数は13である

練習にどうぞ
(1)323と289
(2)551と437
(3)275と127

一輝

誤字がありました

互助法ではなく互除法です

④

ユークリッドの互除法じゃなかったみたいです。勘違いしてました。
四角で囲っている部分がよく分からないです。

一輝

一次不定方程式の互除法ですか自分も余り練習していないので分かりにくかったらごめんなさい

やり方は紙に書いてある通りです

例えば方程式 41x+19y=1を満たす一組を見つける場合

まずは41と19を互除法をします。
41=19×2＋3:①
19=3×6+1:②
①から3=41－19×2：①ダッシュ
1=19－3×6：②ダッシュ
②ダッシュを①ダッシュに代入すると1=19－（41－19×2）×6
よって41×－6+19×13=1
上記からx=－6、y=13は一組である

④

ありがとうございます。