kanedakazuma

以下の合同式を計算したいです.

6251(mod 103)62^{51}(mod\ 103)

これは,解答では-1と合同になりますが,自分が計算すると1と合同になってしまいます.

また,これにはフェルマーの小定理は適用できますか?

回答 1件

ベストアンサー

DoubleExpYui

以下103を法とする。


623≡89≡−1462^3\equiv89\equiv-14より

6251=623×17≡(−14)1762^{51}=62^{3\times17}\equiv(-14)^{17}


(−14)2≡−10(-14)^2\equiv-10より

(−14)17=(−14)2×8+1≡(−10)8×(−14)(-14)^{17}=(-14)^{2\times8+1}\equiv(-10)^8\times(-14)


(−10)2≡−3(-10)^2\equiv-3より

(−10)8=(−10)2×4≡(−3)4(-10)^8=(-10)^{2\times4}\equiv(-3)^4


以上より

6251≡(−3)4×(−14)=−1134=103×(−11)−1≡−162^{51}\equiv(-3)^4\times(-14)=-1134=103\times(-11)-1\equiv-1


フェルマーの小定理使うならp=103p=103として62102≡162^{102}\equiv1だけども、625162^{51}が±1\pm1のどちらかまでは判断できるかな?すぐには思いつかないです



  • 解答していただきありがとうございます.

関連する質問

質問する