アルゴリズム論特論（塩田）第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$.
また
Prop.8 より
Prop.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=21$, $a=\ol{5}$ のとき、
$\znzc{21}=\{\,\ol{1},\ol{2},\ol{4},\ol{5},\ol{8},\ol{10},\ol{11},\ol{13},\ol{16},\ol{17},\ol{19},\ol{20}\,\}$, $\quad\varphi(21)=12$
で、
\begin{align}
\ol{5}\times\ol{1}&=\ol{5} \\
\ol{5}\times\ol{2}&=\ol{10} \\
\ol{5}\times\ol{4}&=\ol{20} \\
\ol{5}\times\ol{5}&=\ol{4} \\
\ol{5}\times\ol{8}&=\ol{19} \\
\ol{5}\times\ol{10}&=\ol{8} \\
\ol{5}\times\ol{11}&=\ol{13} \\
\ol{5}\times\ol{13}&=\ol{2} \\
\ol{5}\times\ol{16}&=\ol{17} \\
\ol{5}\times\ol{17}&=\ol{1} \\
\ol{5}\times\ol{19}&=\ol{11} \\
\ol{5}\times\ol{20}&=\ol{16} \\
\end{align}
辺々掛けると
$\ol{5}^{\,12}
\times(\ol{1}\times\ol{2}\times\ol{4}\times\ol{5}\times\ol{8}\times\ol{10}\times\ol{11}\times\ol{13}\times\ol{16}\times\ol{17}\times\ol{19}\times\ol{20})$
$=\ol{5}\times\ol{10}\times\ol{20}\times\ol{4}\times\ol{19}\times\ol{8}\times\ol{13}\times\ol{2}\times\ol{17}\times\ol{1}\times\ol{11}\times\ol{16}$
$=\ol{1}\times\ol{2}\times\ol{4}\times\ol{5}\times\ol{8}\times\ol{10}\times\ol{11}\times\ol{13}\times\ol{16}\times\ol{17}\times\ol{19}\times\ol{20}$
よって
$\ol{5}^{\,12} = \ol{1}$
Cor.15（フェルマの小定理の別証明） 特に $p$ が素数ならば $\varphi(p)=p-1$ ゆえ、
$a$ が $p$ で割り切れなければ$\quad a^{p-1} \equiv 1 \pmod{p}$.
オイラーの定理で法を素数に限定した version がフェルマの小定理、という訳です。