数论基础——欧拉函数

mind

数论基础——欧拉函数
就是对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n) 。


欧拉函数的通式：φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn)

其中p1, p2……pn为n的所有质因数，n是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。

欧拉函数的一些性质：

① 当m,n互质时，有phi（m*n）= phi（m）*phi（n）；

② 若i%p==0，有phi（i*p） = p * phi(i)；

③ 对于互质x与p，有x^phi§≡1（mod p),因此x的逆元为x^(phi§-1)，即欧拉定理。

（特别地，当p为质数时，phi（p）=p-1,此时逆元为x^(p-2)，即费马小定理）

④ 当n为奇数时，phi(2n)=phi(n)

⑤ 若x与p互质，则p-x也与p互质，因此小于p且与p互质的数之和为phi(x)*x/2;

⑥N>1，不大于N且和N互素的所有正整数的和是 1/2 *N *eular(N)。

⑦若(N%a == 0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;

⑧若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);

————————————————

版权声明：本文为CSDN博主「浦柳人」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。

原文链接：https://blog.csdn.net/weixin_43237242/article/details/97388834