既然前面已经有谈及费马小定理和欧拉函数的文章，这里顺理成章地便可以推导费马-欧拉定理。

同样地，由于不懂数论/群论，维基百科对这个定理的证明我是看不懂的。其实我多多少少是想效法欧拉当年的做法，用简单的初等数学语言来描述重要的数学定理。

从两数互质说起——关于欧拉函数

欧拉函数的初等数学证明在前面的文章已经有了，这里就不赘述了。先摆出欧拉函数的结论：小于正整数\(n = \prod_{i=1}^r p_i^{k_i}\)且与它互质的正整数、有\(\phi(n) = n \prod_{i=1}^r (1-\frac{1}{p_i})\)这么多个。

设集合\(R = \{x_1, x_2, …, x_{\phi(n)}|x_i \perp n, 0 \lt x_i \lt n\}\)为与n互质且小于n的所有正整数，由于取模预算的性质，当\(x_i \lt n\)，肯定有\(x_i \mod n = x_i\)。

那么，当一个正整数y如果大于n、且与n互质，那么它对n取模的值将会是什么？

我们设\(y = tn + m, t \geq 1, 0 \lt m \lt n, y \perp n\)。由于\(tn\)肯定不能与n互质，所以如果要y能够与n互质，必然有m和n互质，即\(m \perp n\)。我们再观察m的性质：\(m \perp n, 0 \lt m \lt n\)，m的定义与\(x_i\)相同，那么便可以直接判断得出：\(y \mod n = m \in R\)。

这其实便证明了，只要一个正整数u与n互质，不论它多大，肯定都有\((u \mod n) \in R, u \perp n\)。

另一方面，如果有两个正整数u、v分别与n互质，那么肯定也有\((uv \mod n) \in R, u \perp n, v \perp n\)。

为什么呢？设p代表素因数、\(u = \prod_{f=1} p_f^{k_f}, v = \prod_{g=1} p_g^{k_g}, n = \prod_{i=1} p_i^{k_i}\)，再设\(F = \{…,p_f\}\)为u的素因数的集合、\(G = \{…,p_g\}\)为v的素因数的集合、\(I = \{…,p_i\}\)为n的素因数的集合。由于\(u \perp n, v \perp n \Leftrightarrow F ∩ I = \varnothing, G ∩ I = \varnothing\)，即F与I没有交集、G与I也没有交集。基于集合的基本操作，F和G的并集肯定也与I没有交集，即\((F∪G) ∩ I = \varnothing \Leftrightarrow uv \perp n\)，所以\((uv \mod n) \in R\)。

取模运算的乘法结合率

对于任意正整数\(z_1, z_2\)，它们的乘积对n取模等价与它们分别对n取模后相乘、再对n取模：\(z_1 z_2 \mod n = \{(z_1 \mod n)(z_2 \mod n)\} \mod n\)。

我们可以设\(z_1 = t_1 n + m_1, z_1 \mod n = m_1, z_2 = t_2 n + m_2, z_2 \mod n = m_2\)，于是有：
\(\begin{aligned}
z_1 z_2 \mod n &= \{(t_1 n + m_1)(t_2 n + m_2)\} \mod n \\
&= (t_1 t_2 n^2 + m_1 t_2 n + m_1 m_2) \mod n \\
&= m_1 m_2 \mod n \\
&= \{(z_1 \mod n)(z_2 \mod n)\} \mod n \\
\end{aligned}\)

对于多个整数相乘的情况结合率也是可以适用的。

费马-欧拉定理

基于上述结论，当任意与n互质的正整数a与集合R中的元素相乘，肯定会得到一个新集合\(AR = \{ax_1, ax_2, …, ax_{\phi(n)}|a \perp n, x_i \perp n, ax_i \perp n, 0 \lt x_i \lt n\}\)，集合中的每一个元素肯定都与n互质。而且也不难想象，集合R和集合AR的每个元素直接相乘得出来的数，肯定也会与n互质，即：

• \(\prod_{i=1}^{\phi(n)} x_i \perp n, (\prod_{i=1}^{\phi(n)} x_i \mod n) \in R\)；
• \(\prod_{i=1}^{\phi(n)} ax_i \perp n, (\prod_{i=1}^{\phi(n)} ax_i \mod n) \in R\)。

观察集合AR中的每个元素，由于\(ax_i \perp n, ax_i \mod n = x_j \in R, 1\leq j\leq \phi(n)\)，所以各不相同的\(x_i\)乘以a后对n取模后的值肯定也各不相同，且由于集合AR对n取模后的大小仍然为\(\phi(n)\)，于是肯定有：
\(\begin{aligned}
AR \mod n &= \{(ax_1 \mod n), (ax_2 \mod n), …, (ax_{\phi(n)} \mod n)\} \\
&= \{…,x_j|1\leq j\leq \phi(n), x_j \in R\}
\end{aligned}\)

集合AR对n取模后，实际上就是集合R的重新排列（顺序有可能不一样）。但由于这里讨论的集合都是无序集合，所以便有\(AR \mod n = R\)，于是有：
\(\begin{aligned}
&\{AR \mod n\} \mod n = R \mod n \\
&\Rightarrow \{(ax_1 \mod n)(ax_2 \mod n)…(ax_{\phi(n)} \mod n)\} \mod n = \{x_1 x_2 …x_{\phi(n)}\} \mod n \\
&\Rightarrow (ax_1 ax_2 …ax_{\phi(n)}) \mod n = (x_1 x_2 …x_{\phi(n)}) \mod n \\
&\Rightarrow \prod_{i=1}^{\phi(n)} ax_i \mod n = \prod_{i=1}^{\phi(n)} x_i \mod n \\
&\Rightarrow (a^{\phi(n)} \cdot \prod_{i=1}^{\phi(n)} x_i) \mod n = \prod_{i=1}^{\phi(n)} x_i \mod n \\
&\Rightarrow \{(a^{\phi(n)} \mod n)(\prod_{i=1}^{\phi(n)} x_i \mod n)\} \mod n = \{(1 \mod n)(\prod_{i=1}^{\phi(n)} x_i \mod n)\} \mod n \\
&\Rightarrow (a^{\phi(n)} \mod n) = (1 \mod n) \\
&\Rightarrow a^{\phi(n)} \mod n = 1
\end{aligned}\)

我们再转换一下记号方法，便可以得到费马-欧拉定理：当正整数a与n互质，有\(a^{\phi(n)} \equiv 1 \pmod{n}, a \perp n, a \in \mathbb{Z}^+, n \in \mathbb{Z}^+\)。

不难看出，费马-欧拉定理就是费马小定理的一般化推广。当p是素数，\(\phi(p) = p-1\)，任何正整数a都会与p互质，所以有\(a^{p-1} \equiv 1 \pmod{p}\)。

应用

在讨论费马小定理的文章里已经提到，费马小定理可以用于快速运算指数函数对一个素数取模，即一个针对素数的mod_pow操作。由于费马-欧拉定理是费马小定理的推广，所以也可以用于实现快速mod_pow操作，而这次底数变成了任何正整数——可应用的范围相当于无限阔了。

试想有一个数\(a^k\)，幂数k十分大。如果我们只需要\(a^k\)的个位数，如何快速得到呢？假设\(n = 10\)，且n与a互质。那么，便有\(a^{\phi(n)} \equiv 1 \pmod{n}\)。再设\(k = \phi(n) \cdot t + s\)，那么便会有\(a^k = a^{\phi(n) \cdot t + s} = (a^{\phi(n)})^t \cdot a^s \equiv 1^t a^s \equiv a^s \pmod{n}\)。可以想象得到，s远小于k，计算过程便会少很多。

为何执着于用初等数学对定理进行解释

其实，上面的推导过程，如果用数论、整数模n乘法群等概念进行，是等价的——构造集合R和AR就是那些高等概念的底层过程。高深的理论、辞藻往往会让人忘记背后的细节。在这些过程中抓住核心过程、去芜存精，从来都是思维锻炼的最佳方法——看似遥远却是最便捷的方法。不受华丽词汇影响的思维内核，负担最小。

其实这个学习过程对于我自身来说也是喜出望外的——因为我从来都不觉得自己有能力去理解费马小定理、欧拉函数、费马-欧拉定理这些重要的东西。但事实上我走过来了。我相信其他只要对数学还是抱有基本兴趣的人、即便像我一样只有初等数学水平，也是可以继续不断一路往前的。共勉之。

bruce天地不仁，以万物为刍狗

微信支付

支付宝

PayPal链接

https://paypal.me/xieweiking