今天学习一些欧拉函数的性质，以及重要的数论欧拉定理，当 $a$ 和 $N$ 互质时，有：
$$ a^{\phi(N)} \equiv 1\hskip -.6em \mod N$$
以及今天主要讨论的广义欧拉定理，当 $a$ 和 $N$ 不互质时，有：
$$
a^b \equiv
\left\lbrace\begin{aligned}
&a^b \hskip -.6em\mod N, & 0\leqslant b < \varphi(N) \
&a^{\big(b\hskip -.6em\mod \varphi(N)\big) + \varphi(N)} \hskip -.6em \mod N, &b \geqslant \varphi(N)
\end{aligned}\right.
$$
欧拉函数 $\varphi$
$\varphi(N)$ 等于 $1,2,\cdots,N-1$ 中与 $N$ 互质的数的个数。
欧拉函数的一些性质
【性质 1】 若 $\displaystyle N=p_1^{k_1}p_2^{k_2}\cdots p_s^{k_s}$，则 $\displaystyle \varphi(N)=N\cdot\left(1-\frac{1}{p_1}\right)\cdot\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_s}\right)$
$\hskip 2em$ 证明见 模方程基础之筛法
【性质 2】 若 $X$ 和 $Y$ 是互质的两个正整数，则：$\displaystyle\varphi(X\cdot Y)=\varphi(X)\cdot \varphi(Y)$。
同余类与剩余系
如果 $a \equiv b\hskip -.6em \mod N$，则成 $a, b$ 模 $N$ 同余。
特别地，$\big\lbrace a-kN, a-kN+N, \cdots, a, a+N, \cdots, a+kN \big\rbrace$ 构成一个模 $N$ 的同余类。
如果 $\big\lbrace a_1, a_2, \cdots, a_N\big\rbrace$ 两两模 $N$ 不同余，则称其为模 $N$ 的一组完全剩余系。
如果 $\big\lbrace a_1, a_2, \cdots, a_{\varphi(N)}\big\rbrace$ 两两模 $N$ 不同余且均和 $N$ 互质，则称其为模 $N$ 的一组既约剩余系。
【定理 1】如果 $\gcd(\lambda,N)=1$ 且 $\big\lbrace a_1, a_2, \cdots, a_{\varphi(N)}\big\rbrace$ 是一组模 $N$ 的既约剩余系，
$\hskip 3em$ 则 $\big\lbrace \lambda\cdot a_1, \lambda\cdot a_2, \cdots, \lambda\cdot a_{\varphi(N)}\big\rbrace$ 也是一组模 $N$ 的既约剩余系。
$\hskip 1em$ 【证】
$\hskip 3em$ 因为 $\gcd(\lambda,N)=1$，且由 $\big\lbrace a_1, a_2, \cdots, a_{\varphi(N)}\big\rbrace$ 构成模 $N$ 的既约剩余系，有：$\gcd(a_i, N)=1$。
$\hskip 3em$ 进而有， $\gcd(\lambda\cdot a_i, N)=1$。
$\hskip 3em$ 若 $\lambda\cdot a_i \equiv \lambda\cdot a_j\hskip -.6em \mod N$，则 $\lambda\cdot(a_i -a_j) \equiv 0 \hskip -.6em \mod N$，
$\hskip 3em$ 即 $\lambda \equiv 0\hskip -.6em \mod N$ 或 $(a_i-a_j) \equiv 0\hskip -.6em \mod N$。但这显然是不可能的。
$\hskip 3em$ 故有，$\lambda\cdot a_1, \lambda\cdot a_2, \cdots, \lambda\cdot a_{\varphi(N)}$ 两两模 $N$ 不同余。
$\hskip 3em$ 这就证明了 $\big\lbrace \lambda\cdot a_1, \lambda\cdot a_2, \cdots, \lambda\cdot a_{\varphi(N)}\big\rbrace$ 也是一组模 $N$ 的既约剩余系。
$\hskip 1em$ 【证毕】
数论欧拉定理
如果 $\gcd(\lambda, N)=1$，那么 $\lambda^{\varphi(N)}\equiv 1 \hskip -.6em\mod N$。
这个定理被称为数论欧拉定理（因为欧拉在很多领域有欧拉定理= =，所以加前缀以区分）。
在证明数论欧拉定理之前，先看这个定理。
【定理 2】如果 $\displaystyle ca \equiv cb\hskip -1em\mod N$，那么有 $\displaystyle a\equiv b\hskip -1em\mod\frac{N}{\gcd(c,N)}$。
$\hskip 1em$ 【证】
$\hskip 3em$ 因为 $\displaystyle ca \equiv cb\hskip -1em\mod N$，所以有 $\displaystyle N\mid c\cdot(a-b)$，
$\hskip 3em$ 又因为 $\displaystyle \gcd\left(\frac{N}{\gcd(c,N)},\frac{c}{\gcd(c,N)}\right)=1$，所以必有 $\displaystyle \frac{N}{\gcd(c,N)} \big|~ a-b$。
$\hskip 3em$ 所以，$\displaystyle a\equiv b\hskip -1em\mod\frac{N}{\gcd(c,N)}$
$\hskip 1em$ 【证毕】
【欧拉定理】
$\hskip 1em$【证】
$\hskip 3em$ 如果 $\big\lbrace a_1, a_2, \cdots, a_{\varphi(N)}\big\rbrace$ 是一组模 $N$ 的既约剩余系，
$\hskip 3em$ 由【定理 1】 可知，$\big\lbrace \lambda\cdot a_1, \lambda\cdot a_2, \cdots, \lambda\cdot a_{\varphi(N)}\big\rbrace$ 也是一组模 $N$ 的既约剩余系。
$\hskip 3em$ 所以，$\quad \displaystyle \prod_{i=1}^{\varphi(N)} (a_i \hskip -1em\mod N) \equiv \prod_{i=1}^{\varphi(N)} (\lambda\cdot a_i \hskip -1em\mod N)$
$\hskip 3em$ 即， $\quad \displaystyle \prod_{i=1}^{\varphi(N)} (a_i \hskip -1em\mod N) \equiv \lambda^{\varphi(N)}\prod_{i=1}^{\varphi(N)} (a_i \hskip -1em\mod N)$
$\hskip 3em$ 又因为，$\quad \displaystyle \gcd\left(\prod_{i=1}^{\varphi(N)} (a_i\hskip -1em\mod N), N\right)=1$ 且 $\gcd(\lambda^{\varphi(N)},N)=1$
$\hskip 3em$ 所以由【定理 2】，$\quad \displaystyle \lambda^{\varphi(N)} \equiv 1\hskip -1em\mod N$
$\hskip 1em$【证毕】
如果 $p$ 是一个素数，那么有 $\varphi(p)=p-1$，且：
- 如果 $\gcd(\lambda, p)=1$，由欧拉定理，有：$\displaystyle \lambda^p=\lambda^{\varphi(p)+1}\equiv 1\cdot \lambda\hskip -1em\mod p\equiv \lambda\hskip -1em\mod p$。
- 如果 $\gcd(\lambda, p)\neq 1$，因为 $p$ 是一个素数，则必有 $\displaystyle\gcd(\lambda, p)=p$，所以：$\displaystyle \lambda^p\equiv 0\hskip -1em\mod p\equiv \lambda\hskip -1em\mod p$。
综上，对于任意整数 $\lambda$ 都有 $\displaystyle \lambda^p\equiv \lambda\hskip -1em\mod p$。
这就是著名的费马小定理。
广义欧拉定理
如果 $\gcd(\lambda, N)\neq 1$ 呢？
首先，由于 $\displaystyle \lambda^i\hskip -1em\mod N\in[0,N-1]$，由鸽巢原理可知，必存在 $i(0\leqslant i\leqslant N-1)$ 使得 $\displaystyle \lambda^N\equiv \lambda^i\hskip -1em\mod N$。
可能你会想，那岂不是 $\displaystyle \lambda^{N-i}\equiv 1\hskip -1em\mod N$？
但事实并不是这样的，这样想的读者忽略了 $\gcd(\lambda, N)\neq 1$ 。
由于 $\displaystyle N \big|~ \lambda^i\cdot \left(\lambda^{N-i}-1 \right)$，不难有：$\displaystyle \frac{N}{\gcd(N,\lambda^i)}\big|~\left(\lambda^{N-i}-1\right)$，
所以只能得出 $\displaystyle \lambda^{N-i}\equiv 1\hskip -1em\mod \frac{N}{\gcd(N,\lambda^i)}$。
事实上，由扩展欧几里得定理可知，方程 $\lambda\cdot x+N\cdot y=1\neq \gcd(\lambda,N)$ 无解，
那么就不存在 $\lambda$ 在模 $N$ 意义下的逆元。
进而推知，不存在整数 $b$ 使得 $\displaystyle \lambda^{b+1}\equiv 1\hskip -1em\mod N$，
因为如果存在，那 $\lambda^b$ 就是 $\lambda$ 模 $N$ 意义下的逆元了，与前面的结论矛盾。
尽管如此，由鸽巢原理的分析，我们知道存在一个最小的 $L$ 和一个足够大的整数 $\delta$，使得当 $x\geqslant \delta$ 时，有：$$\lambda^{L+x}\equiv\lambda^x\hskip -1em\mod N$$
接下来，我们将证明当 $N=p_1^{k_1}p_2^{k_2}\cdots p_{s}^{k_s}$ 时，有：$\delta=\max\lbrace k_i\rbrace,(1\leqslant i\leqslant s)$，以及 $L \mid \varphi(N)$。
不妨假设 $N=p^k\cdot X$，其中，$k \geqslant 1$ 且 $\gcd(p^k, X)=1$。
【定理 3】 $\displaystyle \varphi(X) \mid \varphi(N)$
$\hskip 1em$ 【证】
$\hskip 3em$ 因为 $\gcd(p^k,X)=1$，由【性质 2】可知：$\varphi(N)=\varphi(X)\cdot\varphi(p^k)$。
$\hskip 3em$ 所以，$\varphi(X) \mid \varphi(N)$
$\hskip 1em$ 【证毕】
【定理 4】 $\displaystyle p^{\varphi(N)+k} \equiv p^k\hskip -1em\mod N$
$\hskip 1em$ 【证】
$\hskip 3em$ 由于 $\gcd(p,X)=1$，根据欧拉定理，有 $\displaystyle p^{\varphi(X)}\equiv 1\hskip -1em\mod X$
$\hskip 3em$ 所以，存在一个整数 $t$ 使得 $\displaystyle p^{\varphi(X)}=tX+1$
$\hskip 3em$ 于是， $\displaystyle p^k\cdot p^{\varphi(X)}=tX\cdot p^k+p^k$， 即 $\displaystyle p^{\varphi(X)+k}=tN+p^k\equiv p^k\hskip -1em\mod N$
$\hskip 3em$ 不难得出：对于任意整数 $s$ 都满足 $\displaystyle p^{s\cdot\varphi(X)+k} \equiv p^k\hskip -1em\mod N$
$\hskip 3em$ 又由【定理 3】可知，当 $\displaystyle s=\frac{\varphi(N)}{\varphi(X)}$ 时，有：$\displaystyle p^{\varphi(N)+k}\equiv p^k\hskip -1em\mod N$
$\hskip 1em$ 【证毕】
【推论】对于任意非零整数 $s$，都有 $\displaystyle (p^s)^{\varphi(N)+k} \equiv (p^s)^k\hskip -1em\mod N$
$\hskip 1em$ 【证】
$\hskip 3em$ 由【定理 4】可知， $\displaystyle (p^s)^{\varphi(N)+k}=p^{s\cdot\varphi(N)+s\cdot k}\equiv p^{s\cdot k}\hskip -1em\mod N\equiv (p^s)^k\hskip -1em\mod N$
$\hskip 1em$ 【证毕】
【定理 5】 若 $c=a\cdot b$ 满足 $\displaystyle a^{L+x}\equiv a^x\hskip -1em\mod N$ 且 $\displaystyle b^{L+x}\equiv b^x\hskip -1em\mod N$；那么，$\displaystyle c^{L+x}\equiv c^x\hskip -1em\mod N$
$\hskip 1em$ 【证】
$\hskip 3em$ $\displaystyle c^{L+x}=a^{L+x}\cdot b^{L+x}\equiv a^x\cdot b^x\hskip -1em\mod N\equiv c^x\hskip -1em\mod N$
$\hskip 1em$ 【证毕】
【定理 6】 若 $N=p_1^{k_1}p_2^{k_2}\cdots p_s^{k_s}$，对于任意整数 $r$ 满足 $r\geqslant \max\lbrace k_i \rbrace,(1\leqslant i\leqslant s)$
$\hskip 3em$ 若 $\gcd(\lambda,N)\neq 1$， 则 $\displaystyle \lambda^{r+\varphi(N)}\equiv \lambda^r\hskip -1em\mod N$ 成立。
$\hskip 1em$ 【证】
$\hskip 3em$ 将 $\lambda$ 唯一分解定理得，$\displaystyle \lambda=q_1^{a_1}\cdot q_2^{a_2}\cdots q_t^{a_t}$
$\hskip 3em$ 若 $\gcd(q_j,N)=1$，由【欧拉定理】知 $\displaystyle q_j^{\varphi(N)} \equiv 1\hskip -1em\mod N$
$\hskip 5em$ 所以，对于任意整数 $r$ 有： $\displaystyle q_j^{\varphi(N)+r}\equiv q_j^r\hskip -1em\mod N$
$\hskip 3em$ 若 $\gcd(q_j,N)\neq 1$，不妨设 $q_j=p_i$，
$\hskip 5em$ 由【定理 4】可知，当 $r \geqslant k_i$ 时，$\displaystyle q_j^{\varphi(N)+r}\equiv q_j^r\hskip -1em\mod N$ 成立
$\hskip 3em$
$\hskip 3em$ 综上，不难发现，当 $r \geqslant \max\lbrace k_i \rbrace$ 时，$\displaystyle q_j^{\varphi(N)+r}\equiv q^r\hskip -1em\mod N$ 对任意 $1\leqslant j\leqslant t$ 都成立。
$\hskip 3em$ 结合【定理 4】的【推论】有： $\displaystyle (q_j^{a_j})^{\varphi(N)+r}\equiv (q_j^{a_j})^r\hskip -1em\mod N$ 对任意 $1\leqslant j\leqslant t$ 都成立。
$\hskip 3em$ 结合【定理 5】知，当 $r \geqslant \max\lbrace a_i \rbrace$ 时，$\displaystyle \lambda^{\varphi(N)+r}=(q_1^{a_1}\cdot q_2^{a_2}\cdots q_t^{a_t})^{\varphi(N)+r}\equiv\lambda^r\hskip -1em\mod N$
$\hskip 1em$ 【证毕】
【广义欧拉定理】 若 $N=p_1^{k_1}p_2^{k_2}\cdots p_s^{k_s}$，则无论 $a$ 和 $N$ 互质与否，当 $b \geqslant \phi(N)$ 时，都有：
$$a^b \equiv a^{\big(b\hskip -.6em\mod \varphi(N)\big) + \varphi(N)} \hskip -.6em \mod N$$
$\hskip 1em$ 【证】
$\hskip 3em$ 当 $a$ 和 $N$ 互质时，根据【欧拉定理】，结论显然成立。
$\hskip 3em$ 当 $a$ 和 $N$ 不互质时，由于 $\varphi(N)\geqslant p_i^{k_i-1}\geqslant k_i,(1\leqslant i\leqslant s)$，
$\hskip 3em$ 即 $\varphi(N) \geqslant \max\lbrace k_i\rbrace$，结合【定理 6】可知结论成立。
$\hskip 1em$ 【证毕】
练习
| problems | categories | solution |
|---|---|---|
| FJU/Super A^B mod C | 广义欧拉定理 | Code |
Hint
鉴于本人能力有限，有误之处还望指证。
