初等数论整除PPT讲稿.ppt

初等数论整除2023/4/12阜阳师范学院阜阳师范学院 数科院数科院1第1页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院2中小学数学中的一些数论问题：中小学数学中的一些数论问题：4.已知已知:782+8161能被能被57整除，求证：整除，求证：783+8163也能也能被被57整除。整除。1.1.狐狸在跑道上跳远，每次跳远狐狸在跑道上跳远，每次跳远150CM150CM从起点开始每从起点开始每 隔隔130CM130CM设一个陷阱，问狐狸跳了几次后掉进井中？设一个陷阱，问狐狸跳了几次后掉进井中？2.2.已知已知6666X1998YX1998Y，求所有满足条件的六位数，求所有满足条件的六位数X1998Y.X1998Y.3.3.有一个自然数乘以有一个自然数乘以9 9后，得到一个仅由数字后，得到一个仅由数字1 1组成组成的多位数，求这个自然数最小为多少？的多位数，求这个自然数最小为多少？第2页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院35.5.设设n n为整数，求证为整数，求证:24n(n+2)(5n+1)(5n:24n(n+2)(5n+1)(5n1).1).6.1006.100个正整数之和为个正整数之和为101101101101，则它们的最大公约，则它们的最大公约 数的最大可能值是多少数的最大可能值是多少?证明你的结论。证明你的结论。第3页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院41.1 1.1 整除的概念整除的概念 带余数除法带余数除法一、整除的概念一、整除的概念相关概念：因数、约数、倍数、奇数、偶数。相关概念：因数、约数、倍数、奇数、偶数。注：显然每个非零整数注：显然每个非零整数a都有约数都有约数 1，a，称这四个，称这四个数为数为a的平凡约数，的平凡约数，a的另外的约数称为非平凡约数。的另外的约数称为非平凡约数。例例1 1 有一个自然数乘以有一个自然数乘以9 9后，得到一个仅由数字后，得到一个仅由数字1 1组成组成的多位数，求这个自然数最小为多少？的多位数，求这个自然数最小为多少？12345679 12345679 第4页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院5二、整除的性质二、整除的性质定理定理1 1传递性传递性 定理定理2 2 定理定理3 3 例例2 2(1)已知：已知：x和和y是整数，是整数，13(9x+10y)，求证：求证：13(4x+3y)；(2)若若 a,b 是整数，且是整数，且7(a+b),7(2ab)，证明证明:7|(5a+2b)。第5页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院6三、带余数除法三、带余数除法定理定理4 设设a与与b是两个整数，是两个整数，b 0 0，则存在唯一，则存在唯一的两个整数的两个整数q和和r，使得，使得 定义定义2 2：（：（1 1）式通常写成）式通常写成并称并称q为为a被被b除所得的不完全商；除所得的不完全商；r叫做叫做a被被b除所得的余数；除所得的余数；(2)(2)式称为带余数除法。式称为带余数除法。第6页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院7证明：证明：存在性：考虑整数序列存在性：考虑整数序列则则a必在序列的某两项之间，必在序列的某两项之间，即存在一个整数即存在一个整数q，使得，使得 唯一性：反证唯一性：反证略略定理定理4 设设a与与b是两个整数，是两个整数，b 0 0，则存在唯一，则存在唯一的两个整数的两个整数q和和r，使得，使得 第7页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院8例例3 3 利用带余数除法，由利用带余数除法，由a,b的值求的值求q,r.如果允许如果允许b取负值，则要求取负值，则要求 思考思考正确吗？正确吗？第8页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院9证明：证明：由带余除法有由带余除法有 第9页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院10例例5 设设n为整数，求证：为整数，求证：24 n(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),24 24 n3(n+2)24 f(n).练习：对于任意的五个自然数练习：对于任意的五个自然数,证明其中必有证明其中必有3 3个数的和能被个数的和能被3 3整除整除。第10页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院11例例6 已知：已知：782+8161能被能被57整除，整除，求证：求证：783+8163也能被也能被57整除。整除。证明：证明：783+8163 =7(782+8161)7 8161+8163=7(782 +8161)+8161 57782+8161和和57都能被都能被57整除整除原式得证。原式得证。第11页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院12习题选讲习题选讲P44 设设a,b是任意两个整数，是任意两个整数，证明：存在两个整数证明：存在两个整数s,t，使得，使得并且，当并且，当b为奇数时，为奇数时，s,t是唯一的。是唯一的。b为偶数呢？为偶数呢？则则a必在此序列的某两项之间，必在此序列的某两项之间，第12页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院13存在性得证存在性得证 ；下证唯一性；下证唯一性.第13页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院14当当b为奇数时，为奇数时，式中的等号不能成立，式中的等号不能成立，当当b为偶数时为偶数时,s,t可以不唯一，举例如下：可以不唯一，举例如下：注：该例为简化辗转相除法求最大公约数提供了依据。注：该例为简化辗转相除法求最大公约数提供了依据。第14页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院15第15页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院161.2 1.2 最大公因数与辗转相除法最大公因数与辗转相除法一、最大公因数一、最大公因数例例1 1 已知两个自然数的和为已知两个自然数的和为165165，它们的最大公约数，它们的最大公约数 为为1515，求这两个数。，求这两个数。15与与150，或，或30与与135，或，或45与与120，或或60与与105，或，或75与与90.第16页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院17练习：练习：100100个正整数之和为个正整数之和为101101101101，则它们的最大，则它们的最大公约数的最大可能值是多少公约数的最大可能值是多少?证明你的结论。证明你的结论。若这若这100100个数互不相同呢？个数互不相同呢？10011001定理定理1 1：有关最大公因数的结论有关最大公因数的结论注：定理注：定理1(3)1(3)给出了求最大公因数的方法给出了求最大公因数的方法辗转相除法辗转相除法.第17页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院18二、辗转相除法二、辗转相除法定义：设有整数定义：设有整数 的带余数除法中，的带余数除法中，每次用余数去除除数，直到余数为每次用余数去除除数，直到余数为0 0停止，这种运算停止，这种运算方法称为辗转相除法。即有方法称为辗转相除法。即有(*)(*)或或第18页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院19定理定理2 2 在上面的表达式在上面的表达式(*)(*)中，有中，有 证明：证明：另一方面，另一方面，第19页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院20证明：先考虑两个数的情形，证明：先考虑两个数的情形，一方面，一方面，另一方面，由辗转相除法可以得到，另一方面，由辗转相除法可以得到，对于多个整数的公因数，利用对于多个整数的公因数，利用 可以证明可以证明.第20页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院21例例2 2 求下面各组数的最大公因数。求下面各组数的最大公因数。解：解：1859 15731859 15731 1157315732862865 5143014301431432 22862860 0注：亦可通过分解因数的方法求最大公因数注：亦可通过分解因数的方法求最大公因数.第21页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院22补充说明：补充说明：利用利用1.11.1习题习题4 4的结论，可以使得辗转的结论，可以使得辗转相除法求最大公因数更为快速一些。每次除得余数相除法求最大公因数更为快速一些。每次除得余数的绝对值不超过除数的一半，余数可以为负。的绝对值不超过除数的一半，余数可以为负。例例3 3 求（求（7650176501，97199719）.76501 971976501 97198 87775277752125112518 810008100082892894 41156115695953 32852854 4242496961 14 44 40 0=1.第22页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院23定理定理4 4说明：说明：（1）在在 (*)(*)式中，所有各项都乘以式中，所有各项都乘以m可以得证。可以得证。（2 2）由）由(1)(1)即可得证。即可得证。第23页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院24定理定理5 5第24页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院25例例4 4 求最大公约数求最大公约数 ：方法一：利用定理方法一：利用定理5.5.方法二：分解因数方法二：分解因数.48 72 10848 72 1082 224 36 5424 36 542 212 18 27 12 18 27 3 34 6 94 6 9第25页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院26例例5 5 利用辗转相除法计算利用辗转相除法计算 (27090,21672,11352).(27090,21672,11352).27090 21672 1135227090 21672 113522 22270422704（2）22704227044386 4386 1032 1032 111111352113524 44128 4128 0 0258 258 4 41032 1032 0 0所以，所以，(27090,21672,1135227090,21672,11352)=258.第26页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院27例例6 证明：若证明：若n是正整数，则是正整数，则 第27页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院28定理定理6 6 设设a，b不全为不全为0，则存在整数，则存在整数 s,t，使得，使得证明：利用证明：利用P P4 4习题习题1-31-3的结论的结论.一方面，一方面，另一方面，另一方面，第28页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院29特别地，特别地，证：必要性的证明由定理证：必要性的证明由定理6 6直接可得。直接可得。第29页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院30推论推论1 1证明：证明：第30页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院31推论推论2 2证明：证明：另解：利用推论另解：利用推论1 1第31页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院32.思考题：用辗转相除法求思考题：用辗转相除法求x，y，使得，使得125x 17y=(125,17).第32页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院33习题选讲习题选讲第33页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院34 4、证明：在辗转相除法中的、证明：在辗转相除法中的n满足：满足：证：由证：由P31习题习题4知：知：第34页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院35第35页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院361.3 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|；()若若a b，则，则a,b=|b|。第36页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院37定理定理2 2 对任意的正整数对任意的正整数a，b，有，有证明：证明：设设m是是a和和b的一个公倍数，的一个公倍数，那么存在整数那么存在整数k1，k2，使得，使得m=ak1，m=bk2，因此因此 ak1=bk2.第37页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院38推论推论1 1 两个整数的任何公倍数一定是两个整数的任何公倍数一定是最小公倍数的倍数。最小公倍数的倍数。推论推论2 设设m，a，b是正整数，则是正整数，则ma,mb=ma,b。第38页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院39定理定理3 3注：把多个整数的公倍数化为两个数的公倍数来计算。注：把多个整数的公倍数化为两个数的公倍数来计算。推论推论 若若m是是a1,a2,an的公倍数，则的公倍数，则a1,a2,an m。第39页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院40定理定理4 4 整数整数a1,a2,an两两互素，两两互素，即即(ai,aj)=1，1 i,j n，i j 的充要条件是的充要条件是a1,a2,an=a1a2an.例例3 设设a，b，c是正整数，证明是正整数，证明 a,b,c(ab,bc,ca)=abc。证：证：a,b,c=a,b,c=(ab,bc,ca)=(ab,(bc,ca)=(ab,c(a,b)代入即得证代入即得证.第40页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院41多项式的带余式除法多项式的带余式除法称为称为n次多项式次多项式.注：整数的带余数除法推广到多项式的带余式除法，注：整数的带余数除法推广到多项式的带余式除法，其他方面的性质其他方面的性质整除的性质、辗转相除法、约数、整除的性质、辗转相除法、约数、倍数等倍数等也可以作类似地推广。也可以作类似地推广。第41页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院42习题讲解：习题讲解：第42页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院43构造方程构造方程 其有理根只能为其有理根只能为第43页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院44第44页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院451.4 1.4 质数质数 算术基本定理算术基本定理一、质数与合数一、质数与合数定义：定义：若整数若整数a 0，1，并且只有约数，并且只有约数 1和和 a，则，则称称a是素数（或质数）；否则称是素数（或质数）；否则称a为合数。为合数。注：本书中若无特别说明，素数总是指正素数。注：本书中若无特别说明，素数总是指正素数。定理定理1 1 设设a是大于是大于1 1的整数，则的整数，则（1 1）a 除除1 1外的最小正因数外的最小正因数q是质数；是质数；（2）若）若a是合数，则是合数，则 第45页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院46求质数的方法求质数的方法 例例1 1 求求3030以内的质数以内的质数.划去划去2 2、3 3、5 5的倍数，得到不能被的倍数，得到不能被2 2、3 3、5 5整除的数有整除的数有 7 7、1111、1313、1717、1919、2323、29.29.所以所以3030以内的质数有以内的质数有 2 2、3 3、5 5、7 7、1111、1313、1717、1919、2323、29.29.该方法称为幼拉脱斯展纳筛法，利用该方法可以该方法称为幼拉脱斯展纳筛法，利用该方法可以构造质数表，祥见教材构造质数表，祥见教材P P17-1817-18.第46页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院47分析：利用定理分析：利用定理2 2反证即得反证即得.注意：在推论中，若注意：在推论中，若p不是质数，则结论不能成立。不是质数，则结论不能成立。第47页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院48二、算术基本定理二、算术基本定理定理定理3 3算术基本定理算术基本定理任一大于任一大于1 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成立。成立。如果如果k 1是素数，式是素数，式(1)显然成立。显然成立。若若k 1是合数，则存在素数是合数，则存在素数p与整数与整数d，使得，使得k 1=pd。第48页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院49推论推论3.13.1标准分解式标准分解式 推论推论3.2 3.2 a的正因数可以表示为的正因数可以表示为a的分解式中的部分的分解式中的部分因数的乘积。因数的乘积。推论推论3.3 3.3 设设a,b是任意两个正整数，且是任意两个正整数，且推论推论3.33.3是分解质因数方法求最大公因数和最小公倍数的依据。是分解质因数方法求最大公因数和最小公倍数的依据。第49页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院50定理定理4 4 质数的个数是无穷的。质数的个数是无穷的。证：假设质数的个数有限，记为证：假设质数的个数有限，记为 所以存在质数所以存在质数p,所以，质数的个数是无穷的。所以，质数的个数是无穷的。第50页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院51例例2 2 写出写出51480的标准分解式。的标准分解式。解：解：51480=2 25740=22 12870=23 5 1287=23 5 3 429=23 5 32 143=23 32 5 11 13。=23 6435第51页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院52例例3 证明：证明：(a,b)a,b=ab.其中其中p1,p2,pk是互不相同的素数，是互不相同的素数，i，i（1 i k）都是非负整数。）都是非负整数。(a,b)a,b=第52页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院53第53页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院54三、费马数及其他三、费马数及其他 费马数费马数 尺规作图问题：尺规作图问题：正正n边形可尺规作图的充要条件是边形可尺规作图的充要条件是n的最大单因数是不同的的最大单因数是不同的费马质数的乘积。费马质数的乘积。例如：正例如：正3、5、15、17边形等。边形等。第54页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院55证：（反证法）证：（反证法）第55页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院56第56页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院571.5 1.5 函数函数 x 与与 x 及其在数论中的应用及其在数论中的应用定义：定义：设设x是实数，以是实数，以x表示不超过表示不超过x的最大整数，的最大整数，称它为称它为x的整数部分，称的整数部分，称x=x x为为x的小数部分的小数部分.一、函数一、函数 x 与与 x 及其性质及其性质第57页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院58定理定理1 1 对于对于x与与x，有下列结论成立，有下列结论成立第58页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院59第59页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院60第60页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院61第61页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院62二、函数二、函数 x 与与 x 的一个应用的一个应用定理定理2 在在n!的标准分解式中质因数的标准分解式中质因数 例例1 求求 20！分解式中质因数！分解式中质因数2的个数。的个数。第62页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院63定理定理2 2的证明：的证明：下面以下面以15!15!为例说明为例说明.第63页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院64考虑考虑15!15!含有质因数含有质因数2 2的个数的个数.在在2 2，3 3，1515中，含有中，含有1 1个因子个因子2 2的数有的数有4 4个；个；2 2，6 6，1010，14.14.含有含有2 2个因子个因子2 2的数有的数有2 2个；个；4 4，12.12.含有含有3 3个因子个因子2 2的数有的数有1 1个；个；8.8.另一方面，能被另一方面，能被2 2整除的有整除的有N N1 1=4+2+1=7=4+2+1=7个；个；能被能被4 4整除的有整除的有N N2 2=2+1=3=2+1=3个；个；能被能被8 8整除的有整除的有N N3 3=1=1个；个；第64页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院65例例2 2 求求12!12!的标准分解式。的标准分解式。解：解：1212以内的质数有以内的质数有2 2，3 3，5 5，7 7，11.11.其标准分解式中，各质因数的个数如下：其标准分解式中，各质因数的个数如下：所以所以 12!12!的标准分解式为的标准分解式为第65页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院66推论推论2 2 贾宪数贾宪数 证明：由定理证明：由定理2，对于任意的质数，对于任意的质数p，整数，整数n!，k!与与(n k)!的标准分解式中所含的的标准分解式中所含的p的指数分别是的指数分别是 利用定理利用定理1(4)可知可知 第66页，共67页，编辑于2022年，星期五2023/4/12阜阳师范学院阜阳师范学院 数科院数科院67第67页，共67页，编辑于2022年，星期五