pが素数のとき,すべての整数aに対して,フェルマーの小定理
a^p=a (mod p)
が成り立つ.
[参]TSマイケル「離散数学パズルの冒険」青土社
===================================
【1】発見
フェルマーは
[1]1^3-1,2^3-2,3^3-3,4^3-4,5^3-5,・・・はすべて3で割り切れる
[2]1^5-1,2^5-2,3^5-3,4^5-4,5^5-5,・・・はすべて5で割り切れる
[3]1^7-1,2^7-2,3^7-3,4^7-4,5^7-5,・・・はすべて7で割り切れる
という整除性に気づいた.
しかし,2^9-2=510は9で割り切れないので,このパターンはベキが9のとき成立しない.
[4]1^11-1,2^11-2,3^11-3,4^11-4,5^11-5,・・・はすべて11で割り切れる
[5]1^13-1,2^13-2,3^13-3,4^13-4,5^13-5,・・・はすべて13で割り切れる
ことから,フェルマーはベキが素数のときこのパターンが成立することを発見した.
すなわち,pが素数のとき
[6]1^p-1,2^p-2,3^p-3,4^p-4,5^p-5,・・・はすべてpで割り切れる
===================================
【2】証明
2項定理
(x+1)^p=x^p+(p,1)x^(p-1)+(p,2)x^(p-2)+・・・+(p,p-12)x+1
連続するk個の自然数の積
n(n-1)・・・(n-k+1)
がk!で割り切れることは
n(n-1)・・・(n-k+1)/k!
が整数であることがいえればよいのであるが,
n(n-1)・・・(n-k+1)/k!=nCk
すなわち,組み合わせの総数=整数であるから明らかであろう.
したがって,
p(p-1)・・・(p-k+1)/k!=pCk
k=1~p-1に対して,pCk=(p,k)はpで割り切れるから,
(x+1)^p=x^p+1 (mod p)
[1]x=1とおくと,
2^p=2 (mod p)
[2]x=2とおくと,
3^p=2^p+1=3 (mod p)
[3]以下,芋づる式に
a^p=(a-1)^p+1=a (mod p)
が成り立つことが示される.
===================================