§2初等数论-整除

数论是竞赛数学中最重要的一局部，特别是在1991年，IMO在中国举行，国际上戏称那一年为数论年，因为6道IMO试题中有5道与数论有关。数论的魅力在于它可以适合小孩到老头，只要有算术根底的人均可以研究数论――在前几年还盛传广东的一位农民数学爱好者证明了哥德巴赫猜测，当然，这一谣言最终被澄清了。可是这也说明了最难的数论问题，适合于任何人去研究。初等数论最根底的理论在于整除，由它可以演化出许多数论定理。2024/1/22阜阳师范学院数科院2第一章整数的可除性整除性理论是初等数论的根底，本章要介绍带余数除法，辗转相除法，最大公约数，最小公算术根本定理以及倍数，它们的一些应用。2024/1/22阜阳师范学院数科院3中小学数学中的一些数论问题：4.:782+8161能被57整除，求证：783+8163也能被57整除。1.设n为整数，求证:24∣n(n+2)(5n+1)(5n－1).2.66︱X1998Y，求所有满足条件的六位数X1998Y.3.有一个自然数乘以9后，得到一个仅由数字1组成的多位数，求这个自然数最小为多少？2024/1/2245.100个正整数之和为101101，那么它们的最大公约数的最大可能值是多少?证明你的结论。2024/1/225§1.1整除的概念带余数除法一、整除的概念相关概念：因数、约数、倍数、奇数、偶数。注：显然每个非零整数a都有约数

1，a，称这四个数为a的平凡约数，a的另外的约数称为非平凡约数。例1

有一个自然数乘以9后，得到一个仅由数字1组成的多位数，求这个自然数最小为多少？123456792024/1/226二、整除的性质定理1〔传递性〕定理2定理3例2(1)：x和y是整数，13︱(9x+10y)，求证：13︱(4x+3y)；(2)假设a,b是整数，且7∣(a+b),7∣(2a－b)，证明:7|(5a+2b)。2024/1/227三、带余数除法定理4设a与b是两个整数，b>0，那么存在唯一的两个整数q和r，使得定义2：〔1〕式通常写成并称q为a被b除所得的不完全商；r叫做a被b除所得的余数；(2)式称为带余数除法。2024/1/228证明：存在性：考虑整数序列那么a必在序列的某两项之间(包括这两项〕，即存在一个整数q，使得唯一性：反证〔略〕定理4设a与b是两个整数，b>0，则存在唯一的两个整数q和r，使得2024/1/229例3利用带余数除法，由a,b的值求q,r.如果允许b取负值，则要求思考正确吗？2024/1/2210证明：由带余除法有2024/1/22阜阳师范学院数科院11例5设n为整数，求证：24∣n(n+2)(5n+1)(5n－1).证明：f(n)=n(n+2)(5n+1)(5n－1)=n(n+2)[(n2－1)+24n2]=(n－1)n(n+1)(n+2)+24n3(n+2)∵4!∣(n－1)n(n+1)(n+2),24∣24n3(n+2)∴24∣f(n).练习：对于任意的五个自然数,证明其中必有3个数的和能被3整除。2024/1/22阜阳师范学院数科院12例6：782+8161能被57整除，求证：783+8163也能被57整除。证明：783+8163=7(782+8161)－7×8161+8163=7(782+8161)+8161×57∵782+8161和57都能被57整除∴原式得证。2024/1/22阜阳师范学院数科院13习题选讲P4－4

设a,b是任意两个整数，

证明：存在两个整数s,t，使得并且，当b为奇数时，s,t是唯一的。b为偶数呢？那么a必在此序列的某两项之间，2024/1/22阜阳师范学院数科院14存在性得证；下证唯一性.2024/1/22阜阳师范学院数科院15当b为奇数时，②式中的等号不能成立，

当b为偶数时,s,t可以不唯一，举例如下：注：该例为简化辗转相除法求最大公约数提供了依据。2024/1/22阜阳师范学院数科院162024/1/22阜阳师范学院数科院17§1.2最大公因数与辗转相除法一、最大公因数例1两个自然数的和为165，它们的最大公约数为15，求这两个数。15与150，或30与135，或45与120，或60与105，或75与90.2024/1/22阜阳师范学院数科院18练习：100个正整数之和为101101，那么它们的最大公约数的最大可能值是多少?证明你的结论。假设这100个数互不相同呢？1001定理1：〔有关最大公因数的结论〕注：定理1(3)给出了求最大公因数的方法——辗转相除法.2024/1/22阜阳师范学院数科院19二、辗转相除法定义：设有整数的带余数除法中，每次用余数去除除数，直到余数为0停止，这种运算方法称为辗转相除法。即有(*)或2024/1/22阜阳师范学院数科院20定理2

在上面的表达式(*)中，有证明：另一方面，2024/1/22阜阳师范学院数科院21证明：先考虑两个数的情形，一方面，另一方面，由辗转相除法可以得到，对于多个整数的公因数，利用可以证明.2024/1/22阜阳师范学院数科院22例2

求下面各组数的最大公因数。解：18591573115732865143014322860注：亦可通过分解因数的方法求最大公因数.2024/1/22阜阳师范学院数科院23补充说明：利用§1.1习题4的结论，可以使得辗转相除法求最大公因数更为快速一些。每次除得余数的绝对值不超过除数的一半，余数可以为负。例3求〔76501，9719〕.765019719877752125181000828941156953285424961440=1.2024/1/22阜阳师范学院数科院24定理4说明：〔1〕在(*)式中，所有各项都乘以m可以得证。〔2〕由(1)即可得证。2024/1/22阜阳师范学院数科院25定理52024/1/22阜阳师范学院数科院26例4

求最大公约数：方法一：利用定理5.方法二：分解因数.48721082243654212182734692024/1/22阜阳师范学院数科院27例5利用辗转相除法计算(27090,21672,11352).270902167211352222704〔2〕22704438610321111352441280258410320所以，(27090,21672,11352)=258.2024/1/22阜阳师范学院数科院28例6证明：假设n是正整数，那么2024/1/22阜阳师范学院数科院29定理6设a，b不全为0，那么存在整数s,t，使得证明：利用P4习题1-3的结论.一方面，另一方面，2024/1/22阜阳师范学院数科院30特别地，证：必要性的证明由定理6直接可得。2024/1/22阜阳师范学院数科院31推论1证明：2024/1/22阜阳师范学院数科院32推论2证明：另解：利用推论12024/1/22阜阳师范学院数科院33.思考题：用辗转相除法求x，y，使得125x

17y

=(125,17).2024/1/22阜阳师范学院数科院34习题选讲2024/1/22阜阳师范学院数科院35

4、证明：在辗转相除法中的n满足：

证：由P3§1习题4知：

2024/1/22阜阳师范学院数科院362024/1/22阜阳师范学院数科院37§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|。2024/1/22阜阳师范学院数科院38定理2

对任意的正整数a，b，有证明：设m是a和b的一个公倍数，那么存在整数k1，k2，使得m=ak1，m=bk2，因此

ak1=bk2.

2024/1/22阜阳师范学院数科院39推论1两个整数的任何公倍数一定是最小公倍数的倍数。推论2设m，a，b是正整数，那么[ma,mb]=m[a,b]。2024/1/22阜阳师范学院数科院40定理3注：把多个整数的公倍数化为两个数的公倍数来计算。推论假设m是a1,a2,,an的公倍数，那么[a1,a2,,an]m。2024/1/22阜阳师范学院数科院41定理4

整数a1,a2,

,an两两互素，即(ai,aj)=1，1

i,j

n，i

j

的充要条件是[a1,a2,

,an]=a1a2

an.例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/1/22阜阳师范学院数科院42多项式的带余式除法称为n次多项式.注：整数的带余数除法推广到多项式的带余式除法，其他方面的性质〔整除的性质、辗转相除法、约数、倍数等〕也可以作类似地推广。2024/1/22阜阳师范学院数科院43习题讲解：2024/1/22阜阳师范学院数科院44构造方程其有理根只能为2024/1/22阜阳师范学院数科院452024/1/22阜阳师范学院数科院46§1.4质数算术根本定理一、质数与合数定义：假设整数a0，1，并且只有约数1和a，那么称a是素数〔或质数〕；否那么称a为合数。注：本书中假设无特别说明，素数总是指正素数。定理1设a是大于1的整数，那么〔1〕a除1外的最小正因数q是质数；〔2〕假设a是合数，那么2024/1/22阜阳师范学院数科院47求质数的方法例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.2024/1/22阜阳师范学院数科院48分析：利用定理2反证即得.注意：在推论中，假设p不是质数，那么结论不能成立。2024/1/22阜阳师范学院数科院49二、算术根本定理定理3〔算术根本定理〕任一大于1的整数n能表示成质数的乘积，且其分解的结果是唯一的[不考虑次序].即有：n=p1p2pm(1)其中pi〔1im〕是素数.证明当n=2时，结论显然成立。由于2

d

k，由归纳假定知存在素数q1,q2,

,ql，使得d=q1q2

ql，从而k

1=pq1q2

ql。假设对于2

n

k，式(1)成立，下证式(1)对于n=k

1也成立，从而由归纳法推出式(1)对任何大于1的整数n成立。如果k

1是素数，式(1)显然成立。假设k1是合数，那么存在素数p与整数d，使得k1=pd。2024/1/22阜阳师范学院数科院50推论3.1〔标准分解式〕推论3.2a的正因数可以表示为a的分解式中的局部因数的乘积。推论3.3设a,b是任意两个正整数，且推论3.3是分解质因数方法求最大公因数和最小公倍数的依据。2024/1/22阜阳师范学院数科院51定理4质数的个数是无穷的。证：假设质数的个数有限，记为所以存在质数p,

所以，质数的个数是无穷的。2024/1/22阜阳师范学院数科院52例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/1/22阜阳师范学院数科院53例3证明：(a,b)[a,b]=ab.

其中p1,p2,

,pk是互不相同的素数，i，i〔1ik〕都是非负整数。(a,b)[a,b]=

2024/1/22阜阳师范学院数科院542024/1/22阜阳师范学院数科院55三、费马数及其他费马数尺规作图问题：正n边形可尺规作图的充要条件是n的最大单因数是不同的费马质数的乘积。例如：正3、5、15、17边形等。

2024/1/22阜阳师范学院数科院56证：〔反证法〕2024/1/22阜阳师范学院数科院572024/1/22阜阳师范学院数科院58§1.5函数[x]与{x}及其在数论中的应用定义：设x是实数，以[x]表示不超过x的最大整数，称它为x的整数局部，称{x}=x[x]为x的小数局部.一、函数[x]与{x}及其性质2024