フェルマーの小定理

ｐを素数、aをｐの倍数でない自然数とするとき、

a^p-1=1 (modp)

例:ｐ=5に対して,1^4=1,2^4=1,3^4=1,4^4=1

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

p=7,a=3とします。

1,2,3,4,5,6

に３をかけて、mod7を計算すると

3,6,9,12,15,18＝3,6,2,1,4　　(mod7)

すなわち、1,2,3,4,5,6の並び替えになっている。

このことは任意のｐとｐと互いに素な任意の整数aについて成り立つ。

3,6,9,12,15,18＝3,6,2,1,4　　(mod7)

の辺々掛け算すると

3^6・6!=6! 　　(mod7)

６！は７と互いの疎なので、割り算ができて

3^6!=1 　　(mod7)

1,2,・・・,ｐ-1が0を除いた素数ｐを法とする完全剰余系＝位数p-1の乗法群を形成するという事実に依存している。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

P=1a・2a・3a・・・(p-2)a・(p-1)a=a^p-1・(p-1)!=a^p-1・(p-1)!

の順番を変えるだけで、積の値は変わらない。

したがって、P=(p-1)! (modp)

(p-1)!はｐと互いに素であるから消去できて、

a^p-1＝1 (modp)

例:ｐ=5,a=2に対して,P=2・4・6・8=2^4・4！

しかし、5を法とするＰの中の度の因数をとっても

P=2・4・1・3=4！ (mod5)

これより、2^4=1 (mod5)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝