合同式がわかりません

合同式について

473^5 ≡ 3^5 ≡ 3^3 × 3^2 (mod5)

ここで
3^3 ≡ 27 ≡ 2 (mod5)
3^2 ≡ 9 ≡ 4 (mod5) より

473^5 ≡ 2×4 ≡ 8 ≡ 3 (mod5)

よって473^5を5で割った余りは3である


と書かれているのですが
理解できない部分があります。

a≡b (mod n), c≡d (mod n) のとき ac≡ bd (mod n)
という公式を使って
(3^3)*(3^2) ≡ 2*4 (mod 5)
となる。

というのは教えてもらって理解できたのですが

その後
473^5 ≡ 2×4 ≡ 3 (mod5)

このような形にしていいのは何故なのでしょうか

くだらない質問かもしれませんが
よろしくお願いします。

No.4 ベストアンサー 回答者： alice_44 回答日時： 2013/10/02 19:37

←A No.2 補足

そこですか！

合同について、一般に、
A≡B (mod n) かつ B≡C (mod n) であれば、
A≡C (mod n) は成り立ちます。

これは、合同の定義が
A≡B (mod n)　⇔　(A-B=nk となる整数 k が在ること)
であるために、
A-B=nk となる整数 k が在り
B-C=nj となる整数 j が在るならば、
A-C=n(k+j) であって k+j が整数だからです。

これを使って、
473^5 ≡ 3^3 × 3^2 (mod 5) と
3^3 × 3^2 ≡ 2*4 (mod 5) から、
473^5 ≡ 2×4 (mod5)。

この話は、本では
＞ a≡b (mod n), c≡d (mod n) のとき ac≡ bd (mod n)
よりも前に出てくるはずなんですが。

この回答へのお礼

alice_44さんありがとうございます。

自分がメインで使っている参考書がかなり初心者向けのものため
、その部分の説明が省略されていました。



この話は、本では
＞ a≡b (mod n), c≡d (mod n) のとき ac≡ bd (mod n)
よりも前に出てくるはずなんですが。


と書かれているのを見て、全く使っていなかった太めの参考書を見た所、aiceさんの書かれている事と同じことが書かれていました。

もう少し調べてから質問するべきでした。
すみません。


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

お礼日時：2013/10/02 20:51

No.3 回答者： kacchann 回答日時： 2013/10/02 02:37

＞という事をこれは表しているのでしょうか

そうだよ。
合同式の記号「≡」
は
「余りについての等号記号「＝」そのもの」
だよ。(だって「あまりが等しい」ことを意味してるんだから)

だから「＝」と同じように扱えばいいんだよ。
---

つまり…


473^5 ≡ 3^5 ≡ 3^3 × 3^2 (mod5)…(1)
これはいいよね。

公式を使って
(3^3)*(3^2) ≡ 2*4 (mod 5)…(2)

これもいいよね。

あと、常識的(?)に
2*4≡8≡3(mod 5)…(3)

これもいいよね。
(1)、(2)、(3)をつなげれば

473^5
≡ 3^5
≡ 3^3 × 3^2
≡2*4
≡8
≡3(mod5)


つまり合同記号をつかった"等式"は、
単に「あまりについての等式そのもの」だよ。

この回答への補足

ありがとうございます。
alice_44 さんへの補足のコピーになってしまうのですがすみません。


473^5 ≡ 3^3 × 3^2(mod 5)
を
473^5 ≡ 2×4 (mod5)
と置き換えるときには
何か公式を使っているわけではなく

(3^3)*(3^2)　と　2*4 が5を法として合同だから
(3^3)*(3^2)と5を法として合同な473^5は
2*4とも5を法として合同である　

と考えることが出来ることから、というのが理由なのでしょうか？

補足日時：2013/10/02 07:24

No.2 回答者： alice_44 回答日時： 2013/10/01 22:20

回答中での問いに答えていないし、

貴方がどこを解らないのか、その補足では
さっぱり判らないのですが…

補足後半に書かれた式の理解は、
それでよいと思います。

結局、何が質問したかったのでしょうね？

この回答への補足

合同式というものがあまり理解できていないのと
自分の頭の中が整理できていなく
回答の中の質問の意味がよくわかっていませんでした。
自分の中では答えたつもりだったのですが・・・

「
(3^3)*(3^2) ≡ 2*4 (mod 5)　と変形できたとき

473^5 ≡ 3^3 × 3^2(mod 5)
を
473^5 ≡ 2×4 (mod5)
と置き換えることが出来る　」

というのは

(3^3)*(3^2)　と　2*4 が5を法として合同だから
(3^3)*(3^2)と5を法として合同な473^5は
2*4とも5を法として合同である　

と考えることが出来ることから

473^5 ≡ 3^3 × 3^2(mod 5)
を
473^5 ≡ 2×4 (mod5)
と置き換えることが出来る


ということなのかどうかについて知りたいと思っています。
この変形にも何か公式が使われているのではないかと思い
質問させてもらいました。

補足日時：2013/10/02 07:16

No.1 回答者： alice_44 回答日時： 2013/10/01 18:45

3^5 ≡ 3^3 × 3^2 (mod5)　と

3^3 ≡ 27 ≡ 2 (mod5)　と
3^2 ≡ 9 ≡ 4 (mod5) と
3^3 × 3^2 ≡ 2*4 (mod 5)　と
が解ったとすると、
3^5 ≡ 2×4 (mod5)　まで来たはずだけど、

あと解らないのは、
2×4 ≡ 3 (mod5)　ですか？
473^5 ≡ 3^5 (mod5)　の方ですか？

2×4 = 8 = 3 + 5×1 ≡ 3 (mod5)　は、
mod の定義そのものみたいな話。

473^5 ≡ 3^5 (mod5)　は、
473 = 3 + 5×94 ≡ 3 (mod5)　より、
貴方が教わったという
a≡b (mod n), c≡d (mod n) のとき ac≡ bd (mod n)　を
繰り返し使って、
473^2 = 473 × 473 ≡ 3 × 3 = 3^2 (mod5)、
473^4 = 473^2 × 473^2 ≡ 3^2 × 3^2 = 3^4 (mod5)、
473^5 = 473^4 × 473 ≡ 3^4 × 3 = 3^5 (mod5)
と導けます。

この回答への補足

ありがとうございます。
私がわからないのは

473^5 ≡ 3^5 ≡ 3^3 × 3^2 (mod5)

ここで
3^3 ≡ 27 ≡ 2 (mod5)
3^2 ≡ 9 ≡ 4 (mod5) より

473^5 ≡ 2×4 ≡ 8 ≡ 3 (mod5)

の
473^5 ≡ 2×4 ≡ 8 ≡ 3 (mod5)
この部分です。

公式を使って
(3^3)*(3^2) ≡ 2*4 (mod 5)を導くと

(3^3)*(3^2) ≡ 2*4 (mod 5)だから
473^5 ≡ 3^5 の
3^5の部分を2*4と置き換えて
473^5 ≡ 2×4 (mod5)
と考えることが出来て
2×4=8を5で割ると余り3だから
473^5も5で割ると3で余る

という事をこれは表しているのでしょうか？

補足日時：2013/10/01 19:17