これは 日曜数学 Advent Calendar 2023 の 21 日目の記事です.
オイラーの定理の話をする前にオイラー関数の話をします. 正の整数 $n$ に対して, $n$ 以下の $n$ と互いに素な正の整数の個数を $\varphi(n)$ と表します. 別の言い方をすると, 環 $R$ の単数群を $U(R)$ で表すとき $$\varphi(n) = |U(\mathbb{Z}/n\mathbb{Z})|$$ と表せます.
$\varphi(n)$ の求め方は簡単で, $n$ が素数 $p_1, p_2, \dots, p_k$ を用いて $$n = {p_1}^{e_1} {p_2}^{e_2} \dots {p_k}^{e_k}$$ と素因数分解できるとき $$\varphi(n) = n \prod_{i = 1}^k \left( 1 - \frac{1}{p_i} \right)$$ と求められます.
オイラーの定理が主張することは, $a$ が $n$ と互いに素な整数のとき $$a^{\varphi(n)} \equiv 1 \pmod{n}$$ です.
一つ具体例を計算してみましょう. $n = 24$ のとき, $24 = 2^3 \cdot 3$ なので $$\varphi(24) = 24 \left( 1 - \frac{1}{2} \right) \left( 1 - \frac{1}{3} \right) = 8$$ ですから, $a$ と $24$ が互いに素ならば $$a^8 \equiv 1 \pmod{24}$$ が成り立つ, というのがオイラーの定理の主張になります.
ところが実際は \begin{align} U(\mathbb{Z}/24\mathbb{Z}) &\cong U(\mathbb{Z}/3\mathbb{Z} \oplus \mathbb{Z}/8\mathbb{Z}) \\ &\cong U(\mathbb{Z}/3\mathbb{Z}) \times U(\mathbb{Z}/8\mathbb{Z}) \\ &\cong C_2 \times C_2 \times C_2 \end{align} ($C_2$ は 2 次の巡回群)なので, $U(\mathbb{Z}/24\mathbb{Z})$ は単位元以外の位数は全て 2 です. よって $a$ と $24$ が互いに素ならば $$a^2 \equiv 1 \pmod{24}$$ が成り立ちます.
オイラーの定理は主張が簡明で分かりやすいですが, このように評価は結構ガバガバなことが多いので, 使うときは十分注意したいものですね.
赤猫堂本舗「数学に関するよしなしごと」へ(鋭意建設中)