数学の質問＆宿題○投げ場コミュの合同式の基本的な質問

ac≡bc (mod p)でpとcが互いに素
ならば、a≡b (mod p)　

ですが、ｃで割ることの出来ない場合に自信が無いのですが、

たとえば、出来る場合の例として、
6≡15(mod9)
これは３で割って
2≡5(mod9)
と2と9が互いに素なので、できますよね？

ところが、
6=10(mod4)
だと２で割って、
3≡5(mod4)
とは、２と４が互いに素ではないため、２で割ることは、できないということですか？

この辺りが自信ないので、そうなのかそうでないのかを教えて下さい。

コメント(3)

最初
全て
最新の40件

[2] mixiユーザー 04月27日 11:21

ac≡bc (mod p)すなわち
ac-bc=pkのとき
pとcが互いに素であるならば、kがcの倍数であることがいえるので
a-b=pk' (k=ck')すなわちa≡b (mod p)が成立します。

一方、pとcが互いに素でない場合
kがcの倍数とは限らないので
a-b=pk'が必ずしも成立するとはいえません。

必ずしもいえないというだけで
たとえば
　14≡2 (mod 6)
　7≡1　(mod 6)
の場合のように、2と6が互いに素でないのに2で割っても
成立することもあります。

＞6=10(mod4)が成立するのに、3≡5(mod4)が成立しない
ことの本質は
2と4が互いに素でないことではなく、
10と6の差を4で割ったときの商が2で割り切れないことにあると思います。

以上まとめますと
ac≡bc (mod p)かつa≡b (mod p)が成立する必要十分条件は
ac-bcをpで割ったときの商がcで割り切れること　…*
であると思います。
pとcが互いに素というのは*の十分条件ということになると思います。

[3] mixiユーザー 04月27日 14:13

なるほど。そういうことでしたか。ありがとうございました。

ログインすると、みんなのコメントがもっと見れるよ