(フェルマーの小定理)
===============================
pを素数とする。
aがpの倍数でないとき、
a^(p-1)≡1 (mod p)
===============================
【証明】
(補題)
0≦i＜p, 0≦j＜pとする。
i=j⇔ia≡ja (mod p)
(補題の証明)
⇒)i=jならばia=jaより、明らか
⇐)a(i-j)≡0 (mod p)
aはpの倍数でないから、互いに素
よって、i-jはpの倍数
-p＜i-j＜pだから、i-j=0でi=j
補題から
a,2a,…,(p-1)aをpで割った余りは異なる。
{a,2b,…(p-1)a}をpで割った余りは
{1,2,…,p-1}である。
a×2a×…×(p-1)a≡1×2×…×(p-1) (mod p)
(p-1)!×a^(p-1)≡(p-1)! (mod p)
(p-1)!とpは互いに素だから、
a^(p-1)≡1 (mod p)
【証明終】
===============================
a≡b (mod n) ⇔ ka≡kb (mod kn)
===============================
【証明】
⇒)a-b=ntだから、k(a-b)=knt
ka-kb=kntより、ka≡kb (mod kn)
⇐)ka-kb=k(a-b)=kntだから、a-b=nt
よって、a≡b (mod n)
【証明終】
【例】3^50を5で割った余り
【解】
フェルマーの小定理より、
3^4≡1 (mod 5)
3^50=(3^4)^12×3^2≡3^2≡9≡4 (mod 5)
【例】2^100を35で割った余り
【解】
x=2^100とする。
2^4≡1 (mod 5)より、
x=2^100=(2^4)^25≡1 (mod 5)
2^6≡1 (mod 7)より、
x=(2^6)^16×2^4≡2^4≡2 (mod 7)
x≡1 (mod 5)
x≡2 (mod 7)
7s≡1 (mod 5)→2s≡6→s≡3
5t≡2 (mod 7)→5t≡-5→t≡-1
よって、
x≡7×3+5×(-1)≡21-5≡16 (mod 35)
【別解】
x=2^100とする。
2^4≡1 (mod 5)、2^6≡1 (mod 35)から
2^12≡(2^4)^3≡1 (mod 5)
2^12≡(2^6)^2≡1 (mod 7)
よって、
2^12≡1 (mod 35)
したがって、
2^100≡(2^12)^8×2^4≡16 (mod 35)
【例】3^100を15で割った余り
【解】
3^100=15N+rとすると、余りrは3の倍数
3^100≡3a (mod 15)とする。
3^99≡a (mod 5)
3^4≡1 (mod 5)より、
3^99≡(3^4)^24×3^3≡27≡2 (mod 5)
よって、
3^100≡6 (mod 15)
