フェルマーの小定理とは？証明の謎とRSA暗号を支える神髄を徹底解剖

17世紀のフランスで一人の裁判官が余白に残した着想が、380年余りの時を経て現代のインターネット空間全体を守る盾になろうとは、当時の誰が想像したでしょうか。ピエール・ド・フェルマーが発見した数論の至宝「フェルマーの小定理」は、一見すると純粋数学の抽象的なパズルに過ぎないように思えます。しかし実際には、ウェブ上の暗号通信から金融決済、さらには競技プログラミングの現場に至るまで、今日のデジタル社会の根幹を人知れず支えています。

教科書的な数式の背後には、思わず息をのむような美しい論理の連鎖が眠っています。「名前は聞いたことがあるが証明の道筋が分からない」「なぜこれが暗号に応用できるのか仕組みが見えない」と感じる初学者から、実務でモジュロ演算を扱うエンジニアまで、知的好奇心を刺激するその全体像を徹底解剖します。

📌 【この記事の重要ポイントまとめ】

• 要点1：フェルマーの小定理は素数を法としたべき乗の余りに潜む普遍的な規則性を示す基礎定理であり、「最終定理」とは時代・難易度・対象が根本から異なる。
• 要点2：証明は剰余類の置換や二項定理と数学的帰納法により極めて明快に導かれ、この性質がオイラーの定理を経てRSA暗号の復号ロジックへと昇華している。
• 要点3：素数判定（フェルマーテスト）におけるカーマイケル数（絶対擬素数）の落とし穴や、競技プログラミングでのモジュラ逆元計算など、理論と実装の間に横たわる実用上の境界線を把握することが不可欠である。

【歴史の舞台裏】裁判官フェルマーの経歴と「最終定理」との決定的な違い

ピエール・ド・フェルマーは、大学教授や研究所に籍を置く職業的数学者ではありませんでした。彼の本職はトゥールーズの高等法院で参事官を務めた高級官僚、すなわち法服貴族の法律家です。裁判業務という極めて厳格な激務の合間、夜な夜な古典ギリシャの数学書を読み耽り、余暇の知的遊戯として数論に没頭していた「孤高のアマチュア」でした。公刊を嫌い、発見した定理を仲間の学者たちへ挑戦状のような書簡で送りつける風変わりなスタイルは、当時の学界を大いに刺激しました。

フェルマーの小定理が初めて文書として登場したのは、1640年10月18日に友人である文人フレニクル・ド・ベシーへ宛てた書簡の中です。この中でフェルマーは「ある素数 $p$ が $a^{p-1} - 1$ を割り切る」という命題を提示しつつ、「論述が長くなりすぎるのを恐れるため、ここには証明を書かない」と記しました。フェルマーの悪癖ともいえる「証明の省略」はここでも発揮され、完全な厳密証明が活字となったのは、およそ1世紀後の1736年、大数学者レオンハルト・オイラーの手によってでした。

一般の読者が最も混同しやすいのが、世界的なベストセラー書籍でも知られる「フェルマーの最終定理」との違いです。小定理が「素数を法とする合同式と剰余の性質」を扱う平易かつ普遍的な基礎命題であるのに対し、最終定理は「$x^n + y^n = z^n$（$n \ge 3$）を満たす自然数解は存在しない」という不定方程式の難問です。最終定理はアンドリュー・ワイルズによって1995年に完全解決されるまで350年以上を要しましたが、小定理は初等的な整数論の枠組みで完全に証明が完結します。両者は難易度も対象領域も全くの別物です。

【徹底図解】フェルマーの小定理をわかりやすく紐解く｜合同式modの基礎と基本公式

フェルマーの小定理を理解するための第一歩は、数論の共通言語である「合同式（mod計算）」の感覚を掴むことです。合同式とは、割り算の「余り（剰余）」に着目した計算体系を指します。日常の身近な例で言えば、12時間表記の時計がまさに合同式の世界です。現在の時刻が朝9時である場合、その5時間後は14時ですが、文字盤の上では「2時」を指します。これを数学では以下のように表現します。

$$9 + 5 \equiv 2 \pmod{12}$$

「12で割った余りが等しい」ことを「$\equiv$（合同）」という記号で表すのが合同式の基本ルールです。この余りの世界において、フェルマーの小定理は驚くほどシンプルで美しい法則を提示します。

定理の定義は次の通りです。$p$ を素数とし、$a$ を $p$ の倍数でない整数（$a$ と $p$ が互いに素）とするとき、次の関係が必ず成り立ちます。

$$a^{p-1} \equiv 1 \pmod p$$

あるいは、両辺に $a$ を掛け合わせることで、任意の整数 $a$ に対して成立する同値な表現として次の形もよく用いられます。

$$a^p \equiv a \pmod p$$

抽象的な文字だけでは実感が湧きにくいため、具体的な数値で検証してみましょう。例えば、素数 $p = 7$、整数 $a = 3$ を設定します。定理によれば $3^{7-1} = 3^6$ を 7 で割った余りは必ず 1 になるはずです。

実際に計算を進めると、$3^1 = 3$、$3^2 = 9 \equiv 2 \pmod 7$、$3^3 = 27 \equiv 6 \pmod 7$ と推移します。さらに指数を増やすと、$3^6 = (3^3)^2 \equiv 6^2 = 36$ となり、36 を 7 で割ると $36 = 7 \times 5 + 1$ ですから、余りは見事に「1」に収束します。どんなに巨大な累乗数であっても、指数が「素数引く1」に達した瞬間、余りの世界では原点である 1 へと時計の針が回帰するのです。

なぜ成り立つのか？驚きの証明ロジックを解明｜剰余の置換と二項定理・数学的帰納法

一見すると作為的に思えるこの関係式が、一体なぜいかなる素数においても例外なく成り立つのでしょうか。フェルマーの小定理の背後には、数学が持つ極めてエレガントな秩序が存在します。代表的な2つの証明アプローチからそのロジックを紐解きます。

アプローチ1：剰余類の置換を利用した鮮やかな証明

最も直感的で美しいとされるのが、集合の並び替えを利用する手法です。素数 $p$ で割ったときの 0 以外の余りは、必ず $\{1, 2, 3, \dots, p-1\}$ の $p-1$ 種類になります。この集合の各要素に、素数 $p$ と互いに素な整数 $a$ を掛け合わせた次の数列を考えます。

$$S = \{1a, 2a, 3a, \dots, (p-1)a\}$$

ここで重要なのは、この $S$ に含まれる数同士を $p$ で割った余りは、すべて互いに異なり、重複が一切発生しないという点です。もし仮に $ka \equiv ma \pmod p$（$1 \le k < m \le p-1$）が成り立ったとすると、$(m - k)a$ は $p$ の倍数となります。しかし $a$ は $p$ と互いに素であり、$m - k$ は $p$ より小さい正の整数であるため、$p$ の倍数にはなり得ず矛盾します。

すなわち、$S$ の要素を $p$ で割った余りは、元の $\{1, 2, 3, \dots, p-1\}$ の順番をただシャッフルして並び替えたものに過ぎません。したがって、両方の集合の全要素を掛け合わせた積は、$\pmod p$ において一致します。

$$(1a) \times (2a) \times (3a) \times \dots \times ((p-1)a) \equiv 1 \times 2 \times 3 \times \dots \times (p-1) \pmod p$$

左辺を整理すると $a$ が $p-1$ 個存在し、階乗 $(p-1)!$ が現れます。

$$a^{p-1} (p-1)! \equiv (p-1)! \pmod p$$

$p$ は素数であるため、1 から $p-1$ までの積である $(p-1)!$ は $p$ と互いに素です。したがって両辺を $(p-1)!$ で割ることが許され、鮮やかに目標の式が導き出されます。

$$a^{p-1} \equiv 1 \pmod p$$

アプローチ2：二項定理と数学的帰納法による代数的アプローチ

もう一つの王道の道筋が、高校数学の範囲でも完全に追体験可能な二項定理と数学的帰納法を用いたアプローチです。目標はすべての自然数 $a$ について $a^p \equiv a \pmod p$ を示すことです。

まず二項展開の公式を用いて $(a + 1)^p$ を分解します。

$$(a + 1)^p = a^p + \binom{p}{1}a^{p-1} + \binom{p}{2}a^{p-2} + \dots + \binom{p}{p-1}a + 1$$

ここで着目すべきは途中に現れる二項係数 $\binom{p}{k} = \frac{p!}{k!(p-k)!}$（$1 \le k \le p-1$）です。分子には素数 $p$ が含まれ、分母の $k!$ や $(p-k)!$ には $p$ 未満の数しか存在しないため、$p$ を約分して消すことができません。つまり、両端の項を除くすべての係数は $p$ の倍数になります。したがって、mod $p$ の世界では間の項がすべて綺麗に消失します。

$$(a + 1)^p \equiv a^p + 1 \pmod p$$

$a = 1$ のとき $1^p = 1$ より明らかに成立します。$a = k$ で $k^p \equiv k \pmod p$ が成り立つと仮定すると、$(k + 1)^p \equiv k^p + 1 \equiv k + 1 \pmod p$ となり、$a = k + 1$ でも成立します。数学的帰納法により、すべての自然数 $a$ において $a^p \equiv a \pmod p$ が証明されます。

【データ比較検証】数論の重要定理と素数判定アルゴリズムの性能差

フェルマーの小定理は単独で完結する理論にとどまらず、暗号技術やアルゴリズム設計の祖形として多様な定理や計算手法へと発展を遂げました。理論構造や計算量、用途の違いを整理したのが下表です。

【実態検証】現代社会の心臓部へ｜RSA暗号の仕組みとモジュラ逆元計算の現場

フェルマーの小定理が純粋数学の枠を飛び出し、世界のインフラとして定着した決定打が公開鍵暗号「RSA暗号」の発明です。1977年にロナルド・リベスト、アディ・シャミア、レオナルド・エードルマンの3名によって考案されたこの暗号系は、オイラーによる小定理の一般化（オイラーの定理）を数学的基盤としています。

RSA暗号が成立する決定的なカラクリ

RSA暗号では、巨大な2つの素数 $p, q$ の積である合成数 $N = pq$ を公開鍵の一部とします。オイラーのトーシェント関数 $\phi(N)$ は、互いに素な自然数の個数を表し、素数の積であれば $\phi(N) = (p-1)(q-1)$ と簡潔に求まります。

暗号化鍵 $e$ と復号鍵 $d$ は、$ed \equiv 1 \pmod{\phi(N)}$ を満たすように設計されます。送信者が平文 $M$ を暗号文 $C \equiv M^e \pmod N$ として送信した際、受信者は手元の秘密鍵 $d$ を用いて以下のように平文を復元します。

$$C^d \equiv (M^e)^d = M^{ed} = M^{1 + k\phi(N)} \equiv M \cdot (M^{\phi(N)})^k \equiv M \cdot 1^k \equiv M \pmod N$$

ここで $M^{\phi(N)} \equiv 1 \pmod N$ と変換できる根拠こそが、フェルマーの小定理を合成数へと拡張したオイラーの定理です。素因数分解の困難性を安全性の根拠にしつつ、復号の成立そのものは小定理の系（発展形）に完全に依存しています。私たちがスマートフォンで行うクレジットカード決済やSSL/TLS通信の裏側では、アクセスするたびにフェルマーの着想が実行されているのです。

競技プログラミングにおける「余り計算」とモジュラ逆元

一方、情報科学を学ぶ学生やソフトウェアエンジニアが直面する最も身近な応用例が、競技プログラミング（AtCoderなど）における「巨大な組み合わせ数の余り計算」です。組み合わせ記号 $\binom{n}{r} = \frac{n!}{r!(n-r)!}$ などの計算では、答えが天文学的な数値になるため、問題文で「$10^9+7$ や $998244353$ で割った余りを求めよ」と指定されるのが通例です。

しかし、合同式の世界では足し算・引き算・掛け算はそのまま行えますが、割り算（除算）をそのまま実行することはできません。そこで除算を乗算に変換するために「モジュラ逆元（法の下での逆数）」を用います。ある数 $b$ で割る代わりに、$b \times x \equiv 1 \pmod p$ となる $x$（逆元 $b^{-1}$）を掛けるのです。

ここで法 $p$ が素数である場合、フェルマーの小定理より以下が導かれます。

$$b^{p-1} \equiv 1 \implies b \times b^{p-2} \equiv 1 \pmod p$$

つまり、$b$ の逆元は単に $b^{p-2}$ を計算するだけで得られるのです。繰り返し二乗法（バイナリ法）を用いれば、わずか $O(\log p)$ の計算量で除算の逆元が手に入ります。拡張ユークリッド互除法を書く手間に比べ、わずか数行の実装で正確な剰余演算が完了するため、競プロ界隈における必須の基本テクニックとして定着しています。

一般に知られていない盲点とネットの誤解｜フェルマーテストの限界と擬素数の脅威

インターネット上の技術フォーラムや質問サイトでは、フェルマーの小定理に関して根強い誤解が散見されます。その最たるものが「フェルマーの小定理の逆も成り立つのではないか」、すなわち「ある数 $n$ に対して $a^{n-1} \equiv 1 \pmod n$ が成り立てば、$n$ は素数であると断定できる」という誤謬です。

結論から言えば、この逆の命題は明確に「偽」です。フェルマーの小定理の条件を偶然満たしてしまう合成数が存在し、これらを「擬素数（Pseudoprime）」と呼びます。

例えば、合成数 $341$（$11 \times 31$）に対して底を $a = 2$ とすると、$2^{340} \equiv 1 \pmod{341}$ が成立してしまい、素数判定テストをすり抜けてしまいます。さらに厄介なのが、いかなる底 $a$（ただし $\gcd(a, n) = 1$）を選んでも必ずフェルマーの小定理をクリアしてしまう極めて特殊な合成数、「絶対擬素数（カーマイケル数）」の存在です。

最小のカーマイケル数である 561（$3 \times 11 \times 17$）をはじめ、1105、1729、2465 などが無数に存在することが1994年に数学的に証明されています。もし現代の暗号システムを構築する際に、フェルマーテスト単体で素数を生成しようとすれば、カーマイケル数を誤って素数鍵として採用してしまい、暗号強度が根底から崩壊する致命的な脆弱性を生み出します。

このため、現代の商用暗号ライブラリでは、小定理の判定式を改良し、平方根の自明でない剰余チェックを組み込んだ「ミラー–ラビン素数判定法」を採用するのが業界の絶対的な標準となっています。「定理の美しさ」と「実装上の実用限界」を峻別して捉える視点こそが、真の技術的理解には欠かせません。

【プロの結論】数学的思考を武器にする人・落とし穴にはまる人の判断基準

抽象的な定理を現実の開発や問題解決に活かせるエンジニアと、バグや脆弱性に悩まされる初学者の間には、明確な分水嶺が存在します。フェルマーの小定理を道具として扱う際の判断基準を提示します。

向いている人・適切に武器化できる条件

• 前提条件の境界値を常に意識できる人：フェルマーの小定理が使えるのは「法が素数であり、割る数と法が互いに素である」場合に限られます。法が合成数の場合にオイラーの定理や拡張ユークリッド互除法へ即座に思考を切り替えられる柔軟性を持つエンジニアは、堅牢なシステムを設計できます。
• 数式をアルゴリズムの計算量（オーダー）に翻訳できる人：単に定理を眺めるだけでなく、指数部を $p-2$ と置いた際に繰り返し二乗法で $O(\log p)$ に落とし込める計算幾何学的な視点を持つ人は、パフォーマンスの高いコードを書くことができます。
• 暗号ライブラリの内部動作をブラックボックスにしない人：既製の暗号APIを利用する際にも、背後にある数学的限界や擬素数のリスクを把握した上で適切な鍵長・アルゴリズムを選択できるセキュリティエンジニアがこれに該当します。

落とし穴にはまる人・慎重になるべき条件

• 商用コードで暗号プリミティブを自作しようとする人：「フェルマーテストで簡単に素数判定ができる」と誤認し、オレオレ暗号や自前の素数生成器を業務プロダクトに組み込む行為は重大なインシデントに直結します。暗号実装はOpenSSLなどの監査済みライブラリを使用するのが鉄則です。
• 除算の逆元を法が無条件で素数でない環境で適用する人：法 $m$ が素数でない（例えば $10^9$ など偶数の）状況で $a^{m-2}$ を計算しても、正しいモジュラ逆元は得られず誤った計算結果を出力し続けます。

【フェルマーの小定理】に関するよくある質問（FAQ）

Q1：フェルマーの小定理は高校数学の教育課程に含まれていますか？大学入試でも出題されますか？
A1：日本の現行学習指導要領（数学Aの「整数の性質」など）において、公式そのものが必須知識として指定されているわけではありません。しかし、合同式の応用問題や、二項定理・数学的帰納法を用いた誘導形式の大問として、東京大学や京都大学をはじめとする難関大学の個別試験で極めて頻繁に題材として取り上げられています。背景知識として定理の証明構造を理解しておくことは、受験戦略上も大きなアドバンテージとなります。

Q2：量子コンピュータが実用化されるとフェルマーの小定理は無意味になるのですか？
A2：定理自体の数学的真理性が損なわれることは決してありません。ただし、フェルマーの小定理を土台にしたRSA暗号などの「素因数分解の困難性に依存する公開鍵暗号」は、ショアのアルゴリズムを走らせる大規模な耐障害型量子コンピュータによって多項式時間で解読されるリスクがあります。そのため国際的には、小定理とは異なる格子暗号などをベースにした「耐量子計算機暗号（PQC）」への移行作業が急速に進められています。

Q3：なぜ競技プログラミングでは「1000000007」や「998244353」という特定の数が法として指定されるのですか？
A3：理由は主に2点あります。第1に、これらの数が「32ビット符号付き整数の最大値（約21.4億）に収まり、かつ足し算を行ってもオーバーフローしない大きさの素数」であるためです。第2に、法が素数であればフェルマーの小定理を用いた $O(\log p)$ の逆元計算が保証されるためです。特に $998244353$ は $119 \times 2^{23} + 1$ と分解でき、高速フーリエ変換（NTT）を用いた畳み込み計算と相性が極めて良いため、現代のアルゴリズムコンテストで標準的に採用されています。

まとめ：純粋数学からデジタルインフラへ繋がるフェルマーの遺産

17世紀の法服貴族ピエール・ド・フェルマーが知的好奇心の赴くままに発見した性質は、無意味な余暇の戯れどころか、現代社会のあらゆる通信セキュリティを支える強固な背骨となりました。合同式の並び替えという極めてシンプルな証明ロジックから、巨大なRSA暗号の復号機構、さらには競技プログラマーが日々酷使するモジュラ逆元まで、その影響力は情報化が進むほどに増しています。

一見難解に見える数式も、その背景にある「剰余の周期性」と「素数特有の性質」を捉えれば、極めて明快な秩序によって成り立っていることが分かります。定理の美しさを味わうと同時に、擬素数の存在に代表される実装上の境界線を冷静に見極めること。数学の理論的深度とエンジニアリングの実用性を繋ぐ架け橋として、フェルマーの小定理はこれからもデジタル空間の最前線で息づき続けます。 （出典: フェルマー の 小 定理（Yahoo!ニュース））