区块链中的数学 -欧拉定理和欧拉函数

写在前面

上一节介绍了RSA加解密过程，用到了欧拉定理等知识点。这一节详细说说欧拉定理及其相关。

欧拉定理

这里所说的欧拉定理是指数论中的欧拉定理，也称欧拉函数定理。该定理被认为是数学世界中最美妙的定理之一。 欧拉这个人成就非常多，在其他其他领域，如平面几何中的欧拉定理、多面体欧拉定理等，不在本文范畴。 欧拉定理表述很简单：若n,a为正整数，且n,a互质，则 $a^{\varphi (n)} \equiv 1\ mod\ n$ 上式中$\varphi (n)$代表欧拉函数： 指1到n−1中（也就是[1,n−1]）且与n互质的整数的个数. 证明过程类似费马小定理大致如下： 记小于 n 且与 n 互质的正整数集合为： $R =x_1,x_2,x3,...,x{\varphi (n)}$ 可知R中元素各不相同。 令集合：$S =ax_1 \ mod\ n,ax2 \ mod\ n,...,ax{\varphi (n)} \ mod\ n$ 即R中每个元素乘以a模n. S中元素满足如下性质：

1. S中元素两两不相同 反证法： 假设存在第i,j两个元素相同（i!=j），即$ax_i \equiv ax_j(mod\ n)$ 由于a,n互质，两边消去a, 得$x_i \equiv x_j(mod\ n)$， $x_i$和 $x_j$是小于n且与n互质的数不可能相同，所以假设不成立，S中元素两两不相同。

2. S中元素均与n互质 对于S中任意元素$ax_i(mod\ n)$，由于a与n互质，$ax_i$与n互质【R集合性质】，所以 $ax_i$与n互质。 这一结论看起来理所当然，数学是不相信直觉的，可以通过贝祖定理（注：有时也翻译为裴蜀定理）严谨证明。 下面看一下具体证明过程：

   已知a,b互质,a,c互质,证明a与bc乘积互质： 根据互质的定义： gcd(a,b)=1等价于存在整数u、v使得 ua + vb = 1(贝祖定理，大家可以自行查阅，此处不做扩展) 可得如下： gcd(a,b)=1推出存在整数u、v使得 ua + vb = 1. gcd(a,c)=1推出存在整数s、t使得 sa + tc = 1. 可得： bc = (1-ua)/v * (1-sa)/t. vtbc = (1-ua)(1-sa)=1-ua-sa+us$a^2$. 移位整理： a(u+s-usa)+bcvt = 1. 所以: gcd(a,bc) = 1.

利用上述结论，可得 $ax_i$与n互质，即gcd($ax_i$,n) = 1, 结合公因子性质 $gcd(ax_i,n) = gcd(n,ax_i\ (mod\ n)) = 1$

得证S中任意元素$ax_i\ (mod\ n)$，与n互质且小于n. 综合1，2这个结论，可知集合R，S 中元素都是互不相同且与n互质的，同为模n简化剩余系，二者是等价的。

两个集合中元素相乘也相等： $x_1x_2...x_{\varphi (n)} \equiv ax_1 ax2 ...ax{\varphi (n)}(modn) \equiv a^{\varphi (n)}x_1x2...x{\varphi (n)}(modn)$ 因为$x_1,x2,...,x{\varphi (n)}$均与n互质，乘积也与n互质【见祖定理相关证明】，两边可消除得证： $a^{\varphi(n)} \equiv 1\ mod\ n$

欧拉函数性质

欧拉函数具有如下性质：

1. φ(1) = 1， 1与任何数（包括自身）都构成互质关系

2. n是质数，则 φ(n) = n-1 因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。

3. n是质数的某一个次方，即 n = $p^k$(p为质数，k为大于等于1整数)，则 $\varphi(n)=\varphi(p^k)=p^k-p^{k-1}=p^k(1-p^{-1})$ 因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有$p^{k-1}$个， 即1×p、2×p、3×p、...、$p^{k-1}$×p，把它们去除，剩下的就是与n互质的数。 例 φ(8) = φ($ 2^3$) = $ 2^3$- $ 2^2$= 8 -4 = 4。

4. n可以分解成两个互质的整数之积 n = p q 则φ(n) = φ(p) φ(q) 即欧拉函数是积性函数【注：积性函数：对于数论函数 f(n) 不恒等于0，当 gcd(m,n) = 1 时，满足 f(mn) = f(m)f(n) ，则称 f(n) 为积性函数】 这个性质证明利用了中国剩余定理，后续单独介绍,只简单说一下思路： 如果a与p互质(a<p)，b与q互质(b<q)，c与pq互质(c<pq)，则c与数对 (a,b) 是一一对应关系。 由于a,b的值分别有φ(p)，φ(q)种可能，则数对 (a,b) 有φ(p)φ(q)种可能， 而c的值也有φ(pq)种可能，所以φ(pq)就等于φ(p)φ(q)。

5. 通用欧拉函数公式，n为大于1整数， 根据质因子唯一分解定理：$n =p_1^{k1} p_2^{k2} ... p_r^{kr} $ $p_1,p_2,p_r$ 是质数。根据性质4， $\varphi(n) = \varphi(p_1^{k1}) \varphi(p_2^{k2}) .. \varphi(p_r^{kr})$ 根据性质3, $\varphi(n) = p_1^{k1}p_2^{k2} ... p_r^{kr}(1-p_1^{-k1})(1-p_2^{-k2})...(1-p_r^{-kr})$ 即$\varphi(n) = n (1-p_1^{-1})(1-p_2^{-1})...(1-p_r^{-1})$ 例：$\varphi(63) = \varphi(3^2*7^1) = 63 (1-1/3)(1-1/7) = 36$

6. n可以分解成两整数之积 n = p * q，但p, q不互质，gcd(p,q)=d

φ(n) =φ(pq)= dφ(p)φ(q)/φ(d)

特别地，当gcd(p,q)=p，则 φ(n) = φ(pq) = pφ(q)

小结

本节主要介绍了欧拉定理和欧拉函数的性质，欧拉定理是费马小定理的扩展，根据欧拉函数性质2, n是质数时退化成费马小定理。在研究欧拉定理及欧拉函数过程中用到了贝祖定理，中国剩余定理等。下一节详细说明。

好了，下一节讲中国剩余定理以及欧拉函数性质4的推导。

欢迎关注公众号：blocksight