第七讲 同余“续1”

《第七讲 同余“续1”》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第七讲同余“续1”定义五：如果一个模m的剩余类kr中任一数与m互质，则称kr是与模m互质的剩余类；在与模m互质的每个剩余类中任取一个数（共个）所组成的数组，称为模m的一个简化剩余系.例如，取m=6，在模6的六个剩余类中，是与模6互质的剩余类.数组1，5；7，－7；1，－1；等等都是模6的简化剩余类.由此定义，不难得到：定理三:是模m的简化剩余系定理四：在模m的一个完全剩余系中，取出所有与m互质的数组成的数组，就是一个模m的简化剩余系.这两个定理，前者是简化剩余系的判别方法，后者是它的构造方法.显然，模m的简化剩余系有无穷多个，但常用的是“最小简化剩余系”，即由1，2，…，m－1中

2、与m互质的那些数组成的数组.由定理不难证得简化剩余系的如下性质定理.定理五：设是模m的简化剩余系.若（k,m）=1，则也是模m的简化剩余系.下面介绍两个有关欧拉函数的重要结论.其证明略.定理六：（欧拉定理）若（a,m）=1，则特别地，（费马小定理）若m=p为质数，pa，则定理七：（威尔逊定理）设p素数，则（p－1）！定理八：（欧拉函数值计算公式）令m的标准分解式为，则例如，30=2·3·5，则-4-读者应认识到：由于任何整数都属于模m的某一剩余类，所以，在研究某些整数性质时，选取适当的（模）m，然后在模m的每个剩余类中取一个“代表数”（即组成一个完全剩余系），当弄清了这些代表数的

3、性质后，就可弄清对应的剩余类中所有数的性质，进而弄清全体整数的性质，这就是引入剩余类和完全剩余系的目的.Ⅲ.同余方程设的整系数多项式.类似于多项式和代数方程式的有关定义，我们有定义六：同余式叫做一元n次同余方程.例如，是七次同余方程.定义七：若c使得叫做同余方程的一个解.显然，同余方程的解是一些剩余类，而不仅是一个或n个类.例如，都是二次同余方程的解.1．一次同余方程（其中ma）称为一次同余方程.关于它的解，有如下共知的结论：定理九：若（a,m）=1，则有一个解.定理十：若（a,m）=d>1，db，则无解，其中.定理十一：若（a,m）=d>1，d

4、b，则有d个解.并且，若的一个解

5、为则d个解为：，其中下面介绍一次同余方程（*）的解法.【解法1】因（a,m）=1，则存在二数s,t，使得as+mt=1，即，由此有为（*）的解.-4-【解法2】先把（*）变形成仅只是形式上的记号），然后用与m互质的数陆续乘右端的分子分母，直至把分母绝对值变成1（通过分子分母各对模m取余数）而得到解.【解法3】得用欧拉定理.因从而有解2．一次同余方程组定义八：若数r同时满足n个同余方程：叫做这n个同余方程组成的同余方程组的解.定理十二：对同余方程组记①若d，则此同余方程组无解；②若，则此同余方程组有对模M的一类剩余解.Ⅳ.模m的阶和中国剩余定理（1）模m的阶定义九：设m>1是一个固

6、定的整数，a是与m互素的整数，则存在整数k，1≤k＜m，使得.我们将具有这一性质的最小正整数（仍记为k）称为a模m的阶.a模m的阶具有如下性质：①设的阶，是任意整数，则的充要条件是.特别地，的充分必要条件是k

7、u.【简证】充分性显然.必要性.设用带余除法，及k的定义知，必须r=0，所以-4-②设模m的阶为k，则数列模m是周期的，且最小正周期是k，而k个数模m互不同余.③设模m的阶整除欧拉函数特别地，若m是素数p，则a模p的阶整除p－1.（2）中国剩余定理（即孙子定理）设是两两互质的正整数，记M=则同余方程组有且只有解（△）其中（△△）【证明】由知，，因此每一个同余方程（i=1，2

8、，…n）都有解，于是必存在所以对模故（△△）是（△）的解.若是适合（△）的任意两个解，则故因此，（△△）是（△）的惟一解.-4-