Fermatの小定理
素数を法にした計算では、指数を小さくするのが勝ち筋です。 Fermatの小定理はその最短ルートです。
定理（条件を明確に）
\(p\) を素数、\(a\) を整数とすると \(a^p\equiv a\pmod p\) が成り立ちます。
特に \(p\nmid a\)（つまり \(\gcd(a,p)=1\)）なら \(a^{p-1}\equiv1\pmod p\) です。
実戦では後者をよく使います。 ただし法が素数であることは必須です。
証明
証明を見る
\(p\) を素数、\(p\nmid a\) とします。 数列 \(1,2,\dots,p-1\) をそれぞれ \(a\) 倍した \(a,2a,\dots,(p-1)a\) を \(\bmod p\) で見ます。
もし \(ia\equiv ja\pmod p\) なら \(p\mid a(i-j)\) です。 \(p\nmid a\) なので \(p\mid(i-j)\)、よって \(i=j\) です。 したがって \(a,2a,\dots,(p-1)a\) は \(1,2,\dots,p-1\) の並べ替えです。
ここで \((p-1)!\) は \(p\) の倍数でないので約分でき、 \(a^{p-1}\equiv1\pmod p\) を得ます。 最後に両辺へ \(a\) を掛けると \(a^p\equiv a\pmod p\) です。
例題
例1：巨大指数の余り
\(2^{1000}\) を \(13\) で割った余りを求めます。
解答を見る
\(2^{12}\equiv1\pmod{13}\) です。 \(1000=12\cdot83+4\) なので \(2^{1000}=(2^{12})^{83}\cdot2^4\equiv16\equiv3\pmod{13}\) です。
例2：逆元を作る
合同式 \(5x\equiv1\pmod{17}\) を解きます。
解答を見る
\(5^{16}\equiv1\pmod{17}\) なので \(5^{-1}\equiv5^{15}\pmod{17}\) です。 実際には \(5\cdot7=35\equiv1\pmod{17}\) なので \(x\equiv7\pmod{17}\) とすぐ分かります。
例3：素数判定の前処理
\(3^{100}+1\) は \(7\) で割り切れるか調べます。
解答を見る
\(3^6\equiv1\pmod7\) より \(3^{100}=3^{96}\cdot3^4\equiv1\cdot4\equiv4\pmod7\) です。 よって \(3^{100}+1\equiv5\pmod7\) で、\(7\) では割り切れません。
数学オリンピックでの使いどころ
- べき剰余の周期を作る最初の手段
- 逆元処理を通じた一次合同式の解法
- オイラーの定理・位数へ進む土台
ありがちな失敗
- 法が合成数でも同じ式を使う
- \(a^{p-1}\equiv1\pmod p\) を \(p\mid a\) の場合にも使う
- 指数分解 \(n=q(p-1)+r\) の余り \(r\) を計算ミスする
まず条件確認、次に指数分解、最後に余りの簡約。 この順を固定すると安定します。
次に学ぶもの
- オイラーの定理（法が合成数の場合）
- 位数と原始根
- 中国剰余定理との併用