在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）（φ(1)=1）。此函数以其首名研究者欧拉命名(Euler′stotientfunction)(Euler′stotientfunction)，它又称为Euler′stotientfunctionEuler′stotientfunction、φφ函数、欧拉商数等。 例如φ(8)=4φ(8)=4，因为1,3,5,71,3,5,7均和88互质。 从欧拉函数引伸出来在环论方面的事实和拉格朗日定理构成了欧拉定理的证明。
欧拉函数
说一下，上面说这么多，就只有第一句有用
欧拉函数，就是求比n小的数中和n互质的数的个数。
来几条很基本的性质：
1.对于任何一个质数pp，φ(p)=p−1φ(p)=p−1（对于质数来说，比它小的数都与它互质）
2.若pp为质数，n=pkn=pk，那么φ(n)=pk−pk−1φ(n)=pk−pk−1
3.欧拉函数是积性函数，φ(n×m)=φ(n)×φ(m)φ(n×m)=φ(n)×φ(m)
欧拉函数值求法
首先贴公式
φ(x)=x(1−1/p(1))(1−1/p(2))(1−1/p(3))(1−1/p(4))…..(1−1/p(n))φ(x)=x(1−1/p(1))(1−1/p(2))(1−1/p(3))(1−1/p(4))…..(1−1/p(n))
其中p(1),p(2)…p(n)p(1),p(2)…p(n)为xx的所有质因数;
xx是正整数;
特别的，φ(1)=1φ(1)=1(唯一和1互质的数，且小于等于1)。注意：每种质因数只有一个。
