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

简介

证明

欧拉函数的编程实现

简介

φ函数的值 通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。 (注意：每种质因数只一个。比如12=2*2*3那么φ（12）=12*（1-1/2）*(1-1/3)=4)

若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。

设n为正整数，以 φ(n)表示不超过n且与n互

素的正整数的个数，称为n的欧拉函数值，这里函数

φ：N→N，n→φ(n)称为欧拉函数。

欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。

特殊性质：当n为奇数时，φ(2n)=φ(n), 证明与上述类似。

证明

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

若

n= ∏p^(α（下标p）)

p|n

则φ(n)=∏(p-1)p^(α（下标p）-1)=n∏(1-1/p)

p|n p|n

例如φ(72)=φ(2^3×3^2)=(2-1)2^(3-1)×(3-1)3^(2-1)=24

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

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

a^φ(m)≡1(mod m)

即欧拉定理

当m是质数p时，此式则为：

a^(p-1)≡1(mod m)

即费马小定理。

欧拉函数的编程实现

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

欧拉函数和它本身不同质因数的关系：欧拉函数ψ（N）=N{∏p|N}（1－1/p）。（P是数N的质因数）

如：

ψ（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）=42。

#include <stdlib.h>

#define N 10000000

main()

{

int *phi,i,j;

char *prime;

prime=(char*)malloc((N+1)*sizeof(char));

prime[0]=prime[1]=0;

for(i=2;i<=N;i++)

{

prime[i]=1;

}

for(i=2;i*i<=N;i++)

{

if(prime[i])

{

for(j=i*i;j<=N;j+=i)

{

prime[j]=0;

}

}

} //这段求出了N内的所有素数

phi=(int*)malloc((N+1)*sizeof(int));

for(i=1;i<=N;i++)

{

phi[i]=i;

}

for(i=2;i<=N;i++)

{

if(prime[i])

{

for(j=i;j<=N;j+=i)

{

phi[j]=phi[j]/i*(i-1); //此处注意先/i再*（i-1)，否则范围较大时会溢出

}

}

//这段求出了N内所有数的欧拉函数值

2-100欧拉函数表

n φ(n)

2 1

3 2

4 2

5 4

6 2

7 6

8 4

9 6

10 4

11 10

12 4

13 12

14 6

15 8

16 8

17 16

18 6

19 18

20 8

21 12

22 10

23 22

24 8

25 20

26 12

27 18

28 12

29 28

30 8

31 30

32 16

33 20

34 16

35 24

36 12

37 36

38 18

39 24

40 16

41 40

42 12

43 42

44 20

45 24

46 22

47 46

48 16

49 42

50 20

51 32

52 24

53 52

54 18

55 40

56 24

57 36

58 28

59 58

60 16

61 60

62 30

63 36

64 32

65 48

66 20

67 66

68 32

69 44

70 24

71 70

72 24

73 72

74 36

75 40

76 36

77 60

78 24

79 78

80 32

81 54

82 40

83 82

84 24

85 64

86 42

87 56

88 40

89 88

90 24

91 72

92 44

93 60

94 46

95 72

96 32

97 96

98 42

99 60

100 40

pascal版写的，贴一下：

const

maxn=10000;

sqrtn=trunc(sqrt(maxn));

var

i,j,n,si:longint;

fi:array[1..maxn] of longint;

hash:array[1..sqrtn] of boolean;

ssb:array[1..sqrtn] of longint;

procedure yuchuli;

var

i,j,daili:longint; pd:boolean;

begin

fillchar(hash,sizeof(hash),false);

i:=2; si:=0;

while i<=sqrtn do

begin

if not hash[i] then

begin

for j:=i+1 to sqrtn div i do

hash[i*j]:=true;

inc(si);

ssb[si]:=i;

end;

inc(i);

end;

for i:=1 to maxn do fi[i]:=1;

for i:=2 to maxn do

begin

daili:=i;

for j:=1 to si do

begin

pd:=false;

while daili mod ssb[j]=0 do

begin

daili:=daili div ssb[j];

if not pd then

fi[i]:=fi[i]*(ssb[j]-1) else fi[i]:=fi[i]*(ssb[j]);

pd:=true;

end;

end;

if daili<>1 then fi[i]:=fi[i]*(daili-1);

end;

end;

begin

yuchuli;

readln(n);

writeln(fi[n]);

readln;

end.

C语言：

int eular(int n)

{

int ret=1,i;

for(i=2;i*i<=n;i++)

if(n%i==0)

{

n/=i,ret*=i-1;

while(n%i==0)

n/=i,ret*=i;

}

if(n>1)

ret*=n-1;

return ret;

}