Ø 第三章 同余

　　一、 主要内容

　　同余的定义、性质、剩余类和完全剩余系、欧拉函数、简化剩余系、欧拉定理、费尔马小定理、循环小数、特殊数2，3，4，5，6，7，8，9，11，13的整除规律

　　二、 基本要求

　　通过本章的学习，能够掌握同余的定义和性质，区别符号：“三”和=”之间的差异。能利用同余的一些基本性质进行一些计算，深刻理解完全剩余系，简化剩余系的定义、性质及构造。能判断一组数是否构成模m的一个完全剩余系或一个简化剩余系。能计算欧拉函数的值，掌握欧拉定理、费尔马小定理的内容以及证明方法。能应用这二个定理证明有关的整除问题和求余数问题。能进行循环小数与分数的互化。

　　三、难点和重点

　　(1)同余的概念及基本性质

　　(2)完全剩余系和简化剩余系的构造、判别

　　(3)欧拉函数计算、欧拉定理、费尔马小定理的证明及应用

　　(4)循环小数与分数的互化

　　(5)特殊数的整除规律。

　　四、自学指导

　　同余理论是初等数论中最核心的内容之一，由同余定义可知，若a≡b(mod m)，则a和b被m除后有相同的余数。这里m为正整数，一般要求m大于1，称为模，同余这一思想本质上是将整数按模m分类，然后讨论每一个类中整数所具有的共性及不同类之间的差异。第一章中用带余除法定理将整数分类解决一些问题的方法只不过是同余理论中的一个特殊例子。从同余的定理上看，同余和整除实际上是同一回事，故同余还有二个等价的定义：①用整除来定义即 m∣a-b 。②用等号来定义a=b+mt 。值得注意a和b关于m同余是个相对概念。即它是相对于模m来讲，二个整数a和b关于一个整数模m同余。则对于另一个整数模m

　　，a和b未必会同余。

　　从定义上看，同余和整除是同一个事情，但引进了新的符号“三”后，无论从问题的叙述上，还是解决问题的方法上都有了显著的变化，同时也带来了一些新的知识和方法。在引进了同余的代数性质和自身性质后，同余符号“三”和等号“=”相比，在形式上有几乎一致的性质，这便于我们记忆。事实上在所有等号成立的运算中，只有除法运算是个例外，即除法的消去律不成立。为此对于同余的除法运算我们有二种除法：

　　(i)模不改变的除法，若ak≡bk(mod m) ，(k,m)=1，则a≡b(mod m)

　　(ii)模改变的除法, 若ak≡bk(mod m) (k,m)=d,则a≡b

　　这一点读者要特别注意。

　　完全剩余系和简化剩余系是二个全新的概念，读者只要搞清引成这些概念的过程。因为同余关系是一个等价关系，利用等价关系可以进行将全体整数进行分类，弄清来胧去脉，对于更深刻理解其本质是很有好处的。完全剩余系或简化剩余系是一个以整数为元素的集合，在每个剩余类各取一个数组成的m个不同数的集合，故一组完全剩余系包含m个整数，由于二个不同的剩余类中的数关于m两两不同余，故可得判别一组数是否为模m的一个完全剩余系的条件有二条为

　　(1) 个数=m

　　(2) 关于m两两不同余

　　另外要能用已知完全剩余系构造新的完全剩余系。即有定理

　　设(a，m)=1，x为m的完全剩余系，则ax+b也是m的完全剩余系。

　　当

　　时，能由

　　的完全剩余系和

　　的完全剩余系，构造

　　完全剩余系。为讨论简化剩余系，需要引进欧拉函数φ(m)，欧拉函数φ(m)定义为不超过m且与m互素的正整数的个数，记为φ(m)，要掌握φ(m)的计算公式，了解它的性质。这些性质最主要的是当(a ,b)=1时，φ(ab) = φ(a) φ(b)，和

　　现在在剩余类中把与m互素的集合分出来，从中可在各个集合中任取一个数即可构造模m的一个简化剩余系。另一方面，简化剩余数也可从模m的一个完全剩余系中得到简化剩余系，一组完全剩余系中与m互素的的数组成的φ(m)个不同数的集合称为m简化剩余系。同样简化剩余系也有一个判别条件。

　　判别一组整数是否为模m的简化剩余系的条件为

　　(1) 个数=φ(m)

　　(2) 关于m两两不同余

　　(3) 每个数与m互素

　　关于m的简化剩余系也能用已知完全剩余系构造新的简化剩余系。

　　设(a，m)=1，x为m的简化剩余系，则ax也是m的简化剩余系。

　　当

　　时，能由

　　的简化剩余系和

　　的简化剩余系，构造

　　简化剩余系。

　　欧拉定理、费尔马小定理是同余理论非常重要的定理之一。要注意欧拉定理和费尔马定理的条件和结论。

　　欧拉定理：设m为大于1的整数，(a，m)=1，则有

　　费尔马小定理：若p是素数，则有

　　除此以外，欧拉定理的证明的思想是非常好的，在各个地方都有应用。就欧拉定理、费尔马小定理来讲，它在某些形如a

　　数的整除问题应用起来显得非常方便。同余方法也是解决整除问题的方法之一。

　　另外同余方法在证明不定方程时也非常有用，即要掌握同余“三”和相等“=”的关系：相等必同余，同余未必相等，不同余肯定不相等。

　　对于特殊数的整除规律要求能掌握其一般定理的证明，并熟记一些特殊数的整除规律

　　1、 一个整数被2整除的充要条件是它的末位为偶数。

　　2、 一个整数被3整除的充要条件是它的各位数字之和能被3整除。

　　3、 一个整数被9整除的充要条件是它的各位数字之和能被9整除。

　　4、 一个整数被5整除的充要条件是它的末位为0或5。

　　5、 一个整数被4，25整除的充要条件是它的末二位能被4，25整除。

　　6、 一个整数被8，125整除的充要条件是它的末三位能被8，125整除。

　　7、 设

　　，则7或11或13整除a的充要条件是7或11或13整除

　　五、例子选讲

　　例1：求3406的末二位数。

　　解：∵ (3，100)=1，∴3

　　≡1(mod 100)

　　(100)=

　　(22·52)=40, ∴ 340≡1(mol 100)

　　∴ 3406=(340)10·36≡(32)2·32≡-19×9≡-171≡29(mod 100)

　　∴ 末二位数为29。

　　例2：证明(a+b)p≡ap+bp(mod p)

　　证：由费尔马小定理知对一切整数有：ap≡a(p)，bp≡b(P)，

　　由同余性质知有：ap+bp≡a+b(p)

　　又由费尔马小定理有(a+b)p≡a+b (p)

　　(a+b)p≡ap+bp(p)