欧拉函数

什么是欧拉函数?就是φ(x),定义:φ(x)是小于x的所有1<=a_i<=x且gcd(a_i,x)=1的数的个数;

性质:φ(x)<=x-1(当且x为素数是取等号)即当x为素数时φ(x)=x-1

如果n,m都是质数,那么φ(n*m)=φ(n)*φ(m)=(n-1)(m-1);

如果x为奇数,那么φ(2x)=φ(x);这个其实用简单的代换就知道,φ(2x)=φ(2)*φ(x);φ(2)=1。。这么水......

即

p是每一步分解出的质数,n最大为sqrt(x),且max(n)<log₂n

φ(p^k)=p^k-p^k-1=(p-1)*p^k-1①其中p是质数

证明;在0<=a_i<=p^k中有p^k-1个a_i%p=0的数,用容斥即可得到。①得证

a^φ(x)≡1 (mod x)当x为质数是即为费马小定理..

EXT欧拉函数

a^x≡a^{x%φ(m)+φ(m)}(mod m)a为任意整数,x>=φ(m);a与m不一定互素

by:s_a_b_e_r

尝试整理一下楼上的定理（其实是自己看晕了x

定义: φ(x)是小于x的所有1<=a_i<=x且gcd(a_i,x)=1的数的个数;

求欧拉函数值：或

　　　　　　　（对于任意元素p_i，都有x%p_i==0，且p_i≠p_j）

性质: 1.φ(x)<=x-1(当且仅当x为素数时取"=")

　　　2.如果n,m互质,那么φ(n*m)=φ(n)*φ(m)

　　　　P.S.如果x为奇数,那么φ(2x)=φ(2)*φ(x)=1*φ(x)=φ(x)

　　　3.如果一个数是质数p的k次方，那么有φ(p^k)=p^k-p^k-1=(p-1)*p^k-1

a^φ(x)≡1 (mod x) (a、x互质)

当x为质数时，φ(x)=x-1，即a^x-1≡1 (mod x) （=费马小定理）

a^x≡a^{x%φ(m)+φ(m)}(mod m)

条件：a为任意整数,x>=φ(m);

注：此处a与m不一定互素

以上都是抄的s的

by:wypx