写在前面
上一节介绍了中国剩余定理并加以证明。有了中国剩余定理的基础，我们来看欧拉函数的积性证明和中国剩余定理的扩展。本节之后，我们可以重回RSA主题。
欧拉函数的积性证明
在欧拉定理和欧拉函数一节中，提到欧拉函数是积性函数【注：积性函数：对于数论函数 f(n) 不恒等于0，当 gcd(m,n) = 1 时，满足 f(mn) = f(m)f(n) ，则称 f(n) 为积性函数。如果不要求m,n互质，则f(n) 为完全积性函数 】
欧拉函数积性性质：φ(mn) = φ(m) * φ(n)
-
中国剩余定理证明法
用中国剩余定理可以证明，证明的思路是建立这样一种一一对应的关系：
\<a, b> <---> x
其中正整数a小于m，并且gcd(a, m) = 1，
正整数b小于n并且gcd(b, n) = 1，
这里的整数x要满足： 0< x < mn && gcd(mn, x) = 1。那么x的个数就是φ(mn)的值。
-
证明过程如下：
（1）根据中国剩余定理，如果m和n互素，那么关于未知量x的方程组:
$
\begin{cases}
x=a\ mod\ m\
x=b\ mod\ n
\end{cases}
$
当0 <= x < m * n时存在并且仅存在一个解。
如果m, n相同，但是a, b不同，那么上述方程组的解x一定不同。
下面证明求满足gcd(m * n, x) = 1条件的x与求满足gcd(m, a) = 1且gcd(n, b) = 1条件的<a,b> 是等价的。
（2)证明gcd(m, a) = 1且gcd(n, b) = 1是gcd(mn, x) = 1的充分必要条件
<2.1> 证明充分性：
gcd(m, a) = 1且gcd(n, b) = 1是gcd(mn, x) = 1的充分条件：
由x=a mod m 可得:
x = k * m + a
由公约数性质：gcd(x, m) = gcd(m, a) = 1
同理可得：gcd(x, n) = gcd(n, b) = 1
所以：gcd(mn, x) = 1 【注：参见欧拉函数性质2相关】
从而证明了充分性。
<2.2>证明必要性
反正法证明：
gcd(m, a) = 1且gcd(n, b) = 1是gcd(mn, x) = 1的必要条件：
假设gcd(a, m) = k > 1，由此可得：
a = a' * k;
m = m' * k
得到：x = k' m + a = k' k m' + k a' = k (k' m' + a')
所以 gcd(x, m) = k > 1。
同理，如果gcd(b, n) > 1， 那么gcd(x, n) > 1。
所以gcd(x, mn) > 1 与假设条件（x与mn互质）矛盾。
所以x和mn互素的必要条件是：a和m互素且b和n互素。
上述结论表明，求x就是求等价数对(a, b)的值 二者建立起一一对应的关系的，有多少个(a, b)，就有多少个对应的x。
符合条件的a个数是 φ(m),
符合条件的b的个数是 φ(n).
于是x可取的个数为：φ(m) * φ(n) = φ(mn)
到这里证明了欧拉函数的积性表达。
- 欧拉函数通式证明法
还有一种证明方式使用欧拉函数通式来证明的，有人说是不对的，理由是欧拉函数通式的推导用到了积性函数的性质【前篇欧拉函数性质5就是这样推导的】，属于循环论证。
这种说法是片面的，因为欧拉函数通式的推导可以使用积性函数的性质，也可以不使用。
下面举出一种不使用积性函数的性质推导的方法：
设$p_1,p_2,...,p_k$ 是n的素因子【质因子唯一分解定理保证一定存在】。
那么1到n中与n不互质的数的个数为：
$n/p_1 + n/p_2 +...+ n/p_k - n/(p_1p_2)- n/(p_2p3)- ... - n/(p{k-1}p_k) - n/(p_1p_2p3) - ... - n/(p{k-2}p_{k-1}p_k)- ...+ n/(p_1,p_2,...,p_k)$
所以与n互质的数个数为：
$\varphi(n) = n-(n/p_1 + n/p_2 + n/p_k - n/(p_1p_2)- n/(p_2p3)- ... - n/(p{k-1}p_k) - n/(p_1p_2p3) - ... - n/(p{k-2}p_{k-1}p_k)- ...+ n/(p_1,p_2,...,p_k) ) = n *(1-p_1^{-1})(1-p_2^{-1})...(1-p_k^{-1})$
下面用该通式来证明欧拉函数的积性：
$\varphi(m) \varphi(n)=m(1-p_1^{-1})(1-p_2^{-1})...(1-p_k^{-1}) * n(1-{p'}_1^{-1})(1-{p'}_2^{-1})...(1-{p'}_k^{-1})$
其中$p_1,p_2,...p_k$为m的质因数，${p'}_1,{p'}_2,...{p'}_k$为n的质因数， 而m,n无公因数， 所以$p_1,p_2,...p_k$，${p'}_1,{p'}_2,...{p'}_k$互不相同，
所以$p_1,p_2,...p_k$，${p'}_1,{p'}_2,...{p'}_k$均为mn的质因数
且为mn质因数的全集， 因此：
$\varphi(m) \varphi(n)=mn(1-p_1^{-1})(1-p_2^{-1})...(1-p_k^{-1})(1-{p'}_1^{-1})(1-{p'}_2^{-1})...(1-{p'}_k^{-1})$
所以φ(mn)=φ(m)φ(n)。
这种证明法更易理解！
中国剩余定理的扩展
上一节说到的中国剩余定理是经典的范式，要求方程组中两两互质。如果不一定两两互质的情况，如何处理呢？
这里用到了剩余定理的扩展
$\begin{cases}
x=a_1\ mod\ m_1 \
x=a_2\ mod\ m_2 \
...\
x=a_2\ mod\ m_2
\end{cases}$
求解过程：
假设已经求出前k-1个方程组成的一个解为x,
且$M=\prod_{i=0}^{k-1}m_i$
则前k-1个方程的方程组通解为:
x + i * M (i∈Z)
那么引入第k个方程后的方程组， 我们要求得一个整数i，使得
$x + i * M \equiv a_k\ mod\ m_k$
即 $i * M \equiv a_k-x\ mod\ m_k$
到这里可以用扩展欧几里算法【参见历史文章】得求解i
若该同余式无解，则整个方程组无解。
小结
本节主要介绍了欧拉函数积性证明和扩展剩余定理，扩展剩余定理应用更加广泛。
关于剩余定理和扩展的代码实现，可以很容易找到，文中没有列出。
剩余定理扩展没有特别详细描述，是基于大家很好理解经典剩余定理的前提，如有必要后续在单独详诉，在此不再赘述。
好了，有了这些铺垫，下一篇继续回到RSA主题。
欢迎关注公众号：blocksight
