■フェルマーの合同式の発見と証明

 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)

が成り立つことが示される.

===================================