ｐが素数のとき，すべての整数ａに対して，フェルマーの小定理

　　ａ^p＝ａ　　（ｍｏｄ　ｐ）

が成り立つ．

　　［参］ＴＳマイケル「離散数学パズルの冒険」青土社

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

【１】発見

　フェルマーは

［１］１^3－１，２^3－２，３^3－３，４^3－４，５^3－５，・・・はすべて３で割り切れる

［２］１^5－１，２^5－２，３^5－３，４^5－４，５^5－５，・・・はすべて５で割り切れる

［３］１^7－１，２^7－２，３^7－３，４^7－４，５^7－５，・・・はすべて７で割り切れる

という整除性に気づいた．

　しかし，２^9－２＝５１０は９で割り切れないので，このパターンはベキが９のとき成立しない．

［４］１^11－１，２^11－２，３^11－３，４^11－４，５^11－５，・・・はすべて１１で割り切れる

［５］１^13－１，２^13－２，３^13－３，４^13－４，５^13－５，・・・はすべて１３で割り切れる

ことから，フェルマーはベキが素数のときこのパターンが成立することを発見した．

　すなわち，ｐが素数のとき

［６］１^p－１，２^p－２，３^p－３，４^p－４，５^p－５，・・・はすべてｐで割り切れる

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

【２】証明

　２項定理

　　（ｘ＋１）^p＝ｘ^p＋（ｐ，１）ｘ^(p-1)＋（ｐ，２）ｘ^(p-2)＋・・・＋（ｐ，ｐ－１２）ｘ＋１

　連続するｋ個の自然数の積

　　ｎ（ｎ－１）・・・（ｎ－ｋ＋１）

がｋ！で割り切れることは

　　ｎ（ｎ－１）・・・（ｎ－ｋ＋１）／ｋ！

が整数であることがいえればよいのであるが，

　　ｎ（ｎ－１）・・・（ｎ－ｋ＋１）／ｋ！＝nＣk

すなわち，組み合わせの総数＝整数であるから明らかであろう．

　したがって，

　　ｐ（ｐ－１）・・・（ｐ－ｋ＋１）／ｋ！＝pＣk

ｋ＝１～ｐ－１に対して，pＣk＝（ｐ，ｋ）はｐで割り切れるから，

　　（ｘ＋１）^p＝ｘ^p＋１　　（ｍｏｄ　ｐ）

［１］ｘ＝１とおくと，

　　２^p＝２　　（ｍｏｄ　ｐ）

［２］ｘ＝２とおくと，

　　３^p＝２^p＋１＝３　　（ｍｏｄ　ｐ）

［３］以下，芋づる式に　　

　　ａ^p＝（ａ－１）^p＋１＝ａ　　（ｍｏｄ　ｐ）

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

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