合同方程式について

合同方程式について分からないことがいくつかあります。
①　ax≡b(modp) a,pが互いに素の時　なぜ答えは1つなのでしょうか。
　　出来れば証明を教えていただきたいです。

②　①で答えを求めるときに全部代入して求めるのは納得できるのですが、
　　以下の方法はどうやって思いつくのか分かりません
　　(答えを見ると納得はするのですが、どういう発想で出るのか)
　　例えば　3x≡2 (mod5)→ 6x≡4(mod5) →x≡4(mod5) のような解き方や
　　　　　 13x≡5(mod23) →26x≡10(mod23)→3x≡10(mod23)→24x≡80(mod23)
　　　　→x≡11(mod23)

③　ax≡b(modp)でa,mの最大公約数g(g>1),b/gが整数のとき、答えの個数は何個ですか。
　　出来れば証明を教えていただきたいです。

④　③のとき一回最大公約数で割り、ax/g≡b/g(modp/g)の答えを求めてmodpに戻す？
　　解法があると思うのですが、戻し方を教えていただきたいです

⑤ ax≡b(modp)でa,mの最大公約数g(g>1), b/gが整数ではないとき、なぜ答えはないのですか。
　　出来れば証明を教えていただきたいです。

長いですがよろしくお願いいたします。

質問者からの補足コメント

• a,mではなくa,pです

    補足日時：2021/12/04 18:42

• ｋをこの最大公約数3でわった商と余りをｑ、ｒとすれば　とありますが、これはmod9に戻すためですよね。

  No.3の回答に寄せられた補足コメントです。 補足日時：2021/12/06 21:34

• すいません
  結局解の個数は何個でしょうか。
  たびたびヒントを与えていただいたのですが、分かりません。

  No.2の回答に寄せられた補足コメントです。 補足日時：2021/12/06 21:40

• 若干本題からそれてしまうのですが、例えば3で割って2余る数①を、9で割ったときの余り②を考えるときに
  まず3k+2①でkを3で割った余りで分類すると②が求められるのは、なぜですか

    補足日時：2021/12/06 21:51

No.3 ベストアンサー 回答者： syotao 回答日時： 2021/12/05 17:17

6x≡3(mod9)

6と9の最大公約数3でわって
2ｘ≡1(mod3)　この解は
ｘ≡2(mod3)だから
ｘ≡3ｋ＋2　となるけどもｋをこの最大公約数3でわった商と余りを
ｑ、ｒとすればｘ＝9ｑ＋3ｒ＋2となり、9ｑ≡0(mod9)だから
ｘ≡3ｒ＋2(mod9)　ここで、ｒ＝0、1、2だから
もとの方程式の答はｘ≡2、5、8　の3つです。

6x≡4(mod9)　は6ｘ＝4＋9ｋ、4＝3(2ｘ－3ｋ)ということだが
4は3の倍数ではないので、いいかえればもとの方程式の解の存在を
仮定すると矛盾が起こるので、この方程式には解がないということです。

この回答へのお礼

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

お礼日時：2021/12/06 21:09

No.5 回答者： syotao 回答日時： 2021/12/07 14:40

例えば3で割って2余る数①を、9で割ったときの余り②を考えるときに

まず3k+2①でkを3で割った余りで分類すると②が求められるのは、なぜですか＞

まあそれはNo3の回答にもあるけど補足すると、
ある整数を9で割った余りを調べるのにその整数を
9Q＋R、0≦R＜9　の形にもっていかなくてはならない、
それで今の場合ｋ＝3ｑ＋ｒとおくことで
3k+2＝9ｑ＋(3ｒ＋2）となりｒは0,1,2のいずれかだから
0≦3ｒ＋2＜9、これはいいかえると
3k+2を9で割った余りは3ｒ＋2ということになるのです。

この回答へのお礼

ありがとうございます。

お礼日時：2021/12/09 00:49

No.4 回答者： syotao 回答日時： 2021/12/06 22:19

ｋをこの最大公約数3でわった商と余りをｑ、ｒとすれば　とありますが、これはmod9に戻すためですよね。

>

はいそのとおりです。えられた解がもとの方程式のmod9の
どの剰余類に属するかを調べています。
あとNo.2さんへの質問にも関連するが、この方程式の
mod９に関する解の数は今問題にしている最大公約数に一致します。

この回答へのお礼

ありがとうございます。

お礼日時：2021/12/06 22:53

No.2 回答者： Tacosan 回答日時： 2021/12/04 23:53

おおまかなストーリーだけ.

①: 結局はそれを示すのと同じだけど, ax ≡ ax' なら x ≡ x' を示すのが簡単かなぁ. ax ≡ ax' だから a(x-x') = pt となる整数 t があって, a と p が互いに素だから x-x' が p の倍数.

⑤: a と p の最大公約数が g だから a = a'g, p = p'g とおけて, 任意の整数 s, t に対し as + pt = g(a's + p't) だから ax を p で割った余りは g の倍数になる.

③, ④: b = b'g とおくと ax ≡ b (mod p) iff a'x ≡ b' (mod p') で後者は (mod p' で) 解を 1つしか持たない. そしてその解の 1つを x0 とおくとx0 + p'k (k は整数) で全ての解を網羅できる. これを mod p で考えれば前者の解になる. さて, 何個出てくるだろうか?

最後に ② だけど, そこに書いてあるのはおそらく発見的な手法になると思う. つまり「やってみたらうまくいった」という話. きちんとやるならユークリッドの互除法を調べるべし.

この回答へのお礼

回答ありがとうございます。
理解力がなくてすみません。
①,ax ≡ ax' なら x ≡ x' を示すとなぜ、解が1つになるのでしょうか。
⑤ax を p で割った余りは g の倍数になる理由をもう少し詳しく教えていただけないでしょうか

お礼日時：2021/12/06 21:24

No.1 回答者： Tacosan 回答日時： 2021/12/04 18:27

いくつか「出来れば証明を教えていただきたいです」って書いてあるんだけど, それは当然「自分で証明しようと思っていろいろ考えたんだけ

ど今くいかなかった」ってことだよね? では, それぞれでどう考えてどこで困った?

この回答へのお礼

①はaxをpより小さいので割ったら全部余りが違うという証明が出来ません。
③⑤は具体例だと分かりそうなのですが、文字に置くと分かりません
③6x≡3(mod9)
このとき6x=9k+3とおける(kは整数)で、x=3/2k+1/2でkは奇数なのは分かるのですが、答えの個数は分かりません

⑤6x≡4(mod9)より 6x=9k+4　x=3/2k+2/3で分母が通分できない？

お礼日時：2021/12/04 18:59