初等数论整除

1、初等数论整除2022/9/3阜阳师范学院 数科院1第1页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院2中小学数学中的一些数论问题：4.已知: 782 + 8161能被57整除，求证：783 +8163也能被57整除。1.狐狸在跑道上跳远，每次跳远150CM从起点开始每 隔130CM设一个陷阱，问狐狸跳了几次后掉进井中？2.已知66X1998Y，求所有满足条件的六位数X1998Y.3.有一个自然数乘以9后，得到一个仅由数字1组成的多位数，求这个自然数最小为多少？第2页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学

2、院 数科院35.设n为整数，求证:24n(n+2)(5n+1)(5n1).6. 100个正整数之和为101101，则它们的最大公约 数的最大可能值是多少?证明你的结论。 第3页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院41.1 整除的概念 带余数除法一、整除的概念相关概念：因数、约数、倍数、奇数、偶数。注：显然每个非零整数a都有约数 1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。例1 有一个自然数乘以9后，得到一个仅由数字1组成的多位数，求这个自然数最小为多少？ 12345679 第4页，共67页，2022年，5月20日，13

3、点35分，星期一2022/9/3阜阳师范学院 数科院5二、整除的性质定理1传递性 定理2 定理3 例2 (1) 已知：x和y是整数，13( 9x + 10y )， 求证：13( 4x + 3y )；(2)若 a ,b 是整数，且7( a + b ), 7( 2ab )，证明:7|( 5a + 2b )。 第5页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院6三、带余数除法定理4 设a与b是两个整数，b 0，则存在唯一的两个整数q和r，使得 定义2：（1）式通常写成并称q为a被b除所得的不完全商；r叫做a被b除所得的余数；(2)式称为带余数除法。第6

4、页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院7证明：存在性：考虑整数序列则a必在序列的某两项之间， 即存在一个整数q，使得 唯一性：反证略定理4 设a与b是两个整数，b 0，则存在唯一的两个整数q和r，使得 第7页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院8例3 利用带余数除法，由a, b的值求q, r .如果允许b取负值，则要求 思考正确吗？第8页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院9证明：由带余除法有 第9页，共67页，2022年，5月

5、20日，13点35分，星期一2022/9/3阜阳师范学院 数科院10例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整除。第10页，共67页，2022年，5月20日，13点35分

6、，星期一2022/9/3阜阳师范学院 数科院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年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院12习题选讲P44 设a, b是任意两个整数， 证明：存在两个整数s, t，使得并且，当b为奇数时，s, t是唯一的。b为偶数呢？则a必在此序列的某两项之间， 第12页

7、，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院13存在性得证 ；下证唯一性.第13页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院14当b为奇数时，式中的等号不能成立， 当b为偶数时,s, t可以不唯一，举例如下：注：该例为简化辗转相除法求最大公约数提供了依据。第14页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院15第15页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院161.2 最大公因数与辗转相除法一、最大

8、公因数例1 已知两个自然数的和为165，它们的最大公约数 为15，求这两个数。15与150，或30与135，或45与120，或60与105，或75与90.第16页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院17练习：100个正整数之和为101101，则它们的最大公约数的最大可能值是多少?证明你的结论。若这100个数互不相同呢？1001定理1：有关最大公因数的结论注：定理1(3)给出了求最大公因数的方法辗转相除法.第17页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院18二、辗转相除法定义：设有整数 的

9、带余数除法中， 每次用余数去除除数，直到余数为0停止，这种运算方法称为辗转相除法。即有( * ) 或第18页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院19定理2 在上面的表达式( * )中，有 证明：另一方面，第19页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院20证明：先考虑两个数的情形， 一方面， 另一方面，由辗转相除法可以得到， 对于多个整数的公因数，利用 可以证明.第20页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院21例2 求下面各组数的最

10、大公因数。解：1859 1573115732865143014322860注：亦可通过分解因数的方法求最大公因数.第21页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院22补充说明：利用1.1习题4的结论，可以使得辗转相除法求最大公因数更为快速一些。每次除得余数的绝对值不超过除数的一半，余数可以为负。例3 求（76501，9719）.76501 9719877752125181000828941156953285424961440=1.第22页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院23定理4说明

11、：（1）在 ( * )式中，所有各项都乘以m可以得证。 （2）由(1)即可得证。第23页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院24定理5第24页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院25例4 求最大公约数 ： 方法一：利用定理5.方法二：分解因数.48 72 108224 36 54212 18 27 34 6 9第25页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院26例5 利用辗转相除法计算 (27090, 21672, 11352).

12、27090 21672 11352222704（2）227044386 1032 111135244128 0258 41032 0所以，(27090, 21672, 11352)=258.第26页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院27例6 证明：若n是正整数，则 第27页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院28定理6 设a，b不全为0，则存在整数 s, t，使得证明：利用P4习题1-3的结论.一方面，另一方面，第28页，共67页，2022年，5月20日，13点35分，星期一202

13、2/9/3阜阳师范学院 数科院29特别地，证：必要性的证明由定理6直接可得。 第29页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院30推论1证明：第30页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院31推论2证明：另解：利用推论1第31页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院32.思考题：用辗转相除法求x，y，使得125x 17y = (125, 17).第32页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院

14、 数科院33习题选讲第33页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院34 4、证明：在辗转相除法中的n满足： 证：由P31习题4知： 第34页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院35第35页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院361.3 最小公倍数定义1 ： 整数a1, a2, , ak的公共倍数称为a1, a2, , ak的公倍数。a1, a2, , ak的正公倍数中的最小的一个叫做a1, a2, , ak的最小公倍数，记为a1,

15、 a2, , ak.定理1： 下面的等式成立：() a, 1 = |a|，a, a = |a|；() a, b = b, a；() a1, a2, , ak = |a1|, |a2| , |ak|；() 若ab，则a, b = |b|。第36页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院37定理2 对任意的正整数a，b，有证明： 设m是a和b的一个公倍数，那么存在整数k1，k2，使得m = ak1，m = bk2，因此 ak1 = bk2 . 第37页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院38

16、推论1 两个整数的任何公倍数一定是最小公倍数的倍数。推论2 设m，a，b是正整数，则ma, mb = ma, b。第38页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院39定理3注：把多个整数的公倍数化为两个数的公倍数来计算。推论 若m是a1, a2, , an的公倍数，则a1, a2, , anm 。第39页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院40定理4 整数a1, a2, , an两两互素，即(ai, aj) = 1，1 i, j n，i j 的充要条件是a1, a2, , an = a1

17、a2an .例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年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院41多项式的带余式除法称为n次多项式. 注：整数的带余数除法推广到多项式的带余式除法，其他方面的性质整除的性质、辗转相除法、约数、倍数等也可以作类似地推广。第41页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院4

18、2习题讲解：第42页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院43构造方程 其有理根只能为第43页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院44第44页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院451.4 质数 算术基本定理一、质数与合数定义：若整数a 0，1，并且只有约数 1和 a，则称a是素数（或质数）；否则称a为合数。 注：本书中若无特别说明，素数总是指正素数。 定理1 设a是大于1的整数，则（1）a 除1外的最小正因数q是质数；（2）若a

19、是合数，则 第45页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院46求质数的方法 例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.第46页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院47分析：利用定理2反证即得.注意：在推论中，若p不是质数，则结论不能成立。第47页，共67页，20

20、22年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院48二、算术基本定理定理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成立。如果k 1是素数，式(1)显然成立。若k 1是合数，则存在素数p与

21、整数d，使得k 1 = pd。第48页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院49推论3.1标准分解式 推论3.2 a的正因数可以表示为a的分解式中的部分因数的乘积。推论3.3 设a,b是任意两个正整数，且推论3.3是分解质因数方法求最大公因数和最小公倍数的依据。 第49页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院50定理4 质数的个数是无穷的。证：假设质数的个数有限，记为 所以存在质数p, 所以，质数的个数是无穷的。第50页，共67页，2022年，5月20日，13点35分，星期一2022/9

22、/3阜阳师范学院 数科院51例2 写出51480的标准分解式。解：51480 = 225740= 2212870= 2351287= 2353429= 23532143= 233251113。= 236435第51页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院52例3 证明：(a, b)a, b = ab. 其中p1, p2, , pk是互不相同的素数，i，i（1 i k）都是非负整数。(a, b)a, b = 第52页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院53第53页，共67页，2022年，

23、5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院54三、费马数及其他 费马数 尺规作图问题： 正n边形可尺规作图的充要条件是n的最大单因数是不同的费马质数的乘积。例如：正3、5、15、17边形等。 第54页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院55证：（反证法）第55页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院56第56页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院571.5 函数x与x及其在数论中的应用定义： 设x是实数，以x表示不超过x的最大整数，称它为x的整数部分，称x = x x为x的小数部分.一、函数x与x及其性质第57页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院58定理1 对于x与x，有下列结论成立第58页，共67页，2022年，5月20日，13点35分，星期一2022/9/3阜阳师范学院 数科院5