简化剩余系与欧拉函数.doc

《简化剩余系与欧拉函数.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、§3简化剩余系与欧拉函数定义欧拉函数是一个定义在正整数集上的函数，的值等于系列中与互质的整数的个数。当时，当为质数时，定义如果一个模的剩余类里的数与互质（在模的一个剩余类中，只要有其中一个数和互质，则该剩余类中所有的数就都与互质），就把它叫做一个与互质的剩余类.在与互质的全部剩余类中，各取一个数所组成的一组数，叫做模的一个简化剩余系.定理1模的一个简化剩余系含有个数.证模的全部剩余类是.因为，所以对每个，是一个与互质的剩余类的充要条件是因此，在模的全部剩余类中，与互质的全部剩余类是满足条件的所有剩余类.这样的剩余类公有个，故由简化剩余系的定义知，模的简化剩余系含有个数.

2、定理2若是个与互质的整数，则是模的一个简化剩余系的充要条件是它们两两对模不同余.证必要性设是模的一个简化剩余系，则由简化剩余系的定义，这个数是取自模的不同剩余类的，故这个数两两对模不同余.充分性设与互质的个整数两两对模不同余.因每个整数都与互质，故每个整数都属于一个与互质的剩余类.因这个整数两两对模不同余，故这个整数分别属于不同的与互质的剩余类.另一方面，与互质的剩余类共有个，故分别属于这个与互质的剩余类，故是模的一个简化剩余系.定理3若通过模的简化剩余系，则也通过模的简化剩余系。证当通过模的简化剩余系时，通过个整数.由于故故所通过的这个整数都与互质.下面证明这个整数两

3、两对模不同余.假设在这个整数中，有两个整数对模同余，设（1）其中是所通过的模的简化剩余系中两个不同的数，则由及（1）式得另一方面，因是所通过的模的简化剩余系中两个不同的数，它们不属于模的同一个剩余类，故它们对模不同余，矛盾.因此，根据定理2，这个整数组成模的简化剩余类.定理4若分别通过模的一个简化剩余系，则通过模的一个简化剩余系。证首先证明，当分别通过模的一个简化剩余系时，个整数都与互质.因为所以其次证明，当分别通过模的一个简化剩余系时，个整数两两对模不同余.设这里是所通过的模的简化剩余系中的数，是所通过的模的简化剩余系中的数，则，同理，最后证明，与互质的任意一个整数，

4、都会与某个对模同余，即因为，所以因，故由定理3得，会与某个对模同余，即同理，会与某个对模同余，即于是，因，故由上式得，由定理4，立即得到下面的推论。推论设则定理5设的标准分解式为，则证由定理4的推论得下面证明，当为质数时，由欧拉函数的定义，等于中所有与互质的个数，也就是中所有与互质的整数个数.故等于减去在中与不互质的整数个数。因为质数，故在中，与不互质的整数个数为.从而补充题若为模数的任一缩系，则证法一因为模数的一个缩系，，故也是模数的一个缩系，于是当为奇数时，故此时命题成立。当为偶数时，设这里为正整数,为正奇数。因，故当通过模数的一个缩系，通过模数的缩系时，通过模数的

5、一个缩系。因为奇数，故于是以上最后一个同余式成立是因为，当时，因，故此时；当时，为偶数，此时，证法二因为的一个缩系，故（1）因，故为偶数。若，则（因为若，则，由此会引出矛盾.当为奇数时显然是矛盾的：当为偶数时，，这与矛盾.）且因此，在模的完全剩余系中，与模互质的数是成对出现的，每一对与互质的数满足且其中一个在区间中，另一个在区间，共有对.故（2）由（1），（2）两式即可得作业P61：2，3，4.习题选解2.若是大于的正整数，是整数，通过模的简化剩余系，则（1）其中表示展布在所通过的一切值上的和式。证因对任意整数及任意实数，有由此易得，若，则因通过模的简化剩余系，故通过模

6、的简化剩余系.（2）因，故为偶数.若，则（因为若，则，由此会引出矛盾.当为奇数时显然是矛盾的：当为偶数时，，这与矛盾.）且因此，在模的完全剩余系中，与模互质的数是成对出现的，每一对与互质的数满足且其中一个在区间中，另一个在区间，共有对.故（3）由（2），（3）两式即知，（1）式成立.3.(ⅰ)证明质数.(ⅱ)证明，其中表示展布在的一切正因数上的和式.证(ⅰ)因故(ⅱ)证一当时，结论显然成立。下设又设的标准分解式为下面对用数学归纳法证明，当时，由(ⅰ)知结论正确。假设结论对成立，下证结论对也成立.由(ⅰ)中的结论及归纳假设得证二当时，结论显然成立.下设又设的标准分解式为则

7、4.若是个两两互质的正整数，分别通过模的简化剩余系，则通过模的简化剩余系，其中证法一：因是个两两互质的正整数，故由上一节习题2知，若分别通过模的完全剩余系，则通过模的完全剩余系。若，则反之，若，则从而这就证明了定理的结论.证法二：首先证明，当分别通过模的一个简化剩余系时，个整数都与互质.因为所以其次证明，当分别通过模的一个简化剩余系时，个整数两两对模不同余.设这里是所通过的模的简化剩余系中的数，，则，最后证明，与互质的任意一个整数，都会与某个对模同余，即因为，所以因，故由定理3得，会与某个对模同余，即于是，因是个两两互质的正整数，故由上式