欧拉函数的求法 欧拉函数120的计算方法？

欧拉函数的求法

欧拉函数120的计算方法？

欧拉函数120的计算方法？

分解质因数：120=2^3*3*5 欧拉函数：φ(120)=120*(1-1/2)(1-1/3)(1-1/5)=120*1/2*2/3*4/5=32 小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1）。 设n为正整数，以 φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值φ：N→N，n→φ(n)称为欧拉函数。

欧拉代数学入门？

在数论，对正整数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)。注意：每种质因数只有一个。