このサイトはお使いのブラウザでは正常に動作しません。Google Chromeなど、別のブラウザを使用してください。
一次不定方程式をmodで解く場合
いつもお世話になっております。
92x+197y=10という不定方程式を満たす整数の組を求める問題についてです。
特殊解を見つけて解く解き方はわかったのですが、これを合同式を使って解く
解き方がわかりません。
197y≡10 (mod92)
13y≡10 (mod92)
くらいまでで、そこからどうすればいいかわかりません。
すみませんが教えていただければと思います。
回答
こんにちは。私は夜11時閉店なもので、翌日になりました。
合同式で解くときは、最終目的としてay≡apという式をがんばって作り出して(!)、両辺をaで割って(aと92は互いに素)y≡pとしますよね。
92と197みたいに大きな嫌な数(?)ではやりにくいですが。
以下、mod92は省略します。
92x+197y=10…(*)
92x+197y≡10
197y≡10
ここで(92×2)y≡0を上の式から引いて
13y≡10…①
この後は試行錯誤かもしれません。きちんとしたアルゴリズムがあるのかどうか知りません。
①に92y≡0をたすと、105y≡10…②
①に8をかけて、104y≡80…③
②ー①から y≡-70≡22
これよりy=92k+22
これを(*)に代入してxについて解けばx=-197k-47
この手の問題の答はいろいろな表現があるので、これは1例です。
92yを足したり、8をかけたりというのは試行錯誤です。
とりあえずこれで大丈夫ですか?
これを読んだら、わかったとか、まだこのへんがわからないとか、コメント欄に返事を書いてください。それがないと、書いたのに読まれたのかどうかも、書いたものが役に立ったのかもわかりません。よろしく。
お忙しい中、詳しい解説ありがとうございます!よくわかりました!自分なりに試行錯誤してみたもののなかなかy≡~の形にたどり着かず、困っていたので助かりました。今後もまたよろしくお願いします。
お役にたてたのなら良かったです。またどうぞ。