第二学期第十五次课
§2 同余式
8.2.1 有理整数环中的同余的定义定义8.5 设是一个正整数，若，且，亦即，则称与模同余，记作。不难得到，与模同余就是它们用做带余除法所得的余数相同。整数模同余为一等价关系，验证如下：
反身性：；
对称性：若，则；
转递性：若，，则
。
关于这个等价关系划分为等价类，给定整数，所有与模同余的整数属于一个类，称为以为代表的同余类。
8.2.2 Euler-函数定义8.6(与互素的剩余类的定义) 设是一正整数。如果，则称为与互素的剩余类。在全部模剩余类中，与互素的剩余类的数目记作，称作Euler函数。
引理 设

是全部互不相同的与互素的剩余类，有设，则

也是全部互不相同的与互素的剩余类。
简证 因为，故，即为与互素的剩余类；由若，则，于是，从而，矛盾。
定理（Euler定理）设是与正整数互素的整数，则

证明 设全部互不相同的与互素的剩余类为
，
则由引理

与上述个剩余类仅是排列次序不同而已，所以把它们连乘起来应该相等，即

于是

因，故。于是
，
注意，故命题成立。
作为Euler定理的推论，我们有定理（Fermat小定理）设为素数，若不整除整数，则。
事实上，模的个剩余类，除外，均为与互素的剩余类，即。
8.2.3 中国剩余定理定理（中国剩余定理） 设是个两两互素的正整数。任给个整数，必存在整数，使

证明 首先，对一固定的。当时，，则有，使。令

另一方面有

现在利用上面得到的构造整数

当时，，即，而，带入上式得

定理得证。