ax＋by＝1の1つの整数解の見つけ方

質問

aとbが整数のとき
xyの方程式ax＋by＝1　の1つの整数解をみつける代数的なテクニックがありますよね

質問1　そのテクニックを教えてください

質問2　そのテクニックの適用範囲をおしえてください
　　　　　（=1　ではなく=一般の整数　でも使えるかどうか　など）

参考書の回答をみると
79x-339y=1　の１つの整数解をみつけようとしている箇所で

『339=79×4＋23　
79=23×3＋10
23=10×2＋3
10=3×3＋1

よってx＝103 y＝24　である　』

との記載がありましたが
これだけでは具体的に何をやっているのかわかりません…

回答No.1

Tacosan · ベストアンサー

ユークリッドの互除法だねぇ. 上から
23 = 339 - 4×79 を 2つ目に代入
10 = 何とか×339 - 何とか×79 を 3つ目に代入
以下省略
とやればいいだけだけど, 「よって」はちょっと雑な感じもする.

右辺は a と b の最大公約数になるので, それ以外のときは適当に何倍かしてください.

お礼

あまりの場所に連続的にいれていく形ですね
わかりました　ありがとうございました！