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

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

写在前面

上一节介绍了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

本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

  • 发表于 2020-06-18 14:54
  • 阅读 ( 737 )
  • 学分 ( 0 )
  • 分类:入门/理论

0 条评论

请先 登录 后评论
blocksight
blocksight

78 篇文章, 2196 学分