オイラーの定理 (数論)（Euler's theorem）、カーマイケルの定理(Carmichael function)

はじめに

フェルマーの小定理について投稿しましたが、これをもう少し一般化したオイラーの定理を求めていきます。
さらに、一般化したカーマイケルの定理を示します。

フェルマーの小定理 - Wikipedia
オイラーの定理 (数論) - Wikipedia
カーマイケルの定理

オイラーのφ関数(Euler's totient function)

オイラーのφ関数(オイラーのトーシェント関数)は、$\varphi(n)$と表します。
正の整数$n$に対して、$1$から$n$までの自然数のうち$n$と互いに素なものの個数を与えます。

オイラーのφ関数 - Wikipedia

オイラーの定理(Euler's theorem)

$n$を正の整数とする。$n,a$を互いに素である正の整数とする時、以下が成り立ちます。

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

(証明)

$n$と互いに素の数を以下の集合とする。
オイラーのφ関数の定義どおり$\ \varphi(n)\ $個あります。

A = \{ b_1,b_2,\cdots,b_{\varphi(n)} \}

これに、$n$と互いに素の数を$a$を乗算します。

B = \{ ab_1,ab_2,\cdots,ab_{\varphi(n)} \}

ここで、$ab_i,1\le i \le \varphi(n)\ $を考えます。
$a,b_i$はどちらも$n$と互いに素なので、$ab_i$も$n$と互いに素になります。

$ab_i = nq_i + r_i$ とすれば、ユークリッドの互除法で使った原理より、$r_i\ $も$n$と互いに素になります。
という事は、$ab_i \bmod n$も$n$と互いに素になります。

$ab_i,ab_j,1\le i \le j \le \varphi(n)$ を考えます。
これらの剰余(modulo)は異なります。もし同じであれば$b$も同じになります。

\begin{align*}
& ab_i \equiv ab_j \pmod{n} \\
& b_i \equiv b_j \pmod{n} \\
& b_i = b_j \\
\end{align*}

ようするに、集合$B$の各値の剰余(modulo)は集合$A$の値を並べ替えたものとなります。
したがって、集合$A,B$の各値を乗算すると以下の式が成り立ちます。

\begin{align*}
& b_1\times b_2 \times \cdots \times b_{\varphi(n)} \equiv ab_1\times ab_2 \times \cdots \times ab_{\varphi(n)} \pmod{n}\\
& P = b_1\times b_2 \times \cdots \times b_{\varphi(n)} \\
& P \equiv a^{\varphi(n)}P \pmod{n} \\
& 1 \equiv a^{\varphi(n)} \pmod{n} \\
\end{align*}

オイラーのφ関数(Euler's totient function)

互いに素である正の整数$a,b$において以下の式が成り立つ事を証明します。

\varphi(ab) = \varphi(a)\varphi(b)

先に補助定理を定めておきます。

(補助定理）
整数$a,b$はともに2以上の整数とします。
$a,b$について、正の整数$n$を$n = ap + r\ ,\ n = bq + s$ ($\ p,q,r,s\ $は整数 $\ 1\le r\le a,1\le s\le b\ $）
と表したときの$r$と$s$の組$(r,s)$を考え、それを$A_n$とします。
このとき互いに素である$a,b$に対して$\ A_1,A_2,A_3,\cdots,A_{ab}$の$ab$個はすべて異なる組であり、
$\ (r,s)\ (1\le r\le a,1\le s\le b)$の1つ1つがちょうど一度ずつ現れます。

(補助定理の証明)
$1\le x\le y\le ab$・・・①である$x,y\ $について、$A_x$と$A_y$は同じ組とします。
このときある整数$\ p,p',q,q',r,s(1\le r\le a,1\le s\le b)$について
$x = ap + r = bp' + s\ ,\ y = aq + r = bq' + s\ $であり
$y − x = a(q − p)\ $かつ $y − x = b(q' − p')$ とします。
$y − x$ は$a$の倍数かつ$b$の倍数であって、$a,b$が互いに素であることから$\ y−x$は$ab$の倍数となります。
しかし①より$\ 0\le y − x\le ab − 1$なので$y − x = 0 , y = x
$です。
以上より$1\le x < y\le ab$であるすべての$x,y$について$A_x,A_y$が異なる組であることが示されましたが、
これから$A_1,A_2,\cdots,A_{ab}$はすべて異なる$ab$組あります。
また、$(r,s)$としてありうるのは定義から$ab$個であるので、この一つ一つがちょうど１度ずつ
$A_1,A_2,\cdots,A_{ab}$において現れることが分かります。

互除法の原理とオイラー関数の乗法性

まず、$1$から$ab$までの正の整数を以下のように並べます。

\begin{array}{lllllll}
 1 & 2 & \cdots & t & \cdots & a-1 & a \\
1+a & 2+a & \cdots & t + a & \cdots & (a-1) + a & 2a \\
\vdots & \vdots & \ddots & \vdots & \ddots & \vdots & \vdots \\
1+a(b-1) & 2+a(b-1) & \cdots & t+a(b-1) & \cdots & (a-1)+a(b-1) & ab \\
\end{array}

各列は正の整数$a$において、互いに素でない列は消す事ができます。

\begin{array}{lllllll}
 t_1 & t_2 & \cdots & t_{\varphi(a)} \\
t_1+a & t_2+a & \cdots & t_{\varphi(a)} + a \\
\vdots & \vdots & \ddots & \vdots \\
t_1+a(b-1) & t_2+a(b-1) & \cdots & t_{\varphi(a)}+a(b-1) \\
\end{array}

各列の各値は補助定理により異なる組があらわれます。
したがって、各行は正の整数$b$において、互いに素でない列は消す事ができます。

\begin{array}{lllllll}
 t_{11} & t_{21} & \cdots & t_{\varphi(a)1} \\
t_{12}+a & t_{22}+a & \cdots & t_{\varphi(a)t} + a \\
\vdots & \vdots & \ddots & \vdots \\
t_{1\varphi(b)}+a(b-1) & t_{2\varphi(b)}+a(b-1) & \cdots & t_{\varphi(a)\varphi(b)}+a(b-1) \\
\end{array}

したがって、互いに素である正の整数$a,b$において以下の式が成り立ちます。

\varphi(ab) = \varphi(a)\varphi(b)

$\ p$が素数の時、以下の式が成り立ちます。

\begin{align*}
& \varphi(p) = p-1 \\
& \varphi(p^e) = p^e-p^{e-1} 
\end{align*}

$\varphi(p)$の場合、$1$から$\ p$の正の整数で$\ p$の約数は$\ p$だけなので、$\ p-1$個となります。
$\varphi(p^e)$の場合、$\ 1$から$\ p^e$の正の整数で$\ p$の約数は$\ p^e\div p$個なので、$p^e-p^{e-1}$個となります。

整数$\ n$の素因数分解が$n=p_1^{e_1}\times p_2^{e_2}\times \cdots \times p_d^{e_d}$である時、以下の式が成り立ちます。
$\ p_i,1\le i\le d\ $は素数です。

\begin{align*}
n&=p_1^{e_1}\times p_2^{e_2}\times \cdots \times p_d^{e_d} \\
& p_i,1\le i\le d \text{ is prime number.} \\
\varphi(n) &= \varphi(p_1^{e_1})\varphi(p_2^{e_2})\cdots \varphi(p_d^{e_d}) \\
&= (p_1^{e_1}-p_1^{e_1-1})(p_2^{e_2}-p_2^{e_2-1})\cdots (p_d^{e_d}-p_d^{e_d-1}) \\
&= p_1^{e_1}p_2^{e_2}\cdots p_d^{e_d}(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_d}) \\
&= n \prod_{k=1}^{d}(1-\frac{1}{p_k}) \\
\end{align*}

まとめ

$n$を正の整数とする。$n,a$を互いに素である正の整数とする時、以下が成り立ちます。

\begin{align*}
& a^{\varphi(n)} \equiv 1 \pmod{n} \\
& n = \prod_{k=1}^{d}p_k^{e_k} \\
& p_i,1\le i\le d \text{ is prime number.} \\
& \varphi(n) = n \prod_{k=1}^{d}(1-\frac{1}{p_k}) \\
\end{align*}

互いに素である正の整数$a,b$において以下の式が成り立ちます。

\varphi(ab) = \varphi(a)\varphi(b)

カーマイケルの定理(Carmichael function)

オイラーのφ関数では最小値にならないので、さらに一般化したのがカーマイケルの定理です。

カーマイケルの定理(Carmichael function)

$n$と$a$が互いに素である場合、$a^{\lambda(n)} \equiv 1 \pmod{n}$となる$\lambda(n)$を求めます。

$\ n=2^e$の時、以下の式で表されます。

\lambda (2^e) = \left\{ 
\begin{align*}
&1 & \text{if } e = 1 \\
&2 & \text{if } e = 2 \\
&2^{e-2} & \text{if } e \ge 3 \\
\end{align*}
\right.

$\ n=p^e$、$\ p$が奇素数(奇数の素数）の冪乗の時、以下の式で表されます。

\lambda (p^e) = p^{e-1}(p-1)\ 

$\ n=p_1^{e_1} \times \cdots \times p_n^{e_n}$、$\ n$が左記の素因数分解される時、以下の式で表されます。

\lambda (n) = \text{lcm}(\lambda(p_1^{e_1}), \ldots , \lambda(p_n^{e_n}))

(証明)

証明については、以下を参照願います。
（※：なんとなく理解はできましたが、説明できない・・・、誰か易しい解説をお願いします）

Carmichael's Lambda Function
カーマイケルのλ関数と絶対擬素数
巷で話題のカーマイケル数・カーマイケルの定理について

なんとなく

$\lambda(n) \le \varphi(n)$である事はわかると思います。
$\ n$が奇素数の冪乗であれば、$\lambda(n) = \varphi(n)$となります。
合成数の場合は、最小公倍数を計算しているので、$\lambda(n)$は$\varphi(n)$の約数となります。

さいごに

「はじめに」にも書いたとおり、フェルマーの小定理を、一般化したのがオイラーの定理です。
さらに、一般化したのが、カーマイケルの定理です。
暗号をやる上で重要な定理なので、投稿してみました。