数论期末复习

1、期末复习,二元一次不定方程,有解的充分必要条件:求特解(方法?):辗转相除法,分离整数法.通解(公式?):先求得一个特解(x0,y0),三元一次不定方程,整系数方程axbyczd叫做三元一次不定方程，这里a，b，c，d都是整数，其中a，b，c都不为零.由于三元一次不定方程的x，y，z可以取正整数或负整数，因此在研究三元一次不定方程时，我们只须讨论a，b，c，d都是正整数的情况,解的存在性,定理三元一次不定方程axbyczd(24)有整数解的必要且充分条件是D|d，这里D(a，b，c)，a,b,c,d都是正整数,推论在方程(2，4)中，如果d不能被(a，b，c)整除，那么这个不定方程无整数解(推

2、论的证明请读者自行完成),例1若k为整数,且10k30，试问k取何值时，下列不定方程无整数解kxky91z100,解(k，k，91)(k，91)，由于91137，100不能被7或13整除，所以当是14，21，28时，(k，91)7，这时方程无整数解；同理，当k13或26时，(k，91)13，这时方程也无整数解；因此，当k13，14，2l，26，28时，原不定方程无整数解,例2求不定方程6x+14y32z80的整数解,解1因为(6，14，32)2，2|80，所以原不定方程有整数解，将原方程化简，得3x+7y16z40设3x+7yt，利用观察法或辗转相除法可知x2，y1是不定方程3x7y1的一个整

3、数解，因此3x+7yt的通解为,把3x+7yt代入，得t16z40，这个二元一次不定方程的通解为,由，可得原不定方程的通解为,例3求不定方程2x+4y5z3的整数解,解由于(2，4，5)|3，因此原方程有整数解考虑到原方程中x，y的系数的最大公约数(2，4)2，因此应该令2x+4y2t，即x+2yt，这个不定方程的通解为,把2x+4y2t代入原方程，得,将t45v代入上面x，y的表达式，得原方程的通解为,例4有三个自然数，其中一数是2的倍数，一数为3的倍数，一数为7的倍数，它们的和为23，试求这三个数,解设三个自然数分别为2x，3y与7Z，由题意，得2x+3y+7z23，根据题目要求，应该求这

4、个三元一次不定方程的正整数解。在x，y，z的三个系数中，z的系数最大因为x，y至少取1，所以z的取值范围是,逐次尝试,由上可知z的可能取值是1和2.当z=1时,原方程化为2x+3y=16,解之得正整数解:,因此,所求的三数分别为4,12,7;10,6,7以及6,3,14,当z=2时,原方程化为2x+3y=9,解之得正整数解:,勾股数,形如x2+y2=z2的不定方程的整数解问题，我们将这种方程叫做商高或毕达哥拉斯不定方程。满足上述不定方程的一组正整数x,y,z叫做一组勾股数.,九章算术中的几组勾股数:3,4,5;5,12,13;7,24,25;8,15,17;20,21,29.,关于勾股数的定理

5、,定理2.5不定方程x2+y2=z2(2.6)的适合条件x0，y0，z0，(x，y)=1，x是偶数的一切正整数解均可以表示成x=2ab，y=a2b2，z=a2b2，其中ab0，(a,b)=1,并且a,b一为奇数，一为偶数。,例1.求下列不定方程的正整数解:,(1)x+y=xy2;(2)5x2xy6=0.,(1)xyxy1=3,分解因式(x1)(y1)=3由数分解可知x=2,y=4或x=4,y=2.,(2)可得(5xy)x=6.也是由数的分解推出解来.,特殊非一次型不定方程的解法1、约数分析法：,2整数分离法,不等式法求不定方程的整数解，就是根据不定方程特点，列出不等式，通过解不等式，得到不定方

6、程中各个未知数的取值范围，由此求得未知数在取值范围内的整数值，从而得到不定方程的整数解,3.不等式法,教材例2.26求不定方程(xy)2+2y2=27的非负整数解.,解由原不定方程得(xy)2=272y2因为(xy)20，所以272y20，因此y的取值范围是0y3当y=0时，272y2=27;当y=1时，272y2=25;当y=2时，272y219;当y=3时，272y2=9因为27，19都不是平方数，所以只有当y=1时，(xy)2=25，xy=5，x=6;或xy=5，x4(不合，舍去)。当y=3时，(xy)2=9xy=3，x=6，或xy=3，x=0因此得原不定方程的非负整数解.,弃九法-快速

7、检验运算结果的方法,利用定理我们可以得到一种判断整数四则运算（包括乘方）结果是否有错的快速检验方法，这就是通常所讲的弃九法.,例7用弃九法验算下面算式是否正确2894734578=1001865676.,弃九法只是运算结果正确的必要条件,而非充分条件!因此只能判误.,解,剩余类和完全剩余系,奇数偶数的分类就是模2的两个剩余类.,完全剩余系,定理2.4整数a1,a2,ak是模m的完全剩余系的充分必要条件是(1)k=m;(2)aiaj(modm)(ij).,从模m的每一个剩余类中各取一个数所得到的m个数，称为模m的一个完全剩余系.,定义2.3,模m有无数个完全剩余系.特别地,我们把0,2,m-1称

8、为模m的最小非负完全剩余系,定义2.4,在模m的一个完全剩余系中，与m互质的数的全体称为模m的一个简化剩余系简化剩余系也称既约剩余系,定义2.5,设m是自然数，用(m)表示不大于m且与m互质的自然数的个数(m)称为欧拉函数,简化剩余系的充要条件,定理2.7一组整数构成模m的简化剩余系的充要条件是这组数满足下面三个条件：(i)有(m)个数;(ii)各数关于模m两两不同余;(iii)各数均与模m互素,例如，下面12个与42互素的数构成模42的一个简化剩余系：1,5,11,13,17,19,23,25,29,31,37,41.,练习,1、模5的最小非负完全剩余系是().A-2,-1,0,1,2B-5

9、,-4,-3,-2,-1C1,2,3,4,5D0,1,2,3,42、1,5,7,11是模12的一个简化剩余系.下面不是12的简化剩余系的是()(A)1,5,7,23,(B)2,10,14,22(C)5,25,35,55(D)5,25,47,55,3、假设今天是星期三,2773天后是().A星期二B星期三C星期四D星期五,D,B,A,第三章同余与同余式,主要内容,同余的概念与性质数的整除特征一次同余式同余式组,第一部分同余的概念与性质,一、同余的概念,设m是非零整数，a和b是整数，如m|（a-b），则称a和b关于模m同余（或a对于模m同余于b），记作；此式称为同余式.如m不能整除（a-b），则称

10、a与b关于模m不同余.性质（1）如果a除以m的余数为r（），则；（2）如，则a除以m的余数为r.(3)整数a与b同余，即的充要条件是，其中k为整数.,二、同余的性质,定理同余关系是等价关系，即有（1）自反性：；（2）对称性：如则；（3）传递性如，则.,同余的其它性质（一）,定理3.5如果，则.推论1如果，则；推论2如果则，或；推论3如果自然数n2，则,同余的其它性质（二）,定理3.6如果，那么推论1，c为任意一个整数，那么推论2若自然数n2，那么推论3如果，那么，其中k为任意整数.,三、同余概念、性质的应用,对于数字a与一切自然数k：与a的个位数字相同；与的个位数字相同；与的个位数字相同；与的

11、个位数字相同.例求质数的末位数字.,第二部分数的整除特征,一、整系数整值多项式的同余性质,形如的多项式为整系数整值多项式，其中系数是整数，变量x取整数值.定理3.7设整系数整值多项式：与若则,二、数的整除特征,定理3.8（1）能被2（或5）整除的数的特征是这个数末位数能被2（或5）整除；（2）能被4（或25）整除的数的特征是这个数末两位上数字所组成的数能被4（或25）整除；（3）能被8（或125）整除的数的特征是这个数末三位上数字所组成的数能被8（或125）整除.定理3.9能被9（或3）整除的数的特征是这个数的各个数位上的数字之和能被9（或3）整除.定理3.10能被11整除的数的特征是这个数的

12、偶数位上数字之和与奇数位上数字之和的差能被11整除.定理3.11能被7（或11，或13）整除的数的特征是这个数末三位上数字所组成的数与末三位以前的数字所组成的数的差能被7（或11，或13）整除.,第三部分一次同余式,一、同余式两端公约数的约去,定理3.14如果那么推论如果那么定理3.15若则定理3.16设整数c0，则的必要且充分条件是,二、一次同余式,设a，b都是整数，m是一个正整数，则当a与0模m不同余时，称为模m的一元一次同余式.如果存在整数c，使成立，则称为同余式的一个解（或一个根）.求同余式的解叫做解同余式.定理3.17一次同余式有解的充要条件是（a，m）|b.定理3.18设（a，m）

13、=d，d|b，则同余式有d个解.,三、解一元一次同余式,1.用辗转相除法解同余式2.系数消去法变换（1）加上或减去模的倍数，即：变换（2）移项变换，由可得变换（3）约去同余式两端的公约数，由可得变换（4）同余式两端同时乘以与模m互质的因数c，即得所谓系数消去法解同余式就是对它的“系数”a与b连续施行上面四种变换，目的是使a变成绝对值较小的同余数，直到1为止.,用系数消去法解下列同余式：当，且d|b时，求解同余式：设a=ds，b=dt，m=dl，则（s，t）=1，代入同余式，得约去d，得由于（s，t）=1，所以可用辗转相除法或系数消去法求出同余式一个关于模m的最小剩余的解r，从而可得同余式的d个解：r，r+l，r+2l，r+（d-1）l.,四、不定方程的同余式解法,对于二元一次不定方程ax+by=c，可以看成两个同余式：从中任取一个同余式，解出x或y，然后代入原不定方程，求出另一个未知数.,第四部分同余式组,一、中国剩余定理,定理3.19（孙子定理）如果是两两互质的n个正整数，令那么同余式组的正整数解为：其中是满足同余式的正整