Question

まゆ

13x+8y=7 の整数解を全て求めよ。という問題で、
ユークリッドの互除法を用いて特殊解を求めると(x,y)=(56,-21) になります。でも解説では、x=3,y=4を使って解いてます。これはどうやって求めてるんですか？

正双
①
(2) 13+8y=7 ...... ①
x=3, y=-4は、 ① の整数解の1つである。
よって153 13・3+8・(-4)=7
*****
①-② から
13(x-3)+8(y+4)=0.
3

Answer 1

✨ ベストアンサー ✨

𓆡

計算してみたらたまたま合ってただけだと思います。
あと(56,-21)は特殊解ではないと思います。
x≡y(mod7)であるから、これを満たすような値を入れてけばいずれは合います。例えば(-45,74)なども特殊解です。

まゆ

56じゃなくて(35,-21) でした！
解説には一個しか回答がないのですが、別の特殊解から出た答えでは罰になるんですか？

まゆ

追記:特殊解はなんとなく入れてみて、あってたら使うって感じなんですか？

𓆡

正直、その場の判断としか言いようがないと思います…
今回の場合、早いのは値を入れていく方法ですが、別の問題で最小の特殊解の組み合わせが(100,101)みたいなのがでたらまず手計算では終わりきらないです。なので、modで何となくの当たりをつけてから2,3回試してみて見つかったらラッキー。ダメだったらユークリッドの互除法を用いる。これが一番賢明だと思います。軽いギャンブルですよ

Answer 2

こう

13X+8y=7をみたすような整数は多くみつかるので、そのうちの代表となるxとyの値を、元の式に代入して求めます。いかがでしょうか…