欧拉函数（一）

如果你有了数论书上第一节和第二节的基础，那么你对欧拉函数的理解就更简单了，

数论教材 第一节：同余的概念及其基本性质

第二节：剩余类及完全剩余系

首先我们要知道几个概念：

同余定义：例如：x1 % m = r

x2 % m = r ，则我们就说 x1 和 x2 是关于 m 同余的两个数

关于同余的定理：若整数 a，b 关于 m 同余，则有一充分必要条件：m | a - b， 即 a = b + mt；t 是整数。

剩余类的定义：把模 m 得到余数为 r ( r < m ) 相同的全部都放在一起组成一个数的集合，那么这个集合就叫做剩余类，用字母 Kr 表示..

完全剩余系定义：把模 m 得到的所有的剩余类中各取一个元素组成数的集合叫做模 m 的完全剩余系，例如：

关于 7 的完全剩余系其中之一是 0,1,2,3,4,5,6 也可以是： 2,3,4,5,6,7,8 等等..

简化剩余系定义：它是在完全剩余系中取出和 m 互质的元素组成的数的集合...

还有很多性质和定理就不列举了...

欧拉函数：很简单，说白来就是简化剩余系中元素的个数...

例如：模 8 的完全剩余系：1，2，3，4，5，6，7，8

简化剩余系：1，3 ， 5， 7

模 8 的简化剩余系中的元素有 4 个，所以E(8) = 4......

注：E(n) ==1 <==> n=1 或者 n=2;

小结论1：如果 p 是一个质数，那么 E(p) = p - 1 , E(p^n) = p^n - p^(n-1);

证明：（1）： 因为 p 是质数，所以模 p 的完全剩余系中有元素：1,2,3,4，.....，p-1，p ；

除去 1 个 p 的倍数 ，所以变成简化剩余系：1,2,3,4,.....p-2，p-1。

所以 E(p) = p-1;

（2）：同样的道理：模 p^n的完全剩余系中有元素：1,2,...p，p+1....2*p,2*p+1....p^(n-1)*p-1, p^(n-1)*p

除去 p^(n-1) 个p 的倍数，剩下的变成简化剩余系：1,2,...p-1，p+1，...2*p-1 , 2*p+1....

所以E(p^n) = p^n - p^(n-1);

小结论2：在一个模 m 剩余类中，如果存在一个元素与 m 是互质的, 则该类中的所有元素与 m 是互质的..

证明： 假设有一个模m剩余类 Kr = { x1,x2,x3,x4..... } , 并且（x1 ，m）= 1;

从 Kr 中任意取一个元素 xn ；

因为 xn 与 x1 同余，则有 m | xn - x1 ===>> xn = x1 + mt ( t=1,2,3,... )

又因为 （x1，m）= 1 ； 所以 xn = mt + x1 ====>>由带余除法得：（ xn, m）= ( m, x1 ) = 1;

所以结论成立...

在小结论2的基础上扩展，得到小结论3..

小结论3：在一个模 m 剩余类中，如果存在一个元素与 m 的最大公约是 d ,则该剩余类中所有的元素与 m 的最大公约数都是 d ..

证明方法和证明小结论2的方法是一样的...