欧拉函数(一)定义以及性质,求法

定义:

欧拉函数\phi (N) 的含义为1到N之内与N互质的个数.

公式:\phi(N) = N*\prod\nolimits_{i=a_1}^{a_n}(1 - \frac{1}{p^{a_i}} ) ,设N= p_1^{a1}* p_2^{a2}*.. *p_n^{an}

公式的理解:N= p_1^{a1}* p_2^{a2}*.. *p_n^{a_n}。\\互质的含义是a,b没有公共的质因子,所以我们求的就是1到N之内质因子中不含\{ p1,p2, ...,p_n\}的数的个数.\\1 到 N内有\frac{1}{p}个数能被p整除,那么有(1-\frac{1}{p})个数不能被p整除.\\那么根据乘法原理，公式就出来了

性质:

①对于质数:φ(n)=n−1


②积性函数:当gcd(a,b) = 1时,\phi(a*b) = \phi(a)*\phi(b)

解释：将φ(n)展开成计算式，a,b没有共同质因子，那么 φ(a)和φ(b)中没有共同的pi,所以得证.


③设p为质数,n=p^k,那么\phi(n)=(p-1)*p^{k-1}

解释:1到p^k中只有p的倍数与p^k不互质.\\p^k中p的倍数有p^k/p=p^{k-1}个.\\所以\phi(p^k)=p^k - p^{k-1} =p^{k-1})*(p-1)


④小于n的与n互质的数的和为sum=\frac{\phi(n)*n}{2}

gcd(n,i) = 1时,gcd(n,n-i) = 1

反证法:设gcd(n,n-i) = k(k > 1),那么n%k=0且(n-i)%k = 0,所以 那么i%k == 0 

,推出gcd(n,i) = k. 与原结论相反，得证,

所以与n互质的数成对存在,且两两之间和为n

所以sum=互质个数/2*n


5.1:若p为质数且 n \equiv 0(mod \ p).则\phi(n*p)=\phi(n)*p

还是需要证明一个东西：gcd(n,i) = 1 则gcd(n,n+i) = 1;

设gcd(n,n + i) = k(k!=1).设i = ka1,n+i=ka2,(a2 > a1),则n = k(a2 - a1).

则gcd(n,i) = gcd(k(a2 - a1),ka1) = k (因为gcd(a1,a2) = 1 所以gcd(a2 - a1 , a1) = 1(这个已经证明了),所以gcd(k(a2-a1),ka1) = k)。得证

这个证明了就很好办了，因为n是p的倍数，所以n*p并不增加新的质数.所以1~n内与n互质的数一样与n*p互质。

然后设ai为与n互质的数,那么 ai + kn一样与n互质(也就是n*p),所以 φ(n*p) = φ(n)*p;

注：这里也可以根据计算式来分析.

很简单,(素数与一个数不是倍数，那么两者就是互质,根据性质2可得.


⑥n = \sum\nolimits_{d|n}\phi(d) //先码着


⑦欧拉降幂以及广义欧拉降幂


求法:

一.根据公式 可以利用质因子分解来求单个数N的欧拉函数.(太简单了这里不放代码了)

二.求1~N的欧拉函数:借助欧拉筛(利用性质5.1 5.2)


©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • 2018-06-05
    关于使用python实现RSA加密解密 一、非对称加密算法 1、乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何...
    ttaymm阅读 978评论 0赞 0
  • RSA 算法简介
    一、RSA的历史 1976 年以前，所有的加密方法都是同一种模式： （1）甲方选择某一种加密规则，对信息进行加密；...
    开着保时捷堵你家门口阅读 2,410评论 0赞 1
  • 欧拉定理
    欧拉函数的定义:在数论中，对于正整数N,少于或等于N ([1,N]),且与N互质的正整数(包括1)的个数，记作φ(...
    Gitfan阅读 1,649评论 0赞 0
  • 雨的世界
    如果这是我的老家就好了 我这样想着 我一定不顾一切冲进雨里 任天雷滚滚 将我的一切交给天地 用力敞开手脚 去拥抱自...
    小侃侃而谈阅读 280评论 0赞 2
  • 把建筑画成这样，也是没谁了
    想出去旅游还没钱？ 那就去看画呗！ 人少、安静、好看 还不费体力 能把建筑画成这样 也是没谁了 来自日本画家 Hi...
    艺伙阅读 281评论 0赞 2