フェルマーの小定理はなぜ成り立つのか ― 剰余の世界の「対称性」
(Z/pZ)* の群構造からフェルマーの小定理を導き，a^{p-2} が逆元になる根拠を明らかにします．集合 {a, 2a, ..., (p-1)a} が {1, 2, ..., p-1} の置換であることの直感的な理解を中心に解説します．
フェルマーの小定理は，整数論で最も頻繁に使われる定理のひとつです．「が素数でなら」― この簡潔な主張の背後には，剰余の世界の美しい対称性が隠れています．
1 フェルマーの小定理の主張
定理 1 (フェルマーの小定理).
を素数， を で割り切れない整数とするとき，
注意 2.
同値な形として，任意の整数 に対して と書くこともできます（ なら両辺を で割って上の形になり， なら ）．
2 集合の置換 ― 証明の核心
証明.
を考えます． のとき，集合
が の置換（並べ替え）であることを示します．ステップ1： の各元は で にならない．なぜなら なら または ですが， かつ より，どちらも不成立です．ステップ2： の元はすべて異なる．もし （）なら ． より ですが， なので ．矛盾．以上より，（ で）です．両辺の元をすべてかけると，
左辺は ，右辺は です． なので両辺を で割って，
□
注意 3 (証明の直感).
をかける操作は， をシャッフルしますが，集合としては同じものです．元を全部かけた「総積」は不変量であり，その不変量から が出てくるのです．
3 の群構造
フェルマーの小定理を代数的に理解しましょう．
定義 4 ().
を素数とするとき， に乗法を入れたものは群をなします．これを の乗法群と呼びます．
注意 5.
群の公理を確認しましょう：
閉性： かつ なら
結合律：整数の乗法の結合律から従います
単位元：
逆元：拡張ユークリッドの互除法（前回の記事）で計算できます
定理 6 (ラグランジュの定理からの帰結).
です．群論のラグランジュの定理により，任意の元 の位数は の約数です．したがって です．
注意 7.
フェルマーの小定理は，有限群の元の位数が群の位数の約数であるというラグランジュの定理の特殊ケースです．初等的な証明（集合の置換による証明）は，実はラグランジュの定理の証明と本質的に同じ論法を使っています．
4 が逆元になる理由
定理 8.
を素数， とするとき， の での逆元は です．
証明.
フェルマーの小定理より ．これを と読み替えると， が の逆元であるとわかります． □
例 9.
， のとき，．検算：．
5 競プロでの mod 逆元
注意 10 (2つの方法の比較).
での逆元を求める方法は2つあります：
フェルマーの小定理： を繰り返し二乗法で で計算
拡張ユークリッドの互除法： で計算（定数倍が小さい）
例 11 (二項係数の mod 計算).
を求める典型問題です． なので，分母の逆元が必要です． を前計算しておけば， と の逆元をフェルマーの小定理で求めて で計算できます．
6 オイラーの定理への一般化
定義 12 (オイラーの関数).
は 以上 以下の整数のうち と互いに素なものの個数です．
定理 13 (オイラーの定理).
ならば ．
注意 14.
（素数）のとき なので，フェルマーの小定理に一致します．オイラーの定理はフェルマーの小定理の一般化であり， の群の位数が であることから従います．
7 まとめ
フェルマーの小定理： が素数， のとき
証明の核心は「 をかける操作が の置換になる」こと
代数的には のラグランジュの定理
が逆元になるのはフェルマーの小定理の直接的帰結
一般化がオイラーの定理で，RSA 暗号の理論的基盤です
次の記事では，連立合同式を「合体」する魔法 ― 中国剰余定理に迫ります．