ax+by=1（x,yは整数）の解法について質問です。

質問

ax+by=1（x,yは整数）の解法について質問です。

79x-339y=1(x,yは整数)
という問題があったのですが、解答で、

339=4*79+23
79=3*23+10
23=2*10+3
10=3*3+1
として、
1=10-3*3
=10-3*(23-2*10)
ここまでは今までやってきたことの
逆の操作のをしていっているのだと
思うのですが、この次で、

1=7*10-3*23
となっています。
この式はどこからでてきたのでしょうか？

解説をいただけるとうれしいです。

回答No.4

mister_moonlight · ベストアンサー

その解答の意味を数式で表すと、以下の通り。

79x-339y＝1　→　79*（x-4y）-23y＝1。x-4y＝a ‥‥(1)とすると、７9a－23y＝1。
23*（3a-y）+10*a＝1　であるから、3a-y＝b　‥‥(2)とすると、23b+10a＝1。
10*（a+2b）＋3b＝1 　であるから、a+2b＝c　‥‥(3)とすると、10c＋3b＝1より、b＝（1-10c）/3＝-3c＋（1-c）/3。
bとcは整数から、mを整数として、1-c＝3m、b＝10m-3。
よって、(3)から、a＝7-23m、(2)から　y＝24-79m。(1)から、x＝103-339m。
よって、79x-339y＝79*（103-339m）-339*（24-79m）＝1.

回答No.3

felicior

わかりやすいように重要な数にカッコを付けてみます。
[339]=4*[79]+[23]
[79]=3*[23]+[10]
[23]=2*[10]+[3]
[10]=3*[3]+[1]

そしてこれらを移項してみます。
[23]=[339]-4*[79]
[10]=[79]-3*[23]
[3]=[23]-2*[10]
[1]=[10]-3*[3]
この一番下の式は、1が10と3の倍数に分解できることを表しています。
その上の式は3を23と10の倍数に、その上は10を79と23の倍数に、
一番上は23を339と79の倍数に分解できることを表していますので、
どんどん代入していけば1が339と79の倍数に分解できることになります。

この仕組みが理解できていれば、カッコの数は残すように気をつけながら
分配法則をしていけばうまくいくことがわかります。
[1]=[10]-3*[3]
=[10]-3*([23]-2*[10])
=7*[10]-3*[23]

カッコ付きの数を文字のように考えるとわかりやすいかな？

お礼

ありがとうございました。

質問は寝ぼけてました
あれは、ただ上の式からの変形でした。

ただ、分解の仕方が良くわからなかったので、
非常に参考になりました。

回答No.2

hanabutako

10-3*(23-2*10)
= 10 - 3*23 - 3*(-2*10)
= 10 - 3*23 + 6*10
= (1+6)*10 - 3*23
= 7*10 - 3*23

というわけです。
伝わりますか？

回答No.1

koko_u_u

>この式はどこからでてきたのでしょうか？

直前の式からです。