重要なお知らせ

「教えて! goo」は2025年9月17日(水)をもちまして、サービスを終了いたします。詳細はこちら>

電子書籍の厳選無料作品が豊富!

109x-29y=1 の整数解の1つを求めたいのですが、何か賢い方法はあるでしょうか。

ユークリッドの互除法を利用すれば (x,y)=(4,15) が1つの整数解になることがわかりますが、
互除法を使わずに解に迫る方法はありますか?

109の倍数:109 218 327 436 545 654 763 872 981 1090 …
29の倍数:29 58 87 116 145 174 203 232 261 290 …

A 回答 (11件中11~11件)

カンで見つけるのが早いっちゃ早いかな。


解を見つけるための操作手順としては、
事実上ユークリッド互除法でしかないものを
別の方法であるかのように書いて見せる方法は
いくつか知られている。

109x - 29y = 1 を mod 29 へ移行して
22x ≡ 1 (mod 29) から 22x = 1 + 29n.
これを mod 22 へ移行して
0 ≡ 1 + 7n (mod 22) から 22m = 1 + 7n.
とやってくとか、

109/29 の連分数展開を使ったり、
その連分数展開に行列積を使う方法とか。

どれも皆、ユークリッド互除法の計算手段
なんだけどね。
    • good
    • 1
この回答へのお礼

回答ありがとうございます。

★22x ≡ 1 (mod 29)から、候補としてx=4は思いつきやすいかもしれません。ところで、ここでの★はxが満たすべき必要条件であるため、x=4が解とは限らない(たまたまx=4が解になっているだけ)という解釈であっているでしょうか。

22x ≡ 1 (mod 29) や 22m = 1 + 7n から x や m や n の検討をつけることは、勘が働きやすいです。

これなら、ユークリッドの互除法を使わなくとも整数解が見つけられるかもしれません…というのは未熟で

>事実上ユークリッド互除法でしかないものを別の方法であるかのように書いて見せる

なのですか?

お礼日時:2024/10/14 19:01

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

今、見られている記事はコレ!