フェルマーの小定理 a^(p−1)≡1 (mod p)｜並べかえと二項定理による2通りの証明・大きな累乗の余りの例題【大学数学・東大京大レベル】

フェルマーの小定理

17世紀フランスの数学者フェルマーが述べた定理で、有名な「フェルマーの最終定理（大定理）」とは別のものです。$\equiv$ は合同式の記号で、「$p$ でわった余りが等しい」という意味です。

証明（2通り）

証明1：並べかえ

$a$ は $p$ の倍数でないとします。$a,\ 2a,\ 3a,\ \cdots,\ (p-1)a$ を $p$ でわった余りを考えます。

1. どれも $0$ ではありません（$p$ は素数で、$k$ も $a$ も $p$ の倍数でないから、$ka$ も $p$ の倍数でない）。
2. どの2つも余りがちがいます。もし $ia\equiv ja$（$1\le i<j\le p-1$）なら、$p$ が $(j-i)a$ をわり切りますが、$0<j-i<p$ で $a$ も $p$ の倍数でないので、素数 $p$ はわり切れません。
3. よって、余りは $1,2,\cdots,p-1$ を並べかえたものです。

全部かけると

$$a\cdot2a\cdot3a\cdots(p-1)a\equiv1\cdot2\cdot3\cdots(p-1)\pmod p,\quad\text{つまり}\quad a^{p-1}(p-1)!\equiv(p-1)!\pmod p$$

$(p-1)!$ は $p$ と互いに素なので両辺をわってよく、$a^{p-1}\equiv1\pmod p$ です。

証明2：二項定理と数学的帰納法

まず、$1\le k\le p-1$ のとき ${}_p\mathrm{C}_k$ は $p$ の倍数です。$k\cdot{}_p\mathrm{C}_k=p\cdot{}_{p-1}\mathrm{C}_{k-1}$ で、右辺は $p$ の倍数。$k<p$ と $p$ は互いに素なので、${}_p\mathrm{C}_k$ が $p$ の倍数になります。

次に、自然数 $a$ について $a^p\equiv a$ を数学的帰納法で示します。$a=1$ では成り立ちます。$a$ で成り立つとすると、二項定理より

$$(a+1)^p=a^p+\sum_{k=1}^{p-1}{}_p\mathrm{C}_k\,a^k+1\equiv a^p+1\equiv a+1\pmod p$$

となり $a+1$ でも成り立ちます。（0 や負の整数も、$p$ の倍数を足して自然数にすれば同じです。）$a$ が $p$ の倍数でなければ、$a^p\equiv a$ の両辺を $a$ でわって $a^{p-1}\equiv1$ が出ます。

大学受験（数学A 整数の性質）での使い方

高校の範囲をこえる内容と入試での使い方

• 範囲外の定理：高校の数学Aの整数では、約数・倍数、互除法、不定方程式などを学びます。フェルマーの小定理は教科書の本文の範囲外で、合同式も発展として扱われることが多い内容です。
• 答案では証明してから：「$n^p-n$ は $p$ の倍数であることを示せ」のように、小定理そのものが問われることがあります。そのときに「フェルマーの小定理より」と書いては答えになりません。証明2（${}_p\mathrm{C}_k$ が $p$ の倍数＋帰納法）がそのまま答案になります。
• 余りの計算・検算に使う：「$3^{100}$ を $7$ でわった余り」のような問題では、答案では $3^1,3^2,\cdots$ の余りを順に調べて周期を示し、小定理は周期の見当づけ・検算に使うと安全です。
• 難関大の入試では、二項係数 ${}_p\mathrm{C}_k$ の性質や、べき乗の余りの周期の問題で、フェルマーの小定理が背景になっている問題があります。

よくある間違い

• 素数でないのに使う：$9$ は素数でないので、$2^8$ を $9$ でわった余りは $1$ ではなく $4$（$256=9\cdot28+4$）。素数でないときはオイラーの定理を使います。
• $a$ が $p$ の倍数のときに $a^{p-1}\equiv1$ とする：$7^6\equiv0\pmod7$ です。成り立つのは $a^p\equiv a$ のほうだけ。
• 逆も正しいと思う：$a^{n-1}\equiv1\pmod n$ でも $n$ が素数とは限りません。$2^{340}\equiv1\pmod{341}$ ですが、$341=11\times31$ です。

練習問題

1. 大学受験 $5^{2026}$ を $13$ でわった余りを求めなさい。
   答えと解説を見る

   $5^{12}\equiv1$、$2026=12\cdot168+10$。$5^2=25\equiv-1$ なので $5^{10}=(5^2)^5\equiv(-1)^5=-1\equiv12$。答え $12$
2. 大学受験 $2^{2026}$ を $11$ でわった余りを求めなさい。
   答えと解説を見る

   $2^{10}\equiv1\pmod{11}$、$2026=10\cdot202+6$。$2^6=64=11\cdot5+9$。答え $9$
3. 大学受験 すべての整数 $n$ について、$n^5-n$ は $30$ の倍数であることを示しなさい。
   答えと解説を見る

   $30=2\cdot3\cdot5$。$5$：小定理 $n^5\equiv n$。$3$：$n^3\equiv n$ より $n^5=n^3\cdot n^2\equiv n^3\equiv n$。$2$：$n^5$ と $n$ は偶奇が同じ。$2,3,5$ は互いに素なので $30$ の倍数

関連する公式

• 合同式（mod の計算）
• オイラー関数とオイラーの定理
• 二項定理
• 数学的帰納法
• 整数の性質（約数の個数・倍数の判定）
• 中国剰余定理

よくある質問

あわせて読みたい

• 合格大作戦 算数・数学公式辞典（公式一覧）