数论，对正整数n，欧拉函数是小于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。

欧拉定理是用来阐述素数模下，指数同余的性质。

欧拉定理：对于正整数N，代表小于等于N的与N互质的数的个数，记作φ(N)

例如φ(8)=4，因为与8互质且小于等于8的正整数有4个，它们是：1,3,5,7

欧拉定理还有几个引理，具体如下：

  ①：如果n为某一个素数p，则φ(p)=p-1

  ①证明：因为素数p的质因数只有1和它本身，p和p不为互质，所以φ(p)=p-1；

 ②：如果n为某一个素数p的幂次，那么φ(p^a)=(p-1)*p^(a-1)；

②因为比p^a小的数有p^a-1个，那么有p^(a-1)-1个数能被p所整除（因为把1~p^a-1的p的倍数都筛去了）

所以φ(p)=p^a-1-(p^(a-1)-1)=(p-1)*p^(a-1)

 ③：如果n为任意两个数a和b的积，那么φ(a*b)=φ(a)*φ(b)

 ③因为比a*b小的数有a*b-1个，条件是a与b互质

那么可以知道，只有那些既满足a与其互质且既满足b与其互质的数满足条件。

根据乘法原理，这样的数可以互相组合，那么就有φ(a)*φ(b)个

 所以可以得知φ(a*b)=φ(a)*φ(b) (注意条件必须满足a和b互质)

④：设n=(p1^a1)*(p2^a2)*……*(pk^ak) (为N的分解式)

 那么φ(n)=n*(1-1/p1)*(1-1/p2)*……*(1-1/pk)

④因为各个分解完的p1、p2、……pk均为素数，所以它们均为互质的

每次再刨去它们本身，乘起来， 剩下的运用容斥原理，再根据引理②和引理③就可以得出

欧拉定理：a^(φ(m)) ≡1(mod m) (a与m互质)

φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn)

直接实现：直接套用定理求解欧拉函数值

一：代码中的 ans-=ans/i;  这一步就是对应欧拉函数的通式？

二：while(n%i==0)   n/=i;    这一个语句是为了保证完全消除我们刚才得到的那个i因子。确保我们下一个得到的i是n的素因子。

三：if(n>1)ans-=ans/n;  这个语句是为了保证我们已经除完了n的所有的素因子，有可能还会出现一个我们未除的因子，如果结尾出现n>1 ,说明我们还剩一个素因子木有除。