【最大10000ポイント】当たる!!質問投稿キャンペーン!

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
となっています。
この式はどこからでてきたのでしょうか?

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

このQ&Aに関連する最新のQ&A

A 回答 (4件)

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



79x-339y=1 → 79*(x-4y)-23y=1。x-4y=a ‥‥(1)とすると、79a-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.
    • good
    • 0

わかりやすいように重要な数にカッコを付けてみます。


[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]

カッコ付きの数を文字のように考えるとわかりやすいかな?
    • good
    • 0
この回答へのお礼

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

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

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

お礼日時:2010/02/05 00:32

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

というわけです。
伝わりますか?
    • good
    • 0

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



直前の式からです。
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング