アルゴリズム論特論（塩田）第7回 (3) オイラーの定理
前へ / 戻る / 次へ
$\newcommand{\ol}[1]{\overline{#1}}$
$\newcommand{\znz}[1]{\mathbb{Z}/#1 \mathbb{Z}}$
$\newcommand{\znzc}[1]{(\mathbb{Z}/#1 \mathbb{Z})^{\times}}$
$\newcommand{\inv}[1]{\displaystyle{\frac{1}{#1}}}$
オイラー関数
Def.10（オイラーのトーシャント関数）
$\znzc{n}$ の要素数を $\varphi(n)$ と表す。
$\varphi$ をオイラーのトーシャント関数（または簡単にオイラー関数）と呼ぶ。
言い換えれば、$1$, $\cdots$, $n$ の中で $n$ と互いに素な整数の個数が $\varphi(n)$ です。
Ex.7 より
Ex.11 $\varphi(2)=1$, $\varphi(3)=2$, $\varphi(4)=2$, $\varphi(5)=4$, $\varphi(6)=2$, $\varphi(7)=6$, $\varphi(10)=4$.
また
Rem.8 より
Rem.12 $p$ が素数ならば $\varphi(p)=p-1$.
オイラーの定理
なぜ $\varphi$ をオイラー関数と呼ぶかと言うと、次の定理をオイラー先生が発見したからです。
Th.13（オイラーの定理） $a \in \znzc{n}\quad$ならば$\quad a^{\varphi(n)}=\ol{1}$.
同じことを合同式で書けば
Th.13'（オイラーの定理） $\gcd(a,n)=1\quad$ならば$\quad a^{\varphi(n)} \equiv 1 \pmod{n}$.
証明 $m=\varphi(n)$ とおき、$\znzc{n}$ の $m$ 個の要素に
$x_1$, $x_2$, $\cdots$, $x_m$
と名前を付けます。
Th.9 (3) から $a$ 倍写像は全単射ですから
$ax_1$, $ax_2$, $\cdots$, $ax_m$
も $\znzc{n}$ の $m$ 個の要素になります。従ってそれらの積は同じ値になり、
\begin{align}
x_1 \times x_2 \times \cdots \times x_m
&= (ax_1) \times (ax_2) \times \cdots \times (ax_m) \\
&= a^m \times (x_1 \times x_2 \times \cdots \times x_m) \\
\end{align}
$ (x_1 \times x_2 \times \cdots \times x_m)$ は $\znzc{n}$ の要素ですから両辺を割ることができて
$\ol{1}=a^m=a^{\varphi(n)}$.
(証明終)
Ex.14 $n=24$, $a=\ol{5}$ のとき、
$\znzc{24}=\{\,\ol{1},\ol{5},\ol{7},\ol{11},\ol{13},\ol{17},\ol{19},\ol{23}\,\}$, $\quad\varphi(24)=8$
で、
$\ol{5}\times\ol{1}=\ol{5}$,
$\quad\ol{5}\times\ol{5}=\ol{1}$,
$\quad\ol{5}\times\ol{7}=\ol{11}$,
$\quad\ol{5}\times\ol{11}=\ol{7}$,
$\ol{5}\times\ol{13}=\ol{17}$,
$\quad\ol{5}\times\ol{17}=\ol{13}$,
$\quad\ol{5}\times\ol{19}=\ol{23}$,
$\quad\ol{5}\times\ol{23}=\ol{19}$
辺々掛けると
$\ol{5}^{\,8}
\times(\ol{1}\times\ol{5}\times\ol{7}\times\ol{11}\times\ol{13}\times\ol{17}\times\ol{19}\times\ol{23})$
$=\ol{5}\times\ol{1}\times\ol{11}\times\ol{7}\times\ol{17}\times\ol{13}\times\ol{23}\times\ol{19}$
$=\ol{1}\times\ol{5}\times\ol{7}\times\ol{11}\times\ol{13}\times\ol{17}\times\ol{19}\times\ol{23}$
よって
$\ol{5}^{\,8} = \ol{1}$
Cor.15（フェルマの小定理の別証明） 特に $p$ が素数ならば $\varphi(p)=p-1$ ゆえ、
$a$ が $p$ で割り切れなければ$\quad a^{p-1} \equiv 1 \pmod{p}$.
オイラーの定理で法を素数に限定した version がフェルマの小定理、という訳です。