合同式について

合同式の問題について質問です。
A≡127^57 (mod 2173)
M≡1829^73 (mod 2173)
A=1829、M=127になったのですが合っていますか？
間違っていれば解説お願いします。

No.2 ベストアンサー 回答者： ありものがたり 回答日時： 2022/06/02 20:16

mod 2173 で

M ≡ A^73 = 127^(57×73) = 127^4161.
よって、
mod 41 で
M ≡ 127^(4161 - 40×104) = 127^1,
mod 53 で
M ≡ 127^(4161 - 52×80) = 127^1.
従って、mod 2173 で
M ≡ 127.

泥臭く計算したけど、この綺麗な結果の裏には
なんかもっと華麗な計算がありそう。

No.1 回答者： ありものがたり 回答日時： 2022/06/02 20:02

173 = 41×53

この素因数分解を見つけるのがたいへんで、
涙目になりました。
かろうじてプログラムはしなかったけれど、
百均電卓の御世話にはなりましたよ。
2173 までのエラトステネス篩も
頑張ればできなくはないけれど、
小さい素数で順に割ってみるほうが早いかな。

今回は問題の指数が小さくて
オイラーの定理が使えないので、
中国剰余定理で mod 2173 を
mod 41 と mod 53 に分解してみましょう。

まず mod 41 で、
127^57 ≡ (127 - 41×3)^(57 - φ(41))
= 4^17 = 4^(16+1) = (16^8)×4 = (256^4)×4
≡ (10^4)×4 = 40000
≡ 25,

次に mod 53 で、
127^57 ≡ (127 - 53×2)^(57 - φ(53))
= 21^5 = 441×441×21
≡ 17×17×21 = 289×21
≡ 24×21 = 504
≡ 27.

A ≡ 25 {mod 41}, A ≡ 27 {mod 53} となる A は、
A = 25 + 41p = 27 + 53q {p,qは整数} と置いて
不定方程式 41p - 53q = 2 を解けば、
ユークリッド互除法で 41×22 - 53×17 = 1 が得られることから
p = 22×2 + 53k, q = 17×2 + 41k {kは整数}.
これを A = 25 + 41p へ代入すると、
A = 25 + 41×(22×2 + 53k) = (25 + 41×22×2) + 2173k.
よって mod 2173 で、
A ≡ 25 + 41×22×2 = 1829.

ああしんど。