べき剰余の問題

質問

何回解いてもちがった答えが出てきてしまいます。
x ≡ 351^109 (mod 667 )　　
途中過程も書いていただくと幸いです。よろしくお願いします。

回答No.3

arrysthmia

188 に賛成。

667 = 23×29 だから、
mod 23 と mod 29 で考える。

351 ≡ 6 mod 23 より、
フェルマーの小定理によって、
351~109 ≡ 6~(22×5-1) ≡ 1/6 ≡ (1+23)/6 = 4 mod 23。

同様に、
351 ≡ 3 mod 29 より、
351~109 ≡ 3~(28×4-3) ≡ 1/3~3 mod 29。
1/3 ≡ (1+29)/3 = 10 mod 29 より、
351~109 ≡ 10~3 = 1000 ≡ 14 mod 29。

気合で、29×4-23×5 = 1
という関係を見つけると、
29×40-23×50 = 14-4 から
4-23×50 = 14-29×40 = -1146 が分かる。

よって、351~109 ≡ -1146 ≡ 188 mod 23×29。

お礼

わかりやすくて詳しい解説ありがとうございます。１８８であってました。ありがとうございました。

回答No.2

banakona

あまり自信ないけど・・・

１０９＝１１０１１０１（2進数）だから
３５１^109＝３５１^64×３５１^32×３５１^8×３５１^4×３５１

３５１^4＝（３５１^2）^2≡４７３^2≡２８４（mod６６７）
３５１^8＝（３５１^4）^2≡２８４^2≡６１６
３５１^32＝（３５１^16）^2≡（（３５１^8）^2）^2≡（６１６^2）^2≡６００^2≡４８７
３５１^64＝（３５１^32）^2≡４８７^2≡３８４

３５１^109≡３８４×４８７×６１６×２８４×３５１
　　≡３８４×４８７×６１６×(３０１)
　　≡３８４×４８７×（６５７）
　　≡３８４×（４６６）
　　≡１８８
で、あってませんか？

お礼

とてもわかりやすい解説ありがとうございます。１８８で納得できました。

回答No.1

f1818

うーーむ・・・・・・宇宙の終わりははたしてもうすこし計算さしてください。