初等数论--整除.ppt

数论是竞赛数学中最重要的一部分，特别是在数论是竞赛数学中最重要的一部分，特别是在数论是竞赛数学中最重要的一部分，特别是在数论是竞赛数学中最重要的一部分，特别是在1991199119911991年，年，年，年，IMOIMOIMOIMO在中国举行，国际上戏称那一年为数论年，因为在中国举行，国际上戏称那一年为数论年，因为在中国举行，国际上戏称那一年为数论年，因为在中国举行，国际上戏称那一年为数论年，因为6 6 6 6道道道道IMOIMOIMOIMO试题中有试题中有试题中有试题中有5 5 5 5道与数论有关。道与数论有关。道与数论有关。道与数论有关。数论的魅力在于它可以适合小孩到老头，只要有算术基数论的魅力在于它可以适合小孩到老头，只要有算术基数论的魅力在于它可以适合小孩到老头，只要有算术基数论的魅力在于它可以适合小孩到老头，只要有算术基础的人均可以研究数论础的人均可以研究数论础的人均可以研究数论础的人均可以研究数论在前几年还盛传广东的一位农民在前几年还盛传广东的一位农民在前几年还盛传广东的一位农民在前几年还盛传广东的一位农民数学爱好者证明了哥德巴赫猜想，当然，这一谣言最终被澄数学爱好者证明了哥德巴赫猜想，当然，这一谣言最终被澄数学爱好者证明了哥德巴赫猜想，当然，这一谣言最终被澄数学爱好者证明了哥德巴赫猜想，当然，这一谣言最终被澄清了。可是这也说明了最难的数论问题，适合于任何人去研清了。可是这也说明了最难的数论问题，适合于任何人去研清了。可是这也说明了最难的数论问题，适合于任何人去研清了。可是这也说明了最难的数论问题，适合于任何人去研究。究。究。究。初等数论最基础的理论在于整除，由它可以演化出许多初等数论最基础的理论在于整除，由它可以演化出许多初等数论最基础的理论在于整除，由它可以演化出许多初等数论最基础的理论在于整除，由它可以演化出许多数论定理。数论定理。数论定理。数论定理。2024/5/25 周六阜阳师范学院 数科院2第一章第一章 整数的可除性整数的可除性整除性理论是初等数论的基础，本章要介绍整除性理论是初等数论的基础，本章要介绍带余数除法，辗转相除法，最大公约数，最小公带余数除法，辗转相除法，最大公约数，最小公算算术术基本定理以及基本定理以及倍数，倍数，它们的一些应用。它们的一些应用。2024/5/25 周六阜阳师范学院 数科院3中小学数学中的一些数论问题：中小学数学中的一些数论问题：4.已知已知:782+8161能被能被57整除，求整除，求证证：783+8163也能也能被被57整除。整除。1.1.设设n n为整数，求证为整数，求证:24n(n+2)(5n+1)(5n:24n(n+2)(5n+1)(5n1).1).2.2.已知已知6666X1998YX1998Y，求所有满足条件的六位数，求所有满足条件的六位数X1998Y.X1998Y.3.3.有一个自然数乘以有一个自然数乘以9 9后，得到一个仅由数字后，得到一个仅由数字1 1组成组成的多位数，求这个自然数最小为多少？的多位数，求这个自然数最小为多少？2024/5/25 周六45.1005.100个正整数之和为个正整数之和为101101101101，则它们的最大公约，则它们的最大公约 数的最大可能值是多少数的最大可能值是多少?证明你的结论。证明你的结论。2024/5/25 周六51.1 1.1 整除的概念整除的概念 带余数除法带余数除法一、整除的概念一、整除的概念相关概念：因数、约数、倍数、奇数、偶数。相关概念：因数、约数、倍数、奇数、偶数。注：注：显显然每个非零整数然每个非零整数a都有都有约约数数 1，a，称，称这这四个四个数数为为a的平凡的平凡约约数，数，a的另外的的另外的约约数称数称为为非平凡非平凡约约数。数。例例1 1 有一个自然数乘以有一个自然数乘以9 9后，得到一个仅由数字后，得到一个仅由数字1 1组成组成的多位数，求这个自然数最小为多少？的多位数，求这个自然数最小为多少？12345679 12345679 2024/5/25 周六6二、整除的性质二、整除的性质定理定理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)。2024/5/25 周六7三、带余数除法三、带余数除法定理定理4 设设a与与b是两个整数，是两个整数，b 0 0，则则存在唯一存在唯一的两个整数的两个整数q和和r，使得，使得 定义定义2 2：（：（1 1）式通常写成）式通常写成并称并称q为为a被被b除所得的不完全商；除所得的不完全商；r叫做叫做a被被b除所得的余数；除所得的余数；(2)(2)式称式称为带为带余数除法。余数除法。2024/5/25 周六8证明：证明：存在性：考虑整数序列存在性：考虑整数序列则则a必在序列的某两必在序列的某两项项之之间间(包括包括这这两两项项），），即存在一个整数即存在一个整数q，使得，使得 唯一性：反证唯一性：反证略略定理定理4 设设a与与b是两个整数，是两个整数，b 0 0，则则存在唯一存在唯一的两个整数的两个整数q和和r，使得，使得 2024/5/25 周六9例例3 3 利用利用带带余数除法，由余数除法，由a,b的的值值求求q,r.如果允许如果允许b取负值，则要求取负值，则要求 思考思考正确吗？正确吗？2024/5/25 周六10证明：证明：由带余除法有由带余除法有 2024/5/25 周六阜阳师范学院 数科院11例例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整除整除。2024/5/25 周六阜阳师范学院 数科院12例例6 已知：已知：782+8161能被能被57整除，整除，求求证证：783+8163也能被也能被57整除。整除。证证明：明：783+8163 =7(782+8161)7 8161+8163=7(782 +8161)[phone]+8161和和57都能被都能被57整除整除原式得证。原式得证。2024/5/25 周六阜阳师范学院 数科院13习题选讲习题选讲 P44 设设a,b是任意两个整数，是任意两个整数，证证明：存在两个整数明：存在两个整数s,t，使得，使得并且，当并且，当b为为奇数奇数时时，s,t是唯一的。是唯一的。b为为偶数呢？偶数呢？则则a必在此序列的某两必在此序列的某两项项之之间间，2024/5/25 周六阜阳师范学院 数科院14存在性得证存在性得证 ；下证唯一性；下证唯一性.2024/5/25 周六阜阳师范学院 数科院15当当b为为奇数奇数时时，式中的等号不能成立，式中的等号不能成立，当当b为为偶数偶数时时,s,t可以不唯一，可以不唯一，举举例如下：例如下：注：该例为简化辗转相除法求最大公约数提供了依据。注：该例为简化辗转相除法求最大公约数提供了依据。2024/5/25 周六阜阳师范学院 数科院162024/5/25 周六阜阳师范学院 数科院171.2 1.2 最大公因数与辗转相除法最大公因数与辗转相除法一、最大公因数一、最大公因数例例1 1 已知两个自然数的和为已知两个自然数的和为165165，它们的最大公约数，它们的最大公约数 为为1515，求这两个数。，求这两个数。15与与150，或，或30与与135，或，或45与与120，或或60与与105，或，或75与与90.2024/5/25 周六阜阳师范学院 数科院18练习：练习：100100个正整数之和为个正整数之和为101101101101，则它们的最大，则它们的最大公约数的最大可能值是多少公约数的最大可能值是多少?证明你的结论。证明你的结论。若这若这100100个数互不相同呢？个数互不相同呢？10011001定理定理1 1：有关最大公因数的结论有关最大公因数的结论注：定理注：定理1(3)1(3)给出了求最大公因数的方法给出了求最大公因数的方法辗转相除法辗转相除法.2024/5/25 周六阜阳师范学院 数科院19二、辗转相除法二、辗转相除法定义：设有整数定义：设有整数 的带余数除法中，的带余数除法中，每次用余数去除除数，直到余数为每次用余数去除除数，直到余数为0 0停止，这种运算停止，这种运算方法称为辗转相除法。即有方法称为辗转相除法。即有(*)(*)或或2024/5/25 周六阜阳师范学院 数科院20定理定理2 2 在上面的表达式在上面的表达式(*)(*)中，有中，有 证明：证明：另一方面，另一方面，2024/5/25 周六阜阳师范学院 数科院21证明：先考虑两个数的情形，证明：先考虑两个数的情形，一方面，一方面，另一方面，由辗转相除法可以得到，另一方面，由辗转相除法可以得到，对于多个整数的公因数，利用对于多个整数的公因数，利用 可以证明可以证明.2024/5/25 周六阜阳师范学院 数科院22例例2 2 求下面各组数的最大公因数。求下面各组数的最大公因数。解：解：1859 15731859 1573 1 1157315732862865 5143014301431432 22862860 0注：亦可通过分解因数的方法求最大公因数注：亦可通过分解因数的方法求最大公因数.2024/5/25 周六阜阳师范学院 数科院23补充说明：补充说明：利用利用1.11.1习题习题4 4的结论，可以使得辗转的结论，可以使得辗转相除法求最大公因数更为快速一些。每次除得余数相除法求最大公因数更为快速一些。每次除得余数的绝对值不超过除数的一半，余数可以为负。的绝对值不超过除数的一半，余数可以为负。例例3 3 求（求（7650176501，97199719）.76501 971976501 97198 87775277752125112518 810008100082892894 41156115695953 32852854 4242496961 14 44 40 0=1.2024/5/25 周六阜阳师范学院 数科院24定理定理4 4说明：说明：（1）在在 (*)(*)式中，所有各项都乘以式中，所有各项都乘以m可以得证。可以得证。（2 2）由）由(1)(1)即可得证。即可得证。2024/5/25 周六阜阳师范学院 数科院25定理定理5 52024/5/25 周六阜阳师范学院 数科院26例例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 92024/5/25 周六阜阳师范学院 数科院27例例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.2024/5/25 周六阜阳师范学院 数科院28例例6 证证明：若明：若n是正整数，是正整数，则则 2024/5/25 周六阜阳师范学院 数科院29定理定理6 6 设设a，b不全为不全为0，则存在整数，则存在整数 s,t，使得，使得证明：利用证明：利用P P4 4习题习题1-31-3的结论的结论.一方面，一方面，另一方面，另一方面，2024/5/25 周六阜阳师范学院 数科院30特别地，特别地，证：必要性的证明由定理证：必要性的证明由定理6 6直接可得。直接可得。2024/5/25 周六阜阳师范学院 数科院31推论推论1 1证明：证明：2024/5/25 周六阜阳师范学院 数科院32推论推论2 2证明：证明：另解：利用推论另解：利用推论1 12024/5/25 周六阜阳师范学院 数科院33.思考思考题题：用：用辗转辗转相除法求相除法求x，y，使得，使得125x 17y=(125,17).2024/5/25 周六阜阳师范学院 数科院34习题选讲习题选讲2024/5/25 周六阜阳师范学院 数科院35 4、证证明：在明：在辗转辗转相除法中的相除法中的n满足：满足：证证：由：由P31习题习题4知：知：2024/5/25 周六阜阳师范学院 数科院362024/5/25 周六阜阳师范学院 数科院371.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|。2024/5/25 周六阜阳师范学院 数科院38定理定理2 2 对对任意的正整数任意的正整数a，b，有，有证证明：明：设设m是是a和和b的一个公倍数，的一个公倍数，那么存在整数那么存在整数k1，k2，使得，使得m=ak1，m=bk2，因此因此 ak1=bk2.2024/5/25 周六阜阳师范学院 数科院39推论推论1 1 两个整数的任何公倍数一定是两个整数的任何公倍数一定是最小公倍数的倍数。最小公倍数的倍数。推推论论2 设设m，a，b是正整数，是正整数，则则ma,mb=ma,b。2024/5/25 周六阜阳师范学院 数科院40定理定理3 3注：把多个整数的公倍数化为两个数的公倍数来计算。注：把多个整数的公倍数化为两个数的公倍数来计算。推推论论 若若m是是a1,a2,an的公倍数，的公倍数，则则a1,a2,an m。2024/5/25 周六阜阳师范学院 数科院41定理定理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)代入即得证代入即得证.2024/5/25 周六阜阳师范学院 数科院42多项式的带余式除法多项式的带余式除法称为称为n次多项式次多项式.注：整数的带余数除法推广到多项式的带余式除法，注：整数的带余数除法推广到多项式的带余式除法，其他方面的性质其他方面的性质整除的性质、辗转相除法、约数、整除的性质、辗转相除法、约数、倍数等倍数等也可以作类似地推广。也可以作类似地推广。2024/5/25 周六阜阳师范学院 数科院43习题讲解：习题讲解：2024/5/25 周六阜阳师范学院 数科院44构造方程构造方程 其有理根只能为其有理根只能为2024/5/25 周六阜阳师范学院 数科院452024/5/25 周六阜阳师范学院 数科院461.4 1.4 质数质数 算术基本定理算术基本定理一、质数与合数一、质数与合数定定义义：若整数若整数a 0，1，并且只有，并且只有约约数数 1和和 a，则则称称a是素数（或是素数（或质质数）；否数）；否则则称称a为为合数。合数。注：本书中若无特别说明，素数总是指正素数。注：本书中若无特别说明，素数总是指正素数。定理定理1 1 设设a是大于是大于1 1的整数，的整数，则则（1 1）a 除除1 1外的最小正因数外的最小正因数q是是质质数；数；（2）若）若a是合数，是合数，则则 2024/5/25 周六阜阳师范学院 数科院47求质数的方法求质数的方法 例例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.2024/5/25 周六阜阳师范学院 数科院48分析：利用定理分析：利用定理2 2反证即得反证即得.注意：在推论中，若注意：在推论中，若p不是质数，则结论不能成立。不是质数，则结论不能成立。2024/5/25 周六阜阳师范学院 数科院49二、算术基本定理二、算术基本定理定理定理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。2024/5/25 周六阜阳师范学院 数科院50推论推论3.13.1标准分解式标准分解式 推推论论3.2 3.2 a的正因数可以表示的正因数可以表示为为a的分解式中的部分的分解式中的部分因数的乘因数的乘积积。推推论论3.3 3.3 设设a,b是任意两个正整数，且是任意两个正整数，且推论推论3.33.3是分解质因数方法求最大公因数和最小公倍数的依据。是分解质因数方法求最大公因数和最小公倍数的依据。2024/5/25 周六阜阳师范学院 数科院51定理定理4 4 质数的个数是无穷的。质数的个数是无穷的。证：假设质数的个数有限，记为证：假设质数的个数有限，记为 所以存在质数所以存在质数p,所以，质数的个数是无穷的。所以，质数的个数是无穷的。2024/5/25 周六阜阳师范学院 数科院52例例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 64352024/5/25 周六阜阳师范学院 数科院53例例3 证证明：明：(a,b)a,b=ab.其中其中p1,p2,pk是互不相同的素数，是互不相同的素数，i，i（1 i k）都是非）都是非负负整数。整数。(a,b)a,b=2024/5/25 周六阜阳师范学院 数科院542024/5/25 周六阜阳师范学院 数科院55三、费马数及其他三、费马数及其他 费马数费马数 尺规作图问题：尺规作图问题：正正n边边形可尺形可尺规规作作图图的充要条件是的充要条件是n的最大的最大单单因数是不同的因数是不同的费马质费马质数的乘数的乘积积。例如：正例如：正3、5、15、17边边形等。形等。2024/5/25 周六阜阳师范学院 数科院56证：（反证法）证：（反证法）2024/5/25 周六阜阳师范学院 数科院572024/5/25 周六阜阳师范学院 数科院581.5 1.5 函数函数 x 与与 x 及其在数论中的应用及其在数论中的应用定定义义：设设x是是实实数，以数，以x表示不超表示不超过过x的最大整数，的最大整数，称它称它为为x的整数部分，称的整数部分，称x=x x为为x的小数部分的小数部分.一、函数一、函数 x 与与 x 及其性质及其性质2024/5/25 周六阜阳师范学院 数科院59定理定理1 1 对对于于x与与x，有下列，有下列结论结论成立成立2024/5/25 周六阜阳师范学院 数科院602024/5/25 周六阜阳师范学院 数科院612024/5/25 周六阜阳师范学院 数科院622024/5/25 周六阜阳师范学院 数科院63二、函数二、函数 x 与与 x 的一个应用的一个应用定理定理2 在在n!的的标标准分解式中准分解式中质质因数因数 例例1 求求 20！分解式中！分解式中质质因数因数2的个数。的个数。2024/5/25 周六阜阳师范学院 数科院64定理定理2 2的证明：的证明：下面以下面以15!15!为例说明为例说明.2024/5/25 周六阜阳师范学院 数科院65考虑考虑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个；个；2024/5/25 周六阜阳师范学院 数科院66例例2 2 求求12!12!的标准分解式。的标准分解式。解：解：1212以内的质数有以内的质数有2 2，3 3，5 5，7 7，11.11.其标准分解式中，各质因数的个数如下：其标准分解式中，各质因数的个数如下：所以所以 12!12!的标准分解式为的标准分解式为2024/5/25 周六阜阳师范学院 数科院67推论推论2 2 贾宪数贾宪数 证证明：由定理明：由定理2，对对于任意的于任意的质质数数p，整数，整数n!，k!与与(n k)!的的标标准分解式中所含的准分解式中所含的p的指数分的指数分别别是是 利用定理利用定理1(4)可知可知 2024/5/25 周六阜阳师范学院 数科院68