欧拉定理证明的一点讨论
今天在看HTTPS的相关知识, 然后顺着公钥私钥想到了RSA, 又看到了欧拉定理, 看到阮一峰博客中并没有欧拉定理证明的相关部分, 想着是不是可以证明一下, 就花了许久考虑了一种证明方案, 也希望有心人看到了可以指出问题.
本文中除了证明部分, 其余部分与RSA算法原理（一）一致, 对欧拉定理 有任何理解问题请移步阮一峰的博客.
可以直接跳到证明部分
几个基础概念
互质关系
如果两个正整数,除了1以外,没有其他公因子. 我们就称这两个数是互质关系(coprime). 比如, 15和32没有公因子, 所以它们是互质关系. 这说明, 不是质数也可以构成互质关系.
应用互质关系可以得到以下结论:
任意两个质数构成互质关系, 比如13和61.
一个数是质数, 另一个数只要不是前者的倍数, 两者就构成互质关系, 比如3和10.
如果两个数之中, 较大的那个数是质数, 则两者构成互质关系, 比如97和57.
1和任意一个自然数是都是互质关系, 比如1和99.
p是大于1的整数, 则p和p-1构成互质关系, 比如57和56。
p是大于1的奇数, 则p和p-2构成互质关系, 比如17和15。
欧拉函数
任意给定正整数n, 请问在小于等于n的正整数之中, 有多少个与n构成互质关系? (比如, 在1到8之中, 有多少个数与8构成互质关系?) 计算这个值的方法就叫做欧拉函数, 以$\phi(n)$表示. 在1到8之中, 与8形成互质关系的是1, 3, 5, 7, 所以$\phi(8) = 4$.
$\phi(n)$的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论。
第一种情况
如果n=1, 则$\phi(1) = 1$. 因为1与任何数(包括自身)都构成互质关系.
第二种情况
如果n是质数, 则$\phi(n)=n-1$. 因为质数与小于它的每一个数, 都构成互质关系. 比如5与1, 2, 3, 4都构成互质关系.
第三种情况
如果n是质数的某一个次方, 即$n = p^{k}$ (p为质数, k为大于等于1的整数), 则
$$\phi(p^k) = p^k - p^{k-1}$$
比如$\phi(8) = \phi(2^{3}) =2^{3} - 2^{2} = 8 -4 = 4$ .
这是因为只有当一个数不包含质数p, 才可能与n互质. 而包含质数p的数一共有p^(k-1)个. 即1×p、2×p、3×p、…、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。
上面的式子还可以写成下面的形式：
$$\phi(p^k) = p^k - p^{k-1} = p^{k}(1 - \frac{1}{p}) $$
可以看出, 上面的第二种情况是 k=1 时的特例.
第四种情况
如果n可以分解成两个互质的整数之积.
$$n = p1 × p2$$
则
$$\phi(n) = \phi(p1p2) = \phi(p1)\phi(p2)$$
即积的欧拉函数等于各个因子的欧拉函数之积. 比如,$\phi(56)=\phi(8×7)=\phi(8)×\phi(7)=4×6=24$.
这一条的证明要用到”中国剩余定理”, 这里就不展开了, 只简单说一下思路:如果a与p1互质($a<p1$). b与p2互质$(b<p2)$, c与p1p2互质$(c<p1p2)$, 则c与数对 (a,b) 是一一对应关系. 由于a的值有$\phi(p1)$种可能, b的值有$\phi(p2)$种可能, 则数对(a,b) 有$\phi(p1)\phi(p2)$种可能，而c的值有$\phi(p1p2)$种可能，所以$\phi(p1p2)$就等于$\phi(p1)\phi(p2)$.
第五种情况
因为任意一个大于1的正整数, 都可以写成一系列质数的积.
$$n = p_{1}^{k1}p_{2}^{k2} … p_{r}^{kr}$$
根据第4条的结论，得到
$$ \phi(n) = \phi(p_{1}^{k1})\phi(p_{2}^{k2}) … \phi(p_{r}^{kr}) $$
再根据第3条的结论，得到
$$ \phi(n) = p_{1}^{k1}p_{2}^{k2} … p_{r}^{kr}(1-\frac{1}{p1})(1-\frac{1}{p2})…(1-\frac{1}{pr}) $$
也就等于
$$ \phi(n) = n(1-\frac{1}{p1})(1-\frac{1}{p2})…(1-\frac{1}{pr}) $$
这就是欧拉函数的通用计算公式。比如，1323的欧拉函数，计算过程如下：
$$ \phi(1323) = \phi(3^3 \times 7^2) = 1323(1-\frac{1}{3})(1-\frac{1}{7}) = 756 $$
欧拉定理
如果两个正整数a和n互质，则n的欧拉函数$\phi(n)$可以让下面的等式成立： $$ a^{\phi(n)} \equiv 1(mod\ n) $$
原博客中并没有相关的证明部分, 因此, 我在此考虑了一种证明方法, 欢迎大家提出意见:
证明部分
根据欧拉定理我们做如下假设, 其中G为常数, 我们要证明的就是G=1.
$$ a^{\phi(n)} = nX + G $$
其中X为商, 表示我们未知.
由互质的定义可知$a^{\phi(n)}$与nX+G-1互质, 我们将nX+G-1带入欧拉函数替换n, 将 $a^{\phi(n)}$带入, 替换a.
$$ ({a^{\phi(n)}})^{\phi(nX+G-1)}=(nX+G-1)Y+G $$
Y为另一个商, 表示我们未知
进行幂的变换后如下:
$$ (a^{\phi(nX+G-1)})^{\phi(n)}=(nX+G-1)Y+G $$
a的任意次幂与n是一定互质的, 也就是说, 上述等式也可以写成如下形式
$$(a^{\phi(nX+G-1)})^{\phi(n)}=nZ+G$$
Z为另一个未知商, 连接两个等式:
$$ nZ+G=(nX+G-1)Y+G$$
简化后:
$$nZ+G=nXY+(G-1)Y+G$$
所以就会有
$$ \begin{matrix} Z = XY \ (G-1)Y = 0 \end{matrix} $$
X, Y, Z虽然未知, 但由于$a^{\phi(n)} > n$, 所以X,Y,Z一定不会是0, 因此可得出G = 1.
欧拉定理得证.
额外讨论
上面的计算的确可以得出G=1这个结论, 但还是有一些不严谨, 我提出以下两个问题,
如果读者有什么想法我们可以交流.
- $a^{\phi(n)}$与nX+G+1也互质, 为什么不用nX+G+1进行代换?
- 我们凭什么这样认为$a^{\phi(n)} = nX + G$, 为什么G是一个常数, G如果不是常数会怎么样?