欧拉函数

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

通式:

定义 φ(1)=1(和1互质的数(小于等于1)就是1本身)。

注意:每种质因数只有一个。

若n是质数p的k次幂,

比如12=2*2*3那么φ(12)=φ(4*3)=φ(2^2*3^1)=(2^2-2^1)*(3^1-3^0)=4

设n为正整数,以 φ(n)表示不超过n且与n互素的正整数的个数,称为n的欧拉函数值

φ:N→N,n→φ(n)称为欧拉函数。

欧拉函数是积性函数——若m,n互质,

特殊性质:当n为奇质数时,

若n为质数则

设A, B, C是跟m, n, mn互质的数的集,据中国剩余定理,A*B和C可建立一一对应的关系。盼禁少因此φ(n)的值使用算术基本定理便知,

例如

与欧拉定理、费马小定理的关系

对任何两个互质的正整数a, m(m>=2)有

即欧拉定理

当m是质数p时,束询定霸此式则为:

即费马小定理。

利用欧拉函数和它本身不同质因数的关系,用筛法计算出某个范围内所有数的欧拉函数值。

欧拉函数和它本身不同质因数的关系:

欧拉函数ψ(N)=N{∏p|N}(1-1/p)

亦即:

如:

ψ(10)=10×(1-1/2)×(1-1/5)=4;

ψ(30)=30×(1-1/2)×(1-1/3)×(1-1/5)=8;

ψ(49)=49×(1-1/7)=

φ(n)

0

1

2

3

4

5

6

7

8

9

0?

0

1

1

2

2

4

2

6

4

6

1?

4

10

4

12

6

8

8

16

6

18

2?

8

12

10

22

8

20

12

18

12

28

3?

8

30

16

20

16

24

12

36

18

24

4?

16

40

12

42

20

24

22

46

16

42

5?

20

32

24

52

18

40

24

36

28

58

6?

16

60

30

36

32

48

20

66

32

44

7?

24

70

24

72

36

40

36

60

24

78

8?

32

54

40

82

24

64

42

56

40

88

9?

24

72

44

60

46

72

32

96

42

60

φ(100)=40

相关词汇