Carmichael関数

$bc\equiv a\Mod{p}$ となる $c$ をとると $(bc)^n\equiv a^n\Mod{p}$ だから
$$a^n\equiv b^n\Mod{p}\Longleftrightarrow c^n\equiv 1\Mod{p}$$
となる。よって $g$ は $c^n\equiv 1\Mod{p}$ となる最小の正の整数でもあるから
$$a^n\equiv b^n\Mod{p}\Longleftrightarrow g\mid n\Mod{p}$$
となる。
$$p^f\mid\mid (a^g-b^g)$$

次に $e, k$ が
$$p^e\mid\mid k$$
となる正の整数とする。

$$bc\equiv a\Mod{p^{e+f+1}}$$
となる $c$ をとる。
$$(bc)^g\equiv a^g\equiv b^g\Mod{p}$$
から
$c^g\equiv 1\Mod{p}$
となる。$\ell=0, 1, \ldots, e-1$ に対し、
$$c^{p^\ell g}\equiv 1\Mod{p}$$
が明らかに成り立つ。そこで
$$c^{p^\ell g}=Ap+1$$
とおくと、$p$ は奇数なので
$$\begin{split} \frac{c^{p^{\ell +1}g}-1}{c^{p^\ell g}-1}= & \sum_{i=0}^{p-1} c^{i p^\ell g}=\sum_{i=0}^{p-1} (Ap+1)^i \\ = & p+\frac{p(p+1)}{2}Ap+(Ap^2)\sum_{i=2}^{p-1}\binom{i}{2}+\cdots \\ = & p+\frac{p+1}{2}Ap^2+(Ap^2)\sum_{i=2}^{p-1}\binom{i}{2}+\cdots \\ \end{split}$$
より、
$$\frac{c^{p^{\ell +1}g}-1}{c^{p^\ell g}-1}\equiv p\Mod{p^2}$$
となるから
$$p\mid\mid \frac{c^{p^{\ell +1}g}-1}{c^{p^\ell g}-1}$$
が成り立つ。よって
$$p^e\mid\mid \frac{c^{p^e g}-1}{c^g-1}$$
となるから
$$p^{f+e}\mid\mid (c^{p^e g}-1)$$
となる。
$k=p^e s$ とおくと $p\not\mid s$ だから
$$c^{p^e g(s-1)}+\cdots+c^{p^e g}+1\equiv s\not\equiv 0\Mod{p}$$
なので
$$p^{f+e}\mid\mid (c^{gk}-1)=(c^{p^e g}-1)(c^{p^e g(s-1)}+\cdots+c^{p^e g}+1)$$
となる。よって
$$p^{f+e}\mid\mid ((bc)^{gk}-b^{gk})$$
となるが、$bc\equiv a\Mod{p^{e+f+1}}$ より
$$a^{gk}\equiv (bc)^{gk}\Mod{p^{e+f+1}}$$
だから
$$p^{f+e}\mid\mid (a^{gk}-b^{gk})$$
である。

まず $a\equiv 3, 5\Mod{8}$ とする。
$$2\mid\mid (a-1), 2^3\mid\mid (a-1)(a+1)=(a^2-1)$$
である。また $t\geq 0$ に対して
$$a^{2^t}+1\equiv 2\Mod{4}$$
であるから $v\geq 2$ のとき
$$a^{2^v}-1=(a-1)(a+1)\prod_{i=1}^{v-1}(a^{2^i}+1)$$
より
$$2^{v+2}\mid\mid (a^{2^v}-1)$$
である。

次に $a\equiv 1, 7\Mod{8}$ とする。
$a\equiv 1\Mod{8}$ のとき $2^m\mid\mid (a-1)$,
$a\equiv 7\Mod{8}$ のとき $2\mid\mid (a-1)$ となる。また、いずれの場合も
$$2^{m+1}\mid (a-1)(a+1)=a^2-1$$
となる。上と同様に $v\geq 2$ のとき
$$a^{2^v}-1=(a-1)(a+1)\prod_{i=1}^{v-1}(a^{2^i}+1)$$
より
$$2^{v+m}\mid\mid (a^{2^v}-1)$$
である。

最後に
$$\frac{a^d-1}{a^{2^v}-1}=1+a^{2^v}+\cdots+a^{(u-1)2^v}\equiv u\equiv 1\Mod{2}$$
より $2$ が $a^d-1$ を割り切る回数と $a^{2^v}-1$ を割り切る回数は一致するので、定理がいえる。

$$N=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$$
と素因数分解する。 Eulerの定理 および 系 より $i=1, 2, \ldots, k$ に対して
$$a^{\lambda(p_i^{e_i})}\equiv 1\Mod{p_i^{e_i}}$$
となり、$\lambda(N)$ の定義より各 $\lambda(p_i^{e_i})$ は $\lambda(N)$ を割り切るので
$$a^{\lambda(N)}\equiv 1\Mod{p_i^{e_i}}$$
となるから、 中国式剰余定理 より
$$a^{\lambda(N)}\equiv 1\Mod{N}$$
となる。