初等數(shù)論整除2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院1第一頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院2中小學(xué)數(shù)學(xué)中的一些數(shù)論問(wèn)題：4.已知:782+8161能被57整除，求證：783+8163也能被57整除。1.狐貍在跑道上跳遠(yuǎn)，每次跳遠(yuǎn)150CM從起點(diǎn)開(kāi)始每隔130CM設(shè)一個(gè)陷阱，問(wèn)狐貍跳了幾次后掉進(jìn)井中？2.已知66︱X1998Y，求所有滿(mǎn)足條件的六位數(shù)X1998Y.3.有一個(gè)自然數(shù)乘以9后，得到一個(gè)僅由數(shù)字1組成的多位數(shù)，求這個(gè)自然數(shù)最小為多少？第二頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院35.設(shè)n為整數(shù)，求證:24∣n(n+2)(5n+1)(5n－1).6.100個(gè)正整數(shù)之和為101101，則它們的最大公約數(shù)的最大可能值是多少?證明你的結(jié)論。第三頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院4§1.1整除的概念帶余數(shù)除法一、整除的概念相關(guān)概念：因數(shù)、約數(shù)、倍數(shù)、奇數(shù)、偶數(shù)。注：顯然每個(gè)非零整數(shù)a都有約數(shù)1，a，稱(chēng)這四個(gè)數(shù)為a的平凡約數(shù)，a的另外的約數(shù)稱(chēng)為非平凡約數(shù)。例1

有一個(gè)自然數(shù)乘以9后，得到一個(gè)僅由數(shù)字1組成的多位數(shù)，求這個(gè)自然數(shù)最小為多少？12345679第四頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院5二、整除的性質(zhì)定理1〔傳遞性〕定理2定理3例2(1)

已知：x和y是整數(shù)，13︱(9x+10y)，求證：13︱(4x+3y)；(2)若a,b

是整數(shù)，且7∣(a+b),7∣(2a－b)，證明:7|(5a+2b)。

第五頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院6三、帶余數(shù)除法定理4設(shè)a與b是兩個(gè)整數(shù)，b>0，則存在唯一的兩個(gè)整數(shù)q和r，使得定義2：（1）式通常寫(xiě)成并稱(chēng)q為a被b除所得的不完全商；r叫做a被b除所得的余數(shù)；(2)式稱(chēng)為帶余數(shù)除法。第六頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院7證明：存在性：考慮整數(shù)序列則a必在序列的某兩項(xiàng)之間，即存在一個(gè)整數(shù)q，使得唯一性：反證〔略〕定理4設(shè)a與b是兩個(gè)整數(shù)，b>0，則存在唯一的兩個(gè)整數(shù)q和r，使得第七頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院8例3利用帶余數(shù)除法，由a,b的值求q,r.如果允許b取負(fù)值，則要求思考正確嗎？第八頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院9證明：由帶余除法有第九頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院10例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í)：對(duì)于任意的五個(gè)自然數(shù),證明其中必有3個(gè)數(shù)的和能被3整除。第十頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院11例6已知：782+8161能被57整除，求證：783+8163也能被57整除。證明：783+8163=7(782+8161)－7×8161+8163=7(782+8161)+8161×57∵782+8161和57都能被57整除∴原式得證。第十一頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院12習(xí)題選講P4－4

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

證明：存在兩個(gè)整數(shù)s,t，使得并且，當(dāng)b為奇數(shù)時(shí)，s,t是唯一的。b為偶數(shù)呢？則a必在此序列的某兩項(xiàng)之間，

第十二頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院13存在性得證；下證唯一性.第十三頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院14當(dāng)b為奇數(shù)時(shí)，②式中的等號(hào)不能成立，

當(dāng)b為偶數(shù)時(shí),s,t可以不唯一，舉例如下：注：該例為簡(jiǎn)化輾轉(zhuǎn)相除法求最大公約數(shù)提供了依據(jù)。第十四頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院15第十五頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院16§1.2最大公因數(shù)與輾轉(zhuǎn)相除法一、最大公因數(shù)例1已知兩個(gè)自然數(shù)的和為165，它們的最大公約數(shù)為15，求這兩個(gè)數(shù)。15與150，或30與135，或45與120，或60與105，或75與90.第十六頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院17練習(xí)：100個(gè)正整數(shù)之和為101101，則它們的最大公約數(shù)的最大可能值是多少?證明你的結(jié)論。若這100個(gè)數(shù)互不相同呢？1001定理1：〔有關(guān)最大公因數(shù)的結(jié)論〕注：定理1(3)給出了求最大公因數(shù)的方法——輾轉(zhuǎn)相除法.第十七頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院18二、輾轉(zhuǎn)相除法定義：設(shè)有整數(shù)的帶余數(shù)除法中，每次用余數(shù)去除除數(shù)，直到余數(shù)為0停止，這種運(yùn)算方法稱(chēng)為輾轉(zhuǎn)相除法。即有(*)或第十八頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院19定理2

在上面的表達(dá)式(*)中，有證明：另一方面，第十九頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院20證明：先考慮兩個(gè)數(shù)的情形，一方面，另一方面，由輾轉(zhuǎn)相除法可以得到，對(duì)于多個(gè)整數(shù)的公因數(shù)，利用可以證明.第二十頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院21例2

求下面各組數(shù)的最大公因數(shù)。解：18591573115732865143014322860注：亦可通過(guò)分解因數(shù)的方法求最大公因數(shù).第二十一頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院22補(bǔ)充說(shuō)明：利用§1.1習(xí)題4的結(jié)論，可以使得輾轉(zhuǎn)相除法求最大公因數(shù)更為快速一些。每次除得余數(shù)的絕對(duì)值不超過(guò)除數(shù)的一半，余數(shù)可以為負(fù)。例3

求（76501，9719）.765019719877752125181000828941156953285424961440=1.第二十二頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院23定理4說(shuō)明：（1）在(*)式中，所有各項(xiàng)都乘以m可以得證。（2）由(1)即可得證。第二十三頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院24定理5第二十四頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院25例4

求最大公約數(shù)：方法一：利用定理5.方法二：分解因數(shù).4872108224365421218273469第二十五頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院26例5利用輾轉(zhuǎn)相除法計(jì)算(27090,21672,11352).270902167211352222704（2）22704438610321111352441280258410320所以，(27090,21672,11352)=258.第二十六頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院27例6證明：若n是正整數(shù)，則

第二十七頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院28定理6設(shè)a，b不全為0，則存在整數(shù)s,t，使得證明：利用P4習(xí)題1-3的結(jié)論.一方面，另一方面，第二十八頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院29特別地，證：必要性的證明由定理6直接可得。第二十九頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院30推論1證明：第三十頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院31推論2證明：另解：利用推論1第三十一頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院32.思考題：用輾轉(zhuǎn)相除法求x，y，使得125x

17y

=(125,17).第三十二頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院33習(xí)題選講第三十三頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院34

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

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

第三十四頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院35第三十五頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院36§1.3最小公倍數(shù)定義1

：整數(shù)a1,a2,,ak的公共倍數(shù)稱(chēng)為a1,a2,,ak的公倍數(shù)。a1,a2,,ak的正公倍數(shù)中的最小的一個(gè)叫做a1,a2,,ak的最小公倍數(shù)，記為[a1,a2,,ak].定理1：下面的等式成立：(ⅰ)[a,1]=|a|，[a,a]=|a|；(ⅱ)[a,b]=[b,a]；(ⅲ)[a1,a2,,ak]=[|a1|,

|a2|,|ak|]；(ⅳ)若ab，則[a,b]=|b|。第三十六頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院37定理2

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

ak1=bk2.

第三十七頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院38推論1兩個(gè)整數(shù)的任何公倍數(shù)一定是最小公倍數(shù)的倍數(shù)。推論2設(shè)m，a，b是正整數(shù)，則[ma,mb]=m[a,b]。第三十八頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院39定理3注：把多個(gè)整數(shù)的公倍數(shù)化為兩個(gè)數(shù)的公倍數(shù)來(lái)計(jì)算。推論若m是a1,a2,,an的公倍數(shù)，則[a1,a2,,an]m

。第三十九頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院40定理4

整數(shù)a1,a2,,an兩兩互素，即(ai,aj)=1，1

i,j

n，i

j

的充要條件是[a1,a2,,an]=a1a2an.例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))代入即得證.第四十頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院41多項(xiàng)式的帶余式除法稱(chēng)為n次多項(xiàng)式.注：整數(shù)的帶余數(shù)除法推廣到多項(xiàng)式的帶余式除法，其他方面的性質(zhì)〔整除的性質(zhì)、輾轉(zhuǎn)相除法、約數(shù)、倍數(shù)等〕也可以作類(lèi)似地推廣。第四十一頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院42習(xí)題講解：第四十二頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院43構(gòu)造方程其有理根只能為第四十三頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院44第四十四頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院45§1.4質(zhì)數(shù)算術(shù)基本定理一、質(zhì)數(shù)與合數(shù)定義：若整數(shù)a

0，1，并且只有約數(shù)1和a，則稱(chēng)a是素?cái)?shù)（或質(zhì)數(shù)）；否則稱(chēng)a為合數(shù)。

注：本書(shū)中若無(wú)特別說(shuō)明，素?cái)?shù)總是指正素?cái)?shù)。定理1設(shè)a是大于1的整數(shù)，則（1）a除1外的最小正因數(shù)q是質(zhì)數(shù)；（2）若a是合數(shù)，則第四十五頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院46求質(zhì)數(shù)的方法例1求30以?xún)?nèi)的質(zhì)數(shù).劃去2、3、5的倍數(shù)，得到不能被2、3、5整除的數(shù)有7、11、13、17、19、23、29.所以30以?xún)?nèi)的質(zhì)數(shù)有2、3、5、7、11、13、17、19、23、29.該方法稱(chēng)為幼拉脫斯展納篩法，利用該方法可以構(gòu)造質(zhì)數(shù)表，祥見(jiàn)教材P17-18.第四十六頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院47分析：利用定理2反證即得.注意：在推論中，若p不是質(zhì)數(shù)，則結(jié)論不能成立。第四十七頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院48二、算術(shù)基本定理定理3〔算術(shù)基本定理〕任一大于1的整數(shù)n能表示成質(zhì)數(shù)的乘積，且其分解的結(jié)果是唯一的[不考慮次序].即有：n=p1p2pm

(1)其中pi（1

i

m）是素?cái)?shù).

證明當(dāng)n=2時(shí)，結(jié)論顯然成立。由于2

d

k，由歸納假定知存在素?cái)?shù)q1,q2,,ql，使得d=q1q2ql，從而k

1=pq1q2ql。假設(shè)對(duì)于2

n

k，式(1)成立，下證式(1)對(duì)于n=k1也成立，從而由歸納法推出式(1)對(duì)任何大于1的整數(shù)n成立。如果k1是素?cái)?shù)，式(1)顯然成立。若k1是合數(shù)，則存在素?cái)?shù)p與整數(shù)d，使得k1=pd。第四十八頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院49推論3.1〔標(biāo)準(zhǔn)分解式〕推論3.2a的正因數(shù)可以表示為a的分解式中的部分因數(shù)的乘積。推論3.3設(shè)a,b是任意兩個(gè)正整數(shù)，且推論3.3是分解質(zhì)因數(shù)方法求最大公因數(shù)和最小公倍數(shù)的依據(jù)。第四十九頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院50定理4質(zhì)數(shù)的個(gè)數(shù)是無(wú)窮的。證：假設(shè)質(zhì)數(shù)的個(gè)數(shù)有限，記為所以存在質(zhì)數(shù)p,

所以，質(zhì)數(shù)的個(gè)數(shù)是無(wú)窮的。第五十頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院51例2寫(xiě)出51480的標(biāo)準(zhǔn)分解式。解：51480=225740=2212870=2351287=2353429=23532143=233251113。=236435第五十一頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院52例3證明：(a,b)[a,b]=ab.

其中p1,p2,,pk是互不相同的素?cái)?shù)，i，i（1

i

k）都是非負(fù)整數(shù)。(a,b)[a,b]=

第五十二頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院53第五十三頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院54三、費(fèi)馬數(shù)及其他費(fèi)馬數(shù)尺規(guī)作圖問(wèn)題：正n邊形可尺規(guī)作圖的充要條件是n的最大單因數(shù)是不同的費(fèi)馬質(zhì)數(shù)的乘積。例如：正3、5、15、17邊形等。

第五十四頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院55證：（反證法）第五十五頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院56第五十六頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院57§1.5函數(shù)[x]與{x}及其在數(shù)論中的應(yīng)用定義：設(shè)x是實(shí)數(shù)，以[x]表示不超過(guò)x的最大整數(shù)，稱(chēng)它為x的整數(shù)部分，稱(chēng){x}=x

[x]為x的小數(shù)部分.一、函數(shù)[x]與{x}及其性質(zhì)第五十七頁(yè)，共六十七頁(yè)，2022年，8月28日2023/3/14阜陽(yáng)師范學(xué)院數(shù)科院58定理1對(duì)于[x]與{x}，有下列結(jié)論成立第五十八頁(yè)，共六十