初等数论1整除课件.ppt

《初等数论1整除课件.ppt》由会员分享，可在线阅读，更多相关《初等数论1整除课件.ppt（65页珍藏版）》请在三一办公上搜索。

1、2023/3/16,阜阳师范学院 数科院,1,中小学数学中的一些数论问题：,4.已知:782+8161能被57整除，求证：783+8163也能被57整除。,1.狐狸在跑道上跳远，每次跳远150CM从起点开始每 隔130CM设一个陷阱，问狐狸跳了几次后掉进井中？,2.已知66X1998Y，求所有满足条件的六位数X1998Y.,3.有一个自然数乘以9后，得到一个仅由数字1组成的多位数，求这个自然数最小为多少？,2023/3/16,阜阳师范学院 数科院,2,5.设n为整数，求证:24n(n+2)(5n+1)(5n1).,6.100个正整数之和为101101，则它们的最大公约 数的最大可能值是多少?证

2、明你的结论。,2023/3/16,阜阳师范学院 数科院,3,1.1 整除的概念 带余数除法,一、整除的概念,相关概念：因数、约数、倍数、奇数、偶数。,注：显然每个非零整数a都有约数 1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。,例1 有一个自然数乘以9后，得到一个仅由数字1组成的多位数，求这个自然数最小为多少？,12345679,2023/3/16,阜阳师范学院 数科院,4,二、整除的性质,定理1传递性,定理2,定理3,例2(1)已知：x和y是整数，13(9x+10y)，求证：13(4x+3y)；,(2)若 a,b 是整数，且7(a+b),7(2ab)，证明:7|(5a+2

3、b)。,2023/3/16,阜阳师范学院 数科院,5,三、带余数除法,定理4 设a与b是两个整数，b 0，则存在唯一的两个整数q和r，使得,定义2：（1）式通常写成,并称q为a被b除所得的不完全商；r叫做a被b除所得的余数；(2)式称为带余数除法。,2023/3/16,阜阳师范学院 数科院,6,证明：,存在性：考虑整数序列,则a必在序列的某两项之间，,即存在一个整数q，使得,唯一性：反证略,定理4 设a与b是两个整数，b 0，则存在唯一的两个整数q和r，使得,2023/3/16,阜阳师范学院 数科院,7,例3 利用带余数除法，由a,b的值求q,r.,如果允许b取负值，则要求,2023/3/16

4、,阜阳师范学院 数科院,8,证明：,由带余除法有,2023/3/16,阜阳师范学院 数科院,9,例5 设n为整数，求证：24n(n+2)(5n+1)(5n1).,证明：f(n)=n(n+2)(5n+1)(5n1),=n(n+2)(n21)+24n2,=(n1)n(n+1)(n+2)+24 n3(n+2),4!(n1)n(n+1)(n+2),2424 n3(n+2),24f(n).,练习：对于任意的五个自然数,证明其中必有3个数的和能被3整除。,2023/3/16,阜阳师范学院 数科院,10,例6 已知：782+8161能被57整除，,求证：783+8163也能被57整除。,证明：783+816

5、3=7(782+8161)7 8161+8163,=7(782+8161)+8161 57,782+8161和57都能被57整除,原式得证。,2023/3/16,阜阳师范学院 数科院,11,习题选讲,P44,设a,b是任意两个整数，,证明：存在两个整数s,t，使得,并且，当b为奇数时，s,t是唯一的。b为偶数呢？,则a必在此序列的某两项之间，,2023/3/16,阜阳师范学院 数科院,12,存在性得证；下证唯一性.,2023/3/16,阜阳师范学院 数科院,13,当b为奇数时，式中的等号不能成立，,当b为偶数时,s,t可以不唯一，举例如下：,注：该例为简化辗转相除法求最大公约数提供了依据。,2

6、023/3/16,阜阳师范学院 数科院,14,2023/3/16,阜阳师范学院 数科院,15,1.2 最大公因数与辗转相除法,一、最大公因数,例1 已知两个自然数的和为165，它们的最大公约数 为15，求这两个数。,15与150，或30与135，或45与120，或60与105，或75与90.,2023/3/16,阜阳师范学院 数科院,16,练习：100个正整数之和为101101，则它们的最大公约数的最大可能值是多少?证明你的结论。,若这100个数互不相同呢？,1001,定理1：有关最大公因数的结论,注：定理1(3)给出了求最大公因数的方法,辗转相除法.,2023/3/16,阜阳师范学院 数科院

7、,17,二、辗转相除法,每次用余数去除除数，直到余数为0停止，这种运算,方法称为辗转相除法。即有,(*),或,2023/3/16,阜阳师范学院 数科院,18,定理2 在上面的表达式(*)中，有,证明：,另一方面，,2023/3/16,阜阳师范学院 数科院,19,证明：先考虑两个数的情形，,一方面，,另一方面，由辗转相除法可以得到，,对于多个整数的公因数，利用,可以证明.,2023/3/16,阜阳师范学院 数科院,20,例2 求下面各组数的最大公因数。,解：,1859 1573,1,1573,286,5,1430,143,2,286,0,注：亦可通过分解因数的方法求最大公因数.,2023/3/1

8、6,阜阳师范学院 数科院,21,补充说明：利用1.1习题4的结论，可以使得辗转相除法求最大公因数更为快速一些。每次除得余数的绝对值不超过除数的一半，余数可以为负。,例3 求（76501，9719）.,76501 9719,8,77752,1251,8,10008,289,4,1156,95,3,285,4,24,96,1,4,4,0,=1.,2023/3/16,阜阳师范学院 数科院,22,定理4,说明：,（1）在(*)式中，所有各项都乘以m可以得证。,（2）由(1)即可得证。,2023/3/16,阜阳师范学院 数科院,23,定理5,2023/3/16,阜阳师范学院 数科院,24,例4 求最大公

9、约数：,方法一：利用定理5.,方法二：分解因数.,48 72 108,2,24 36 54,2,12 18 27,3,4 6 9,2023/3/16,阜阳师范学院 数科院,25,例5 利用辗转相除法计算(27090,21672,11352).,27090 21672 11352,2,22704,（2）,22704,4386,1032,11,11352,4,4128,0,258,4,1032,0,所以，(27090,21672,11352)=258.,2023/3/16,阜阳师范学院 数科院,26,例6 证明：若n是正整数，则,2023/3/16,阜阳师范学院 数科院,27,定理6 设a，b不全

10、为0，则存在整数 s,t，使得,证明：利用P4习题1-3的结论.,一方面，,另一方面，,2023/3/16,阜阳师范学院 数科院,28,特别地，,证：必要性的证明由定理6直接可得。,2023/3/16,阜阳师范学院 数科院,29,推论1,证明：,2023/3/16,阜阳师范学院 数科院,30,推论2,证明：,另解：利用推论1,2023/3/16,阜阳师范学院 数科院,31,.,思考题：用辗转相除法求x，y，使得,125x 17y=(125,17).,2023/3/16,阜阳师范学院 数科院,32,习题选讲,2023/3/16,阜阳师范学院 数科院,33,4、证明：在辗转相除法中的n满足：,证：

11、由P31习题4知：,2023/3/16,阜阳师范学院 数科院,34,2023/3/16,阜阳师范学院 数科院,35,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|。,2023/3/16,阜阳师范学院 数科院,36,定理2 对任意的正整数a，b，有,证明：设m是a和b的一个公倍数，,那么存在整数k1，

12、k2，使得m=ak1，m=bk2，,因此 ak1=bk2.,2023/3/16,阜阳师范学院 数科院,37,推论1 两个整数的任何公倍数一定是,最小公倍数的倍数。,推论2 设m，a，b是正整数，则ma,mb=ma,b。,2023/3/16,阜阳师范学院 数科院,38,定理3,注：把多个整数的公倍数化为两个数的公倍数来计算。,推论 若m是a1,a2,an的公倍数，则a1,a2,anm。,2023/3/16,阜阳师范学院 数科院,39,定理4 整数a1,a2,an两两互素，即(ai,aj)=1，1 i,j n，i j 的充要条件是,a1,a2,an=a1a2an.,例3 设a，b，c是正整数，证明

13、 a,b,c(ab,bc,ca)=abc。,证：a,b,c=a,b,c=,(ab,bc,ca)=(ab,(bc,ca)=(ab,c(a,b),代入即得证.,2023/3/16,阜阳师范学院 数科院,40,多项式的带余式除法,称为n次多项式.,注：整数的带余数除法推广到多项式的带余式除法，其他方面的性质整除的性质、辗转相除法、约数、倍数等也可以作类似地推广。,2023/3/16,阜阳师范学院 数科院,41,习题讲解：,2023/3/16,阜阳师范学院 数科院,42,构造方程,其有理根只能为,2023/3/16,阜阳师范学院 数科院,43,2023/3/16,阜阳师范学院 数科院,44,1.4 质

14、数 算术基本定理,一、质数与合数,定义：若整数a 0，1，并且只有约数 1和 a，则称a是素数（或质数）；否则称a为合数。,注：本书中若无特别说明，素数总是指正素数。,定理1 设a是大于1的整数，则,（1）a 除1外的最小正因数q是质数；,（2）若a是合数，则,2023/3/16,阜阳师范学院 数科院,45,求质数的方法,例1 求30以内的质数.,划去2、3、5的倍数，得到不能被2、3、5整除的数有,7、11、13、17、19、23、29.,所以30以内的质数有,2、3、5、7、11、13、17、19、23、29.,该方法称为幼拉脱斯展纳筛法，利用该方法可以构造质数表，祥见教材P17-18.,

15、2023/3/16,阜阳师范学院 数科院,46,分析：利用定理2反证即得.,注意：在推论中，若p不是质数，则结论不能成立。,2023/3/16,阜阳师范学院 数科院,47,二、算术基本定理,定理3算术基本定理任一大于1的整数n能表示成质数的乘积，且其分解的结果是唯一的不考虑次序.,即有：n=p1p2pm(1)其中pi（1 i m）是素数.,证明 当n=2时，结论显然成立。,由于2 d k，由归纳假定知存在素数q1,q2,ql，使得d=q1q2ql，从而k 1=pq1q2ql。,假设对于2 n k，式(1)成立，下证式(1)对于n=k 1也成立，,从而由归纳法推出式(1)对任何大于1的整数n成立

16、。,如果k 1是素数，式(1)显然成立。,若k 1是合数，则存在素数p与整数d，使得k 1=pd。,2023/3/16,阜阳师范学院 数科院,48,推论3.1标准分解式,推论3.2 a的正因数可以表示为a的分解式中的部分因数的乘积。,推论3.3 设a,b是任意两个正整数，且,推论3.3是分解质因数方法求最大公因数和最小公倍数的依据。,2023/3/16,阜阳师范学院 数科院,49,定理4 质数的个数是无穷的。,证：假设质数的个数有限，记为,所以存在质数p,所以，质数的个数是无穷的。,2023/3/16,阜阳师范学院 数科院,50,例2 写出51480的标准分解式。,解：51480=225740

17、,=2212870,=2351287,=2353429,=23532143,=233251113。,=236435,2023/3/16,阜阳师范学院 数科院,51,例3 证明：(a,b)a,b=ab.,其中p1,p2,pk是互不相同的素数，,i，i（1 i k）都是非负整数。,(a,b)a,b=,2023/3/16,阜阳师范学院 数科院,52,2023/3/16,阜阳师范学院 数科院,53,三、费马数及其他,费马数,尺规作图问题：,正n边形可尺规作图的充要条件是n的最大单因数是不同的费马质数的乘积。例如：正3、5、15、17边形等。,2023/3/16,阜阳师范学院 数科院,54,证：（反证法

18、）,2023/3/16,阜阳师范学院 数科院,55,2023/3/16,阜阳师范学院 数科院,56,1.5 函数x与x及其在数论中的应用,定义：设x是实数，以x表示不超过x的最大整数，,称它为x的整数部分，称x=x x为x的小数部分.,一、函数x与x及其性质,2023/3/16,阜阳师范学院 数科院,57,定理1 对于x与x，有下列结论成立,2023/3/16,阜阳师范学院 数科院,58,2023/3/16,阜阳师范学院 数科院,59,2023/3/16,阜阳师范学院 数科院,60,2023/3/16,阜阳师范学院 数科院,61,二、函数x与x的一个应用,定理2 在n!的标准分解式中质因数,例

19、1 求 20！分解式中质因数2的个数。,2023/3/16,阜阳师范学院 数科院,62,定理2的证明：,下面以15!为例说明.,2023/3/16,阜阳师范学院 数科院,63,考虑15!含有质因数2的个数.,在2，3，15中，含有1个因子2的数有4个；,2，6，10，14.,含有2个因子2的数有2个；,4，12.,含有3个因子2的数有1个；,8.,另一方面，能被2整除的有N1=4+2+1=7个；,能被4整除的有N2=2+1=3个；,能被8整除的有N3=1个；,2023/3/16,阜阳师范学院 数科院,64,例2 求12!的标准分解式。,解：12以内的质数有2，3，5，7，11.,其标准分解式中，各质因数的个数如下：,所以 12!的标准分解式为,2023/3/16,阜阳师范学院 数科院,65,推论2 贾宪数,证明：由定理2，对于任意的质数p，整数n!，k!与(n k)!的标准分解式中所含的p的指数分别是,利用定理1(4)可知,