欢迎来到天天文库
浏览记录
ID:14286919
大小:141.00 KB
页数:4页
时间:2018-07-27
《第七讲 同余“续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-
此文档下载收益归作者所有