§2初等數(shù)論-整除

數(shù)論是競賽數(shù)學(xué)中最重要的一局部，特別是在1991年，IMO在中國舉行，國際上戲稱那一年為數(shù)論年，因為6道IMO試題中有5道與數(shù)論有關(guān)。數(shù)論的魅力在于它可以適合小孩到老頭，只要有算術(shù)根底的人均可以研究數(shù)論――在前幾年還盛傳廣東的一位農(nóng)民數(shù)學(xué)愛好者證明了哥德巴赫猜測，當然，這一謠言最終被澄清了?？墒沁@也說明了最難的數(shù)論問題，適合于任何人去研究。初等數(shù)論最根底的理論在于整除，由它可以演化出許多數(shù)論定理。2024/1/22阜陽師范學(xué)院數(shù)科院2第一章整數(shù)的可除性整除性理論是初等數(shù)論的根底，本章要介紹帶余數(shù)除法，輾轉(zhuǎn)相除法，最大公約數(shù)，最小公算術(shù)根本定理以及倍數(shù)，它們的一些應(yīng)用。2024/1/22阜陽師范學(xué)院數(shù)科院3中小學(xué)數(shù)學(xué)中的一些數(shù)論問題：4.:782+8161能被57整除，求證：783+8163也能被57整除。1.設(shè)n為整數(shù)，求證:24∣n(n+2)(5n+1)(5n－1).2.66︱X1998Y，求所有滿足條件的六位數(shù)X1998Y.3.有一個自然數(shù)乘以9后，得到一個僅由數(shù)字1組成的多位數(shù)，求這個自然數(shù)最小為多少？2024/1/2245.100個正整數(shù)之和為101101，那么它們的最大公約數(shù)的最大可能值是多少?證明你的結(jié)論。2024/1/225§1.1整除的概念帶余數(shù)除法一、整除的概念相關(guān)概念：因數(shù)、約數(shù)、倍數(shù)、奇數(shù)、偶數(shù)。注：顯然每個非零整數(shù)a都有約數(shù)

1，a，稱這四個數(shù)為a的平凡約數(shù)，a的另外的約數(shù)稱為非平凡約數(shù)。例1

有一個自然數(shù)乘以9后，得到一個僅由數(shù)字1組成的多位數(shù)，求這個自然數(shù)最小為多少？123456792024/1/226二、整除的性質(zhì)定理1〔傳遞性〕定理2定理3例2(1)：x和y是整數(shù)，13︱(9x+10y)，求證：13︱(4x+3y)；(2)假設(shè)a,b是整數(shù)，且7∣(a+b),7∣(2a－b)，證明:7|(5a+2b)。2024/1/227三、帶余數(shù)除法定理4設(shè)a與b是兩個整數(shù)，b>0，那么存在唯一的兩個整數(shù)q和r，使得定義2：〔1〕式通常寫成并稱q為a被b除所得的不完全商；r叫做a被b除所得的余數(shù)；(2)式稱為帶余數(shù)除法。2024/1/228證明：存在性：考慮整數(shù)序列那么a必在序列的某兩項之間(包括這兩項〕，即存在一個整數(shù)q，使得唯一性：反證〔略〕定理4設(shè)a與b是兩個整數(shù)，b>0，則存在唯一的兩個整數(shù)q和r，使得2024/1/229例3利用帶余數(shù)除法，由a,b的值求q,r.如果允許b取負值，則要求思考正確嗎？2024/1/2210證明：由帶余除法有2024/1/22阜陽師范學(xué)院數(shù)科院11例5設(shè)n為整數(shù)，求證：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).練習(xí)：對于任意的五個自然數(shù),證明其中必有3個數(shù)的和能被3整除。2024/1/22阜陽師范學(xué)院數(shù)科院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阜陽師范學(xué)院數(shù)科院13習(xí)題選講P4－4

設(shè)a,b是任意兩個整數(shù)，

證明：存在兩個整數(shù)s,t，使得并且，當b為奇數(shù)時，s,t是唯一的。b為偶數(shù)呢？那么a必在此序列的某兩項之間，2024/1/22阜陽師范學(xué)院數(shù)科院14存在性得證；下證唯一性.2024/1/22阜陽師范學(xué)院數(shù)科院15當b為奇數(shù)時，②式中的等號不能成立，

當b為偶數(shù)時,s,t可以不唯一，舉例如下：注：該例為簡化輾轉(zhuǎn)相除法求最大公約數(shù)提供了依據(jù)。2024/1/22阜陽師范學(xué)院數(shù)科院162024/1/22阜陽師范學(xué)院數(shù)科院17§1.2最大公因數(shù)與輾轉(zhuǎn)相除法一、最大公因數(shù)例1兩個自然數(shù)的和為165，它們的最大公約數(shù)為15，求這兩個數(shù)。15與150，或30與135，或45與120，或60與105，或75與90.2024/1/22阜陽師范學(xué)院數(shù)科院18練習(xí)：100個正整數(shù)之和為101101，那么它們的最大公約數(shù)的最大可能值是多少?證明你的結(jié)論。假設(shè)這100個數(shù)互不相同呢？1001定理1：〔有關(guān)最大公因數(shù)的結(jié)論〕注：定理1(3)給出了求最大公因數(shù)的方法——輾轉(zhuǎn)相除法.2024/1/22阜陽師范學(xué)院數(shù)科院19二、輾轉(zhuǎn)相除法定義：設(shè)有整數(shù)的帶余數(shù)除法中，每次用余數(shù)去除除數(shù)，直到余數(shù)為0停止，這種運算方法稱為輾轉(zhuǎn)相除法。即有(*)或2024/1/22阜陽師范學(xué)院數(shù)科院20定理2

在上面的表達式(*)中，有證明：另一方面，2024/1/22阜陽師范學(xué)院數(shù)科院21證明：先考慮兩個數(shù)的情形，一方面，另一方面，由輾轉(zhuǎn)相除法可以得到，對于多個整數(shù)的公因數(shù)，利用可以證明.2024/1/22阜陽師范學(xué)院數(shù)科院22例2

求下面各組數(shù)的最大公因數(shù)。解：18591573115732865143014322860注：亦可通過分解因數(shù)的方法求最大公因數(shù).2024/1/22阜陽師范學(xué)院數(shù)科院23補充說明：利用§1.1習(xí)題4的結(jié)論，可以使得輾轉(zhuǎn)相除法求最大公因數(shù)更為快速一些。每次除得余數(shù)的絕對值不超過除數(shù)的一半，余數(shù)可以為負。例3求〔76501，9719〕.765019719877752125181000828941156953285424961440=1.2024/1/22阜陽師范學(xué)院數(shù)科院24定理4說明：〔1〕在(*)式中，所有各項都乘以m可以得證。〔2〕由(1)即可得證。2024/1/22阜陽師范學(xué)院數(shù)科院25定理52024/1/22阜陽師范學(xué)院數(shù)科院26例4

求最大公約數(shù)：方法一：利用定理5.方法二：分解因數(shù).48721082243654212182734692024/1/22阜陽師范學(xué)院數(shù)科院27例5利用輾轉(zhuǎn)相除法計算(27090,21672,11352).270902167211352222704〔2〕22704438610321111352441280258410320所以，(27090,21672,11352)=258.2024/1/22阜陽師范學(xué)院數(shù)科院28例6證明：假設(shè)n是正整數(shù)，那么2024/1/22阜陽師范學(xué)院數(shù)科院29定理6設(shè)a，b不全為0，那么存在整數(shù)s,t，使得證明：利用P4習(xí)題1-3的結(jié)論.一方面，另一方面，2024/1/22阜陽師范學(xué)院數(shù)科院30特別地，證：必要性的證明由定理6直接可得。2024/1/22阜陽師范學(xué)院數(shù)科院31推論1證明：2024/1/22阜陽師范學(xué)院數(shù)科院32推論2證明：另解：利用推論12024/1/22阜陽師范學(xué)院數(shù)科院33.思考題：用輾轉(zhuǎn)相除法求x，y，使得125x

17y

=(125,17).2024/1/22阜陽師范學(xué)院數(shù)科院34習(xí)題選講2024/1/22阜陽師范學(xué)院數(shù)科院35

4、證明：在輾轉(zhuǎn)相除法中的n滿足：

證：由P3§1習(xí)題4知：

2024/1/22阜陽師范學(xué)院數(shù)科院362024/1/22阜陽師范學(xué)院數(shù)科院37§1.3最小公倍數(shù)定義1

：整數(shù)a1,a2,

,ak的公共倍數(shù)稱為a1,a2,,ak的公倍數(shù)。a1,a2,,ak的正公倍數(shù)中的最小的一個叫做a1,a2,,ak的最小公倍數(shù)，記為[a1,a2,,ak].定理1：下面的等式成立：(ⅰ)[a,1]=|a|，[a,a]=|a|；(ⅱ)[a,b]=[b,a]；(ⅲ)[a1,a2,,ak]=[|a1|,|a2|,|ak|]；(ⅳ)假設(shè)ab，那么[a,b]=|b|。2024/1/22阜陽師范學(xué)院數(shù)科院38定理2

對任意的正整數(shù)a，b，有證明：設(shè)m是a和b的一個公倍數(shù)，那么存在整數(shù)k1，k2，使得m=ak1，m=bk2，因此

ak1=bk2.

2024/1/22阜陽師范學(xué)院數(shù)科院39推論1兩個整數(shù)的任何公倍數(shù)一定是最小公倍數(shù)的倍數(shù)。推論2設(shè)m，a，b是正整數(shù)，那么[ma,mb]=m[a,b]。2024/1/22阜陽師范學(xué)院數(shù)科院40定理3注：把多個整數(shù)的公倍數(shù)化為兩個數(shù)的公倍數(shù)來計算。推論假設(shè)m是a1,a2,,an的公倍數(shù)，那么[a1,a2,,an]m。2024/1/22阜陽師范學(xué)院數(shù)科院41定理4

整數(shù)a1,a2,

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

i,j

n，i

j

的充要條件是[a1,a2,

,an]=a1a2

an.例3設(shè)a，b，c是正整數(shù)，證明[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阜陽師范學(xué)院數(shù)科院42多項式的帶余式除法稱為n次多項式.注：整數(shù)的帶余數(shù)除法推廣到多項式的帶余式除法，其他方面的性質(zhì)〔整除的性質(zhì)、輾轉(zhuǎn)相除法、約數(shù)、倍數(shù)等〕也可以作類似地推廣。2024/1/22阜陽師范學(xué)院數(shù)科院43習(xí)題講解：2024/1/22阜陽師范學(xué)院數(shù)科院44構(gòu)造方程其有理根只能為2024/1/22阜陽師范學(xué)院數(shù)科院452024/1/22阜陽師范學(xué)院數(shù)科院46§1.4質(zhì)數(shù)算術(shù)根本定理一、質(zhì)數(shù)與合數(shù)定義：假設(shè)整數(shù)a0，1，并且只有約數(shù)1和a，那么稱a是素數(shù)〔或質(zhì)數(shù)〕；否那么稱a為合數(shù)。注：本書中假設(shè)無特別說明，素數(shù)總是指正素數(shù)。定理1設(shè)a是大于1的整數(shù)，那么〔1〕a除1外的最小正因數(shù)q是質(zhì)數(shù)；〔2〕假設(shè)a是合數(shù)，那么2024/1/22阜陽師范學(xué)院數(shù)科院47求質(zhì)數(shù)的方法例1求30以內(nèi)的質(zhì)數(shù).劃去2、3、5的倍數(shù)，得到不能被2、3、5整除的數(shù)有7、11、13、17、19、23、29.所以30以內(nèi)的質(zhì)數(shù)有2、3、5、7、11、13、17、19、23、29.該方法稱為幼拉脫斯展納篩法，利用該方法可以構(gòu)造質(zhì)數(shù)表，祥見教材P17-18.2024/1/22阜陽師范學(xué)院數(shù)科院48分析：利用定理2反證即得.注意：在推論中，假設(shè)p不是質(zhì)數(shù)，那么結(jié)論不能成立。2024/1/22阜陽師范學(xué)院數(shù)科院49二、算術(shù)根本定理定理3〔算術(shù)根本定理〕任一大于1的整數(shù)n能表示成質(zhì)數(shù)的乘積，且其分解的結(jié)果是唯一的[不考慮次序].即有：n=p1p2pm(1)其中pi〔1im〕是素數(shù).證明當n=2時，結(jié)論顯然成立。由于2

d

k，由歸納假定知存在素數(shù)q1,q2,

,ql，使得d=q1q2

ql，從而k

1=pq1q2

ql。假設(shè)對于2

n

k，式(1)成立，下證式(1)對于n=k

1也成立，從而由歸納法推出式(1)對任何大于1的整數(shù)n成立。如果k

1是素數(shù)，式(1)顯然成立。假設(shè)k1是合數(shù)，那么存在素數(shù)p與整數(shù)d，使得k1=pd。2024/1/22阜陽師范學(xué)院數(shù)科院50推論3.1〔標準分解式〕推論3.2a的正因數(shù)可以表示為a的分解式中的局部因數(shù)的乘積。推論3.3設(shè)a,b是任意兩個正整數(shù)，且推論3.3是分解質(zhì)因數(shù)方法求最大公因數(shù)和最小公倍數(shù)的依據(jù)。2024/1/22阜陽師范學(xué)院數(shù)科院51定理4質(zhì)數(shù)的個數(shù)是無窮的。證：假設(shè)質(zhì)數(shù)的個數(shù)有限，記為所以存在質(zhì)數(shù)p,

所以，質(zhì)數(shù)的個數(shù)是無窮的。2024/1/22阜陽師范學(xué)院數(shù)科院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阜陽師范學(xué)院數(shù)科院53例3證明：(a,b)[a,b]=ab.

其中p1,p2,

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

2024/1/22阜陽師范學(xué)院數(shù)科院542024/1/22阜陽師范學(xué)院數(shù)科院55三、費馬數(shù)及其他費馬數(shù)尺規(guī)作圖問題：正n邊形可尺規(guī)作圖的充要條件是n的最大單因數(shù)是不同的費馬質(zhì)數(shù)的乘積。例如：正3、5、15、17邊形等。

2024/1/22阜陽師范學(xué)院數(shù)科院56證：〔反證法〕2024/1/22阜陽師范學(xué)院數(shù)科院572024/1/22阜陽師范學(xué)院數(shù)科院58§1.5函數(shù)[x]與{x}及其在數(shù)論中的應(yīng)用定義：設(shè)x是實數(shù)，以[x]表示不超過x的最大整數(shù)，稱它為x的整數(shù)局部，稱{x}=x[x]為x的小數(shù)局部.一、函數(shù)[x]與{x}及其性質(zhì)2024