不定1次方程式

19x+29y=450
を満たす整数解をもとめるにはどうしたらよいでしょうか？
19x+29y=1の一般解x=29k-3、y=-19k+2は利用できますか？

No.4 ベストアンサー 回答者： スチールウール 回答日時： 2020/01/13 22:29

例えばですが、19+29 = 48, 450 = 48*9 + 18なのでもう少し攻めて

x = p+10, y=q+9とすれば
19x+29y = 19(p+10) + 29(q+9) = 19p + 29q + 451 = 450
19p + 29q = -1
あとは=1で求めた特殊解(-3,2)を-1倍して
19(3) + 29(-2) = -1
あとはp,qを求めれば一般解が求まりますし、特殊解だけで良いなら、(p,q)=(3,-2)として
(x,y) = (p+10,q+9) = (3+10,-2+9) = (13,7)が求まります

とりあえず、x=p+a, y=q+bみたいにして右辺の数を減らすのが一つの手段だとは思います

この回答へのお礼

変数変換をして右辺の数を小さくすることや、そして48というキーナンバーを巧みに使って変数変換を行うことは、初等的ではあっても、すごく上手い方法だと思いました。こんなことがスラスラできるように頭が回転できるようになりたいなぁ。

お礼日時：2020/01/20 18:09

No.5 回答者： ありものがたり 回答日時： 2020/01/13 22:46

＞この(x,y)=(13,7)を見つける体系的または巧い方法はあるでしょうか。

定数項(の絶対値)が小さいほうが体裁がいいと思うのであれば、
x=29k-1350
y=-19k+900
を見つけた後で k をずらせばよいのでは？
29 と -1350 の符号
-19 と 900 の符号がどちらも異なることから、
ｋ を k+(正の定数) で置き換えればどちらの定数項も小さくなることが判ります。
x≒0, y≒0 を解いて適当な (正の定数) を見つければよいです。
そういう体裁上の問題は、解が得られてからで遅くないと思います。

この回答へのお礼

回答ありがとうございます。
定数項の絶対値が大きいことは、確かに体裁上の問題ですね。

お礼日時：2020/01/20 18:04

No.3 回答者： ありものがたり 回答日時： 2020/01/13 20:48

利用できます。

式の両辺を450倍すればよいです。
式の係数 19,29,450 の個性を使って、冴えた解法で答えを見つけることもできますが、
あなたの解法は、互いに素な整数 a, b と任意の整数 c に対する ax + by = c の
一般解法を与えますから、意義が大きいと思います。

この回答へのお礼

x=29k-1350
y=-19k+900
が一般解になることは理解できるのですが、この一般解と同値な表現として(k=47の場合にみつかる特殊解を利用して)
x=29k+13
y=-19k+7
とできます。この(x,y)=(13,7)を見つける体系的または巧い方法はあるでしょうか。

お礼日時：2020/01/13 21:57

No.2 回答者： konjii 回答日時： 2020/01/13 15:47

手順は、教科書通り19x+29y=1の解の一つを求めて(－３,２)、

19x+29y=1・・①
19*(-3)+29*(2)=1・・②
①－②は
１９（ｘ+3）＋２９（ｙ-2）＝０
１９（ｘ+3）＝２９（-y+2）、１９と２９は互いに素なので
ｘ+3＝２９ｋ・・ｘ＝２９ｋ-3
ーｙ+2＝１９ｋ・・ｙ＝－１９ｋ+2

19x+29y=1の一般解x=29k-3、y=-19k+2はOK

この回答へのお礼

この特殊解(x,y)=(-3,2)を450倍して，(x,y)=(-1350,900)が19x+29y=450の特殊解であることはわかるのですが、もっと絶対値が小さい特殊解を探す方法はないでしょうか？

お礼日時：2020/01/13 21:50

No.1 回答者： スチールウール 回答日時： 2020/01/13 14:50

19x+29y=1の解の一つを求めて(26,-17)、それを450倍して元の式と引き算するのが一つ

19x +29y = 450
19(26*450) + 29(-17*450) = 450

でも、そんなのするよりは単純にx=-1, y=1入れたら10になるので、その45倍する方が楽
19x +29y = 450
19(-45) + 29(45) = 450
19(x+45) + 29(y-45) =0

あとは=1の時の一般解求められるようですので省略で
x = 29k-45
y= -19k+45

この回答へのお礼

なるほど！　19x+29y=10　を利用する方法は考えつきませんでした。

>19x+29y=1の解の一つを求めて(26,-17)、それを450倍して
のところの考えはあったのですがそうすると、
19・11700+29・(-7650)=450
となって、特殊解がものすごく大きな数になっていまうと思うんです。
もっと小さな特殊解を求める方法はないでしょうか？

19x+29y=10の特殊解を求めて、それを45倍する方法もその１つだと思いますが。

お礼日時：2020/01/13 21:48