2^220を221で割った時の余りを求める。

221 = 13*17
　フェルマーの小定理より
　　2^12≡1 (mod 13)
　　2^16≡1 (mod 17)

　　2^12≡1⇒(2^12)^18 = 2^216≡1 (mod 13)
　　2^220 = 2^216*2^4≡2^4≡16≡3 (mod 13)
　ここからmod 17 をどう処理すればいいのかがわかりません。

No.2 ベストアンサー 回答者： mtrajcp 回答日時： 2021/05/15 06:08

2^220=2^(12*18+4)=2^4=16=3 (mod13)

2^220=2^(16*13+12)=2^12=(2^4)^3=16^3=(-1)^3=-1 (mod17)
2^220=13m+3
2^220=17n-1
17n-1=13m+3
17n-13m=4
17-13=4
17(13k+1)-13(17k+1)=4
n=13k+1
m=17k+1
2^220=17(13k+1)-1=17*13k+16
2^220=13(17k+1)+3=17*13k+16
∴
2^220=16 (mod221)

この回答へのお礼

ありがとう。よくわかりました。

お礼日時：2021/05/15 08:17

No.1 回答者： Tacosan 回答日時： 2021/05/15 00:13

mod 13 から mod 17 を計算することはできないので改めて計算すること.