Question

yapeiiiii

1次不定方程式で、ユークリッドの互除法の逆を利用して1つの整数解を求めた後答えを導くという問題がありますが、「ユークリッドの互除法の逆」の意味がよく分かりません。どういう定義なのでしょうか…

あと1つ気になった問題がありました
7x+5y=345
という1次不定方程式を解く問題ですが、ユークリッドの互除法で解いたところ答えがおかしくなったので解答を見たところユークリッドの互除法を用いていませんでした
ユークリッドの互除法を用いてる問題は
5x+8y=1
と言った全ての項の係数？が互いに素になっているのでユークリッドの互除法を使えるが、
上の 7x+5y=345 は5と345が互いに素ではないのでユークリッドの互除法が使えない
これはあくまで私の憶測なのですが、ユークリッドの互除法の逆と何か関係があるのかなと思いました

どちらかでも良いので教えてください🙇🏻

数学a 数a ユークリッドの互除法

Answer 1

✨ ベストアンサー ✨

さい先生

ユークリッドの互除法は、いわば2数の最大公約数を求めるために、割る数を余りで割っていく計算をしていくものでした。
この計算の逆を辿って、「1」をもとの2数を使って表すことで、1次不定方程式の整数解の1つを求めることができます。
このことからもわかるように、1次不定方程式の整数解の1つを求める際にユークリッドの互除法が使えるのは、
右辺が「1」になっているとき、と、なります。
では、345みたいになったらどうか？
このことについては、添付の画像で説明します。

yapeiiiii

理解できました！とても分かりやすかったです有難うございました🙇‍♀️