第十一讲 初等数论-1

2020/4/30,皖西学院数理系,1,第一章整数的可除性,整除性理论是初等数论的基础，本章要介绍,带余数除法，辗转相除法，最大公约数，最小公,算术基本定理以及,倍数，,它们的一些应用。,2020/4/30,皖西学院数理系,2,1.1整除的概念带余数除法,一、整除的概念,相关概念：因数、约数、倍数、奇数、偶数。,注：显然每个非零整数a都有约数1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。,例1有一个自然数乘以9后，得到一个仅由数字1组成的多位数，求这个自然数最小为多少？,12345679,2020/4/30,皖西学院数理系,3,二、整除的性质,定理1传递性,定理2,定理3,例2(1)已知：x和y是整数，13(9x+10y)，求证：13(4x+3y)；,(2)若a,b是整数，且7(a+b),7(2ab)，证明:7|(5a+2b)。,2020/4/30,皖西学院数理系,4,三、带余数除法,定理4设a与b是两个整数，b0，则存在唯一的两个整数q和r，使得,定义2：（1）式通常写成,并称q为a被b除所得的不完全商；r叫做a被b除所得的余数；(2)式称为带余数除法。,2020/4/30,皖西学院数理系,5,定理4设a与b是两个整数，b0，则存在唯一的两个整数q和r，使得,2020/4/30,皖西学院数理系,6,例6已知：782+8161能被57整除，,求证：783+8163也能被57整除。,证明：783+8163=7(782+8161)78161+8163,=7(782+8161)+816157,782+8161和57都能被57整除,原式得证。,2020/4/30,皖西学院数理系,7,1.2最大公因数与辗转相除法,一、最大公因数,2020/4/30,皖西学院数理系,8,1.2最大公因数与辗转相除法,一、最大公因数,例1已知两个自然数的和为165，它们的最大公约数为15，求这两个数。,15与150，或30与135，或45与120，或60与105，或75与90.,2020/4/30,皖西学院数理系,9,定理1：有关最大公因数的结论,注：定理1(3)给出了求最大公因数的方法,辗转相除法.,2020/4/30,皖西学院数理系,10,二、辗转相除法,每次用余数去除除数，直到余数为0停止，这种运算,方法称为辗转相除法。即有,(*),或,2020/4/30,皖西学院数理系,11,定理2在上面的表达式(*)中，有,证明：,另一方面，,2020/4/30,皖西学院数理系,12,对于多个整数的公因数，利用,2020/4/30,皖西学院数理系,13,定理4,说明：,（1）在(*)式中，所有各项都乘以m可以得证。,（2）由(1)即可得证。,2020/4/30,皖西学院数理系,14,定理5,2020/4/30,皖西学院数理系,15,定理6设a，b不全为0，则存在整数s,t，使得,特别地，,2020/4/30,皖西学院数理系,16,推论1,证明：,2020/4/30,皖西学院数理系,17,推论2,证明：,另解：利用推论1,2020/4/30,皖西学院数理系,18,1.3最小公倍数,定义1：整数a1,a2,ak的公共倍数称为a1,a2,ak的公倍数。a1,a2,ak的正公倍数中的最小的一个叫做a1,a2,ak的最小公倍数，记为a1,a2,ak.,定理1：下面的等式成立：()a,1=|a|，a,a=|a|；()a,b=b,a；()a1,a2,ak=|a1|,|a2|,|ak|；()若ab，则a,b=|b|。,2020/4/30,皖西学院数理系,19,定理2对任意的正整数a，b，有,2020/4/30,皖西学院数理系,20,推论1两个整数的任何公倍数一定是,最小公倍数的倍数。,推论2设m，a，b是正整数，则ma,mb=ma,b。,2020/4/30,皖西学院数理系,21,定理3,注：把多个整数的公倍数化为两个数的公倍数来计算。,2020/4/30,皖西学院数理系,22,定理4整数a1,a2,an两两互素，即(ai,aj)=1，1i,jn，ij的充要条件是,a1,a2,an=a1a2an.,2020/4/30,皖西学院数理系,23,多项式的带余式除法,称为n次多项式.,2020/4/30,皖西学院数理系,24,1.4质数算术基本定理,一、质数与合数,定义：若整数a0，1，并且只有约数1和a，则称a是素数（或质数）；否则称a为合数。,注：本书中若无特别说明，素数总是指正素数。,定理1设a是大于1的整数，则,（1）a除1外的最小正因数q是质数；,（2）若a是合数，则,2020/4/30,皖西学院数理系,25,2020/4/30,皖西学院数理系,26,二、算术基本定理,定理3算术基本定理任一大于1的整数n能表示成质数的乘积，且其分解的结果是唯一的不考虑次序.,2020/4/30,皖西学院数理系,27,推论3.1标准分解式,推论3.2a的正因数可以表示为a的分解式中的部分因数的乘积。,推论3.3设a,b是任意两个正整数，且,推论3.3是分解质因数方法求最大公因数和最小公倍数的依据。,2020/4/30,皖西学院数理系,28,三、费马数及其他,费马数,尺规作图问题：,正n边形可尺规作图的充要条件是n的最大单因数是不同的费马质数的乘积。例如：正3、5、15、17边形等。,2020/4/30,皖西学院数理系,29,1.5函数x与x及其在数论中的应用,定义：设x是实数，以x表示不超过x的最大整数，,称它为x的整数部分，称x=xx为x的小数部分.,一、函数x与x及其性质,2020/4/30,皖西学院数理系,30,定理1对于x与x，有下列结论成立,2020/4/30,皖西学院数理系,31,二、函数x与x的一个应用,定理2在n!的标准分解式中质因数,例1求20！分解式中质因数2的个数。,2020/4/30,皖西学院数理系,32,例2求12!的标准分解式。,解：12以内的质数有2，3，5，7，11.,其标准分解式中，各质因数的个数如下：,所以12!的标准分解式为,2020/4/30,皖西学院数理系,33,推论2贾宪数,证明：由定理2，对于任意的质数p，整数n!，k!与(nk)!的标准分解式中所含的p的指数分别是,利用定理1(4)可知,2020/4/30,皖西学院数理系,34,2020/4/30,皖西学院数理系,35,第二章不定方程,2.1二元一次不定方程,2020/4/30,皖西学院数理系,36,二元一次不定方程的一般形式为,注：该方法对一次项系数较小的方程比较实用。,2020/4/30,皖西学院数理系,37,二、二元一次不定方程解的形式和判定,定理1若1式有整数解,则1式的一切解可以表示为,（2）,2020/4/30,皖西学院数理系,38,例2写出下列方程通解的形式：,2020/4/30,皖西学院数理系,39,说明：定理1给出了方程通解的一般形式。这样，解决问题的关键在于求一个特解。,问题：所有的二元一次方程都有解吗？,定理2有整数解,即为方程1的解。,2020/4/30,皖西学院数理系,40,三、求二元一次不定方程整数解的一般方法,先求一个特殊解，再根据定理1写出其通解。,对于方程(1),若有解，则可化为,一般地，利用辗转相除法，得到,2020/4/30,皖西学院数理系,41,例3求方程的一个特殊解。,解：用7、4进行辗转相除法,2020/4/30,皖西学院数理系,42,例4求1的一切整数解。,原方程可以化为,先求3的一个整数解。,1073734，3749+1，从而,故3的一个整数解是,2的一个整数解是,原方程的整数解为,2020/4/30,皖西学院数理系,43,2.2多元一次不定方程,一、多元一次不定方程有解的判定,定理1方程,2020/4/30,皖西学院数理系,44,二、多元一次不定方程求解的方法,例1求不定方程x2y3z=7的所有整数解。,（1）的解为,（2）的解为,把(4)代入(3),消去t,得,注：三元一次不定方程的整数解中含有2个参数.,2020/4/30,皖西学院数理系,45,一般地，我们可以给出多元一次不定方程的求解方法.,2020/4/30,皖西学院数理系,46,二、多元一次不定方程求解的方法,若d不能整除N，则原方程无整数解；,否则，继续下面的步骤。,(2)构造如下的n-1个方程,(3)求出每个方程的所有整数解含参数ti，,再逐步代入上面的方程中，消去所有的ti，,从而得到原方程的所有整数解。,2020/4/30,皖西学院数理系,47,例2求方程的一切整数解。,原方程有整数解。,列出如下的2个方程：,(1)的解为,(2)的解为,把t的值代入x,y的表达式，得到原方程的一切整数解为,2020/4/30,皖西学院数理系,48,(1)的解为,(2)的解为,把t的值代入x,y的表达式，得到原方程的一切整数解为,例3把分解为三个分母两两互质既约正分数之和。,2020/4/30,皖西学院数理系,49,例3把分解为三个分母两两互质既约正分数之和。,2020/4/30,皖西学院数理系,50,第三章同余,同余是数论中的重要概念，同余理论是研究整数问题的重要工作之一.本章介绍同余的基本概念，剩余类和完全剩余系.,生活中我会经常遇到与余数有关的问题，比如：某年级有将近400名学生。有一次演出节目排队时出现：如果每8人站成一列则多余1人；如果改为每9人站成一列则仍多余1人；结果发现现成每10人结成一列，结果还是多余1人；聪名的你知道该年级共有学生多少名吗？,2020/4/30,皖西学院数理系,51,3.1同余的概念及其基本性质,一、问题的提出,1、今天是星期一，再过100天是星期几？,3、13511，13903，14589被自然数m除所得余数相同，问m最大值是多少？,2020/4/30,皖西学院数理系,52,二、同余的定义,注：下面的三个表示是等价的：,2020/4/30,皖西学院数理系,53,三、同余的性质,TH2设a，b，c，d，k是整数，并且ab(modm)，cd(modm)，则acbd(modm)；acbd(modm);akbk(modm).,2020/4/30,皖西学院数理系,54,2020/4/30,皖西学院数理系,55,TH4下面的结论成立：,ab(modm)，dm，d0ab(modd)；,ab(modm)，k0，kNakbk(modmk)；,ab(modmi)，1ikab(modm1,m2,mk)；,ab(modm)(a,m)=(b,m)；,acbc(modm)，(c,m)=1ab(modm);,2020/4/30,皖西学院数理系,56,四、一些整数的整除特征,(1)3、9的整除特征,各位上的数字之和能被3（9）整除,例1检查5874192、435693能否被3（9）整除。,2020/4/30,皖西学院数理系,57,(2)7、11、13的整除特征,注：一般地，求,被m除的余数时，,首先是求出正整数k，使得10k1或1(modm)，,2020/4/30,皖西学院数理系,58,(2)7、11、13的整除特征,特别地，由于，所以,奇偶位差法,例2检查637693、75312289能否被7（11，13）整除。,由69363756，所以637693能被7整除，但不能被11，13整除，,当然也可以由6+3-7+6-9+3=2知637693不能被11整除；,由75-312+28952，所以75312289能被13整除，但不能被7，11整除。,2020/4/30,皖西学院数理系,59,2020/4/30,皖西学院数理系,60,求出整数k，使ak1(modm)；,求出正整数r，rk，使得bcr(modk)；,减小幂指数,2020/4/30,皖西学院数理系,61,例4证明：若n是正整数，则1342n+13n+2。,解：42n+13n+2=442n93n,43n93n,=133n,0(mod13),=416n93n,2020/4/30,皖西学院数理系,62,例5设n的十进制表示是,且792n，,求x，y，z.,解因为792=8911，故,8n，9n及11n。,9n913xy45z=19xy,9xy1，(1),11n11z54yx31=3yx,113yx。(2),即有xy1=9或18，,3yx=0或11,解方程组，得到x=8，y=0，z=6。,2020/4/30,皖西学院数理系,63,五、弃九法验算计算结果,应用这种方法可以验算较大整数的乘法。,例6.验算28997394951145236415是否正确。,注：若结论成立，其结果不一定正确；,所以结果不正确。,也可以检查和、差的运算。,2020/4/30,皖西学院数理系,64,例7.求方程2x3y=1的正整