現代社会において，インターネット通信やクレジットカード決済の安全性・信頼性を担保しているものは巨大な素数の存在です．巨大な素数をｐ，ｑとすると，ｐとｑを掛け合わせてｎ＝ｐｑを得るの易しいが，ｎをｐとｑに素因数分解するのは非常に困難である（不可能に近い）という原理に基づいています．ここでは素数性の判定法の基本となるフェルマーの小定理について紹介します．

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

【１】フェルマーの小定理

ｐが素数で，ａがｐの倍数でないとき，フェルマーの小定理

　　ａ^p-1＝１　　（ｍｏｄ　ｐ）

が成り立ちます．たとえば，ｐ＝１７，ａ＝３の場合

　　３^16＝２５３２１６０・１７＋１

この定理は両辺にａを乗じた形で表されることもありますが，その場合，ａがｐの倍数でないという条件は不要です．すなわち，

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

　　ａ^p＝ａ　　（ｍｏｄ　ｐ）

が成り立つ．

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

【２】古代ギリシャ　

　古代ギリシャ人はｎ＝２，３，５，７のとき，２^n−１が素数になることを知っていました．ｎが素数でないときには素数を表さないことは明らかですから，それとは逆に，すべての素数に対して，２^n−１は素数になると考えていたようです．ｎが素数であることは２^n−１が素数であるための必要条件です．しかし，逆の十分性は成り立ちません．

　　２^2−１＝３　　（素数）

　　２^3−１＝７　　（素数）

　　２^5−１＝３１　　（素数）

　　２^7−１＝１２７　　（素数）

　　２^11−１＝２０４７＝２３・８９　　（非素数）

　　２^13−１＝８１９１　　（素数）

フェルマーの定理の応用性は高く，

　　２^4−１＝１５　　（非素数）

　　２^6−１＝６３　　（非素数）

　　２^8−１＝２５５　　（非素数）

　　２^9−１＝５１１＝７・７３　　（非素数）

　　２^12−１＝１０２３＝３・３４１　　（非素数）

などはすぐ判定できます．

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