Fermatの小定理 Eulerの定理 Carmichaelの定理

競技プログラミングでは ${}_n \mathrm{C}_r = \dbinom{n}{r}$ を用いた数え上げ問題が頻出します。このとき途中で割り算を用いますが、計算途中のオーバフローを避けるためモジュラ逆数というものを使いますが、このモジュラ逆数はFermat*1の小定理やEuler*2の定理といったものを利用して計算されていたりします。
他にも整数の性質を用いた問題ではこれらの定理を背景として作られる問題もあります。今回はこれらの定理について必要な前提知識とともに解説っぽいことをしていきたいと思います。また、これらの定理は $$
a^{f(n)} \equiv 1 \pmod{n}
$$ という形をしていますが、 $\gcd(a,\,n) = 1$ のときにしか用いることができません。これを $\gcd(a,\,n) \neq 1$ のときについても使えるように一般化したものについてはこちらの記事を参考にしてください。

前提知識
- Eulerのトーシェント函数
- Carmichael函数
Fermatの小定理
- 証明
Eulerの定理
- 証明
- 周期と原始根
Carmichaelの定理
Fermatテスト
- Carmichael数
モジュラ逆数

前提知識

Eulerのトーシェント函数

Eulerのトーシェント函数は $n$ と互いに素であるような $n$ 以下の正整数の個数を与える函数 $\varphi(n)$ です。
$n$ が有限の自然数からなる集合 $S$ を用い、 $p_i$ を $i$ 番目の素数として $$
n = \prod_{i \in S} {p_i}^{e_i}\hspace{2em} (\forall i \in S,\ e_i \geq 1)
$$ と素因数分解されるとき、
$$
\varphi(n) = \prod_{i \in S} ({p_i}^{e_i} - {p_i}^{e_i - 1}) = n \prod_{i \in S} \left( 1 - \frac{1}{p_i} \right)
$$ となります。この公式の証明についてはこちらにあります。

Carmichael函数

Carmichael*3 函数はちょっと複雑な函数 $\lambda(n)$ です。この函数が返す値はEulerのトーシェント函数の与える値の約数となっています。
定義はこちらを参照してください。

Fermatの小定理

かの有名なFermatの最終定理と区別するため「小定理」という名前がついています。

Fermatの小定理

素数 $p$ と $p$ の倍数でない整数 $a$ について

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

が成り立つ

証明

証明方法はいくつかありますが、そのうち1つの方法で証明します。

$\gcd(a,\,p) = 1$ であるため $ia \equiv ja \Longleftrightarrow i \equiv j \pmod{p}$ となります。
よって $\{a,\,2a,\,\dots,\,(p - 1)a\}$ は $p$ を法として $\{1,\,2,\,\dots,\,p - 1\}$ と合同となる、すなわち、 $a,\,2a,\,\dots,\,(p - 1)a$ を $p$ で割った余りはすべて異なります。このことから
$$
\prod_{i = 1}^{p - 1} ia = a^{p - 1} (p - 1)! \equiv \prod_{i = 1}^{p - 1} i = (p - 1)! \pmod{p}
$$ となり、 $(p - 1)!$ は $p$ と互いに素であるため、両辺を $(p - 1)!$ で割ることができ、 $a^{p - 1} \equiv 1 \pmod{p}$ を得ることができます。

Eulerの定理

Fermatの小定理を法が素数でない場合に拡張しましょう。

Eulerの定理

互いに素な2整数 $a,\,n$ について

$a^{\varphi(n)} \equiv 1 \pmod{n}$

が成立する

素数 $p$ について $\varphi(p) = p - 1$ となるためEulerの定理はFermatの定理を含みます。

証明

Fermatの小定理とほぼ同じように証明できます。

$\gcd(a,\,n) = 1$ であるため $ia \equiv ja \Longleftrightarrow i \equiv j \pmod{n}$ となります。
$n$ 以下の $n$ と互いに素な $\varphi(n)$ 個の正整数 $m_1,\,m_2,\,\dots,\,m_{\varphi(n)}$ についてそれぞれ $a$ を掛けた $am_1,\,am_2,\,\dots,\,am_{\varphi(n)}$ を $n$ で割った余りはそれぞれ異なり、また全て $n$ と互いに素であるため、
$$
\prod_{i = 1}^{\varphi(n)} am_{i} = a^{\varphi(n)} \prod_{i = 1}^{\varphi(n)} m_{i} \equiv \prod_{i = 1}^{\varphi(n)} m_{i} \pmod{n}
$$ となりますが、 $\displaystyle \prod_{i = 1}^{\varphi(n)} m_{i}$ は $n$ と互いに素であるため、 $a^{\varphi(n)} \equiv 1 \pmod{n}$ とできます。

周期と原始根

Eulerの定理より $a^{m} \equiv a^{m + \varphi(n)} \pmod{n}$ より $a$ の累乗の余りの周期は $\varphi(n)$ であることが分かります。このことは $n$ と互いに素であればどんな $a$ についても成り立ちます。しかし全ての $a$ で最小の周期が $\varphi(n)$ となる訳ではありません。例えば $n = 7$ とすると $$\begin{align}
&1: 1 \rightarrow \cdots
\\&2: 2 \rightarrow 4 \rightarrow 1 \rightarrow \cdots
\\&3: 3 \rightarrow 2 \rightarrow 6 \rightarrow 4 \rightarrow 5 \rightarrow 1 \rightarrow \cdots
\\&4: 4 \rightarrow 2 \rightarrow 1 \rightarrow \cdots
\\&5: 5 \rightarrow 4 \rightarrow 6 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow \cdots
\\&6: 6 \rightarrow 1 \rightarrow \cdots
\end{align}$$ となり、 $a \equiv 3\ \mathrm{or}\ 5$ のときは最小周期が $6 = \varphi(7)$ となりますが、その他の時は最小周期は $\varphi(7)$ にはなりません。一般に最小周期が $\varphi(n)$ となるような $a$ (正確にはそれを $n$ で割ったもの) を $n$ を法とした原始根と言い、 $a,\,a^2,\,\dots,\,a^{\varphi(n)}$ を $n$ で割った余りには $n$ 以下の $n$ と互いに素な数が1度ずつ出てきます。

原始根でない $a$ の最小周期、すなわち $a^m \equiv 1 \pmod{n}$ となる最小の $m$ は $\varphi(n)$ の約数になります。それを背理法で示します。
もしも最小周期が $\varphi(n)$ の約数でない $b$ であるとします。 $a^b \equiv 1 \pmod{n}$ で $a^{\varphi(n)} \equiv 1 \pmod{n}$ の両辺を割ることで $a^{\varphi(n) - b} \equiv 1 \pmod{n}$ を得ます。この操作を繰り返すことで $\varphi(n)$ を $b$ で割った余りを $c$ として $a^c \equiv 1 \pmod{n}$ となりますが、このとき $1 \leq c \lt b$ であるため、 $b$ の最小性に反します。よって最小周期は $\varphi(n)$ の約数でなければならないことが分かりました。

原始根ですが全ての $n$ について存在するわけではありません。 $n = 12$ のとき
$$\begin{align}
1&: 1 \rightarrow \cdots
\\5&: 5 \rightarrow 1 \rightarrow \cdots
\\7&: 7 \rightarrow 1 \rightarrow \cdots
\\11&: 11 \rightarrow 1 \rightarrow \cdots
\end{align}$$ となりますが、 $\varphi(12) = 4$ であるため、原始根が存在しません。

Carmichaelの定理

実はEulerの定理は必ずしも $n$ と互いに素な $a$ について $a^m \equiv 1 \pmod{n}$ となるような最小の $m$ を与えるものではありません。これに対してCarmichaelの定理は最適化したもので、最小の $m$ を与えます。

Carmichaelの定理

互いに素な2整数 $a,\,n$ について

$a^{\lambda(n)} \equiv 1 \pmod{n}$

が成立する

全ての $n$ と互いに素な $a$ について $a^i$ $(i = 1,\,2,\,\dots)$ を $n$ で割った余りの最小周期は $\lambda(n)$ の約数となる

最小周期が $\lambda(n)$ となるような $a$ が必ず存在する

この定理はかなり強いもので、証明は群論を用いた少し複雑なもので*4、ここでは証明は省くことにします。

また、全ての $n$ と互いに素な $a$ についての最小周期が $\lambda(n)$ の約数になることについての証明は、上側の主張 $(a^{\lambda(n)} \equiv 1 \pmod{n})$ を認めれば、Eulerのものの $\varphi(n)$ を $\lambda(n)$ に置き換えるだけでOKです。

Fermatテスト

Fermatの小定理の対偶をとると

互いに素な2整数 $a,\,n$ について

$a^{n - 1} \not\equiv 1 \pmod{n}$

となるとき $n$ は合成数である

この条件を用いて次のような $n$ について素数判定を行うことができます。

$a$ を $2$ 以上 $n$ 未満として適当に決める
$\gcd(a,\,n) \neq 1$ であるとき $n$ は合成数である
$a^{n - 1} \not\equiv 1 \pmod{n}$ ならば $n$ は合成数であり、そうでなければ 確率的素数となる

3.で素数でなく確率的素数となるのはFermatの小定理の対偶は $n$ が合成数であることの十分条件に過ぎないからです。つまり、素数でなくとも3.まで通過することがあるわけです。確率的素数であるような合成数を擬素数と言います。今回はFermatテストであるためFermat擬素数と呼ばれます。

Carmichael数

Fermat擬素数であっても底 $a$ を変えればFermatテストを通過しないようになることがあります。即ち $a$ を何度も取り換えることで確率的素数の確率は上がっていきます。

しかし、素数でないにもかかわらず、 $2$ 以上 $n$ 未満の全ての $a$ についてFermatテストを通過してしまうような数が存在します。そのような数をCarmichael数や絶対擬素数と呼びます。具体的には $561,\,1105,\,1729,\,\dots$ と言った数で無数に存在することが知られています。

これらの数はCarmichaelの定理より $\lambda(n)$ が $n - 1$ の約数であるような数であることが分かります。

モジュラ逆数

法 $n$ での $a$ のモジュラ逆数とは
$$
ax \equiv 1 \pmod{n}
$$ となるような $x$ (を $n$ で割った余り)のことです。普通の逆元と同じように $a^{-1}$ と表記します。

$a$ と $n$ が互いに素でないときはこのような $x$ が存在しないため、モジュラ逆数は存在しません。

$a$ と $n$ が互いに素な時、Eulerの定理より*5
$a^{\varphi(n)} = a \cdot a^{\varphi(n) - 1} \equiv 1 \pmod{n}$ より $a^{-1} \equiv a^{\varphi(n) - 1} \pmod{n}$ となります。
因みに余談ですがモジュラ逆数はBézout*6の等式 $ax + ny = 1$ の解であるため拡張Εὐκλείδης*7の互除法によっても求めることができます。