■フェルマーの合同式の発見と証明(その2)

 pが素数で,aがpの倍数でないとき,フェルマーの小定理

  a^p-1=1  (mod p)

が成り立つ.

 この定理は両辺にaを乗じた形で表されることもあるが,その場合,aがpの倍数でないという条件は不要となる.すなわち,

 pが素数のとき,すべての整数aに対して,フェルマーの小定理

  a^p=a  (mod p)

が成り立つ.

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

【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−1)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)

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

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