第二学期第十五次课 §2 同余式 8.2.1 有理整数环中的同余的定义 定义8.5 设是一个正整数，若，且，亦即，则称与模同余，记作。不难得到，与模同余就是它们用做带余除法所得的余数相同。整数模同余为一等价关系，验证如下： 反身性：； 对称性：若，则； 转递性：若，，则 。 关于这个等价关系划分为等价类，给定整数，所有与模同余的整数属于一个类，称为以为代表的同余类。 8.2.2 Euler-函数 定义8.6(与互素的剩余类的定义) 设是一正整数。如果，则称为与互素的剩余类。在全部模剩余类中，与互素的剩余类的数目记作，称作Euler函数。 引理 设  是全部互不相同的与互素的剩余类，有设，则  也是全部互不相同的与互素的剩余类。 简证 因为，故，即为与互素的剩余类；由若，则，于是，从而，矛盾。 定理（Euler定理）设是与正整数互素的整数，则  证明 设全部互不相同的与互素的剩余类为 ， 则由引理  与上述个剩余类仅是排列次序不同而已，所以把它们连乘起来应该相等，即  于是  因，故。于是 ， 注意，故命题成立。 作为Euler定理的推论，我们有 定理（Fermat小定理）设为素数，若不整除整数，则。 事实上，模的个剩余类，除外，均为与互素的剩余类，即。 8.2.3 中国剩余定理 定理（中国剩余定理） 设是个两两互素的正整数。任给个整数，必存在整数，使  证明 首先，对一固定的。当时，，则有，使。令  另一方面有  现在利用上面得到的构造整数  当时，，即，而，带入上式得  定理得证。