初等數論1整除課件

2023/9/5阜陽師范學院數科院1中小學數學中的一些數論問題：4.已知:782+8161能被57整除，求證：783+8163也能被57整除。1.狐貍在跑道上跳遠，每次跳遠150CM從起點開始每隔130CM設一個陷阱，問狐貍跳了幾次后掉進井中？2.已知66︱X1998Y，求所有滿足條件的六位數X1998Y.3.有一個自然數乘以9后，得到一個僅由數字1組成的多位數，求這個自然數最小為多少？2023/8/2阜陽師范學院數科院1中小學數學中的一些數2023/9/5阜陽師范學院數科院25.設n為整數，求證:24∣n(n+2)(5n+1)(5n－1).6.100個正整數之和為101101，則它們的最大公約數的最大可能值是多少?證明你的結論。2023/8/2阜陽師范學院數科院25.設n為整數，求證2023/9/5阜陽師范學院數科院3§1.1整除的概念帶余數除法一、整除的概念相關概念：因數、約數、倍數、奇數、偶數。注：顯然每個非零整數a都有約數

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

有一個自然數乘以9后，得到一個僅由數字1組成的多位數，求這個自然數最小為多少？123456792023/8/2阜陽師范學院數科院3§1.1整除的概2023/9/5阜陽師范學院數科院4二、整除的性質定理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)。

2023/8/2阜陽師范學院數科院4二、整除的性質定理12023/9/5阜陽師范學院數科院5三、帶余數除法定理4設a與b是兩個整數，b>0，則存在唯一的兩個整數q和r，使得定義2：（1）式通常寫成并稱q為a被b除所得的不完全商；r叫做a被b除所得的余數；(2)式稱為帶余數除法。2023/8/2阜陽師范學院數科院5三、帶余數除法定理42023/9/5阜陽師范學院數科院6證明：存在性：考慮整數序列則a必在序列的某兩項之間，即存在一個整數q，使得唯一性：反證〔略〕定理4設a與b是兩個整數，b>0，則存在唯一的兩個整數q和r，使得2023/8/2阜陽師范學院數科院6證明：存在性：考慮整2023/9/5阜陽師范學院數科院7例3利用帶余數除法，由a,b的值求q,r.如果允許b取負值，則要求思考正確嗎？2023/8/2阜陽師范學院數科院7例3利用帶余數除法2023/9/5阜陽師范學院數科院8證明：由帶余除法有2023/8/2阜陽師范學院數科院8證明：由帶余除法有2023/9/5阜陽師范學院數科院9例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整除。2023/8/2阜陽師范學院數科院9例5設n為整數，2023/9/5阜陽師范學院數科院10例6已知：782+8161能被57整除，求證：783+8163也能被57整除。證明：783+8163=7(782+8161)－7×8161+8163=7(782+8161)+8161×57∵782+8161和57都能被57整除∴原式得證。2023/8/2阜陽師范學院數科院10例6已知：72023/9/5阜陽師范學院數科院11習題選講P4－4

設a,b是任意兩個整數，

證明：存在兩個整數s,t，使得并且，當b為奇數時，s,t是唯一的。b為偶數呢？則a必在此序列的某兩項之間，

2023/8/2阜陽師范學院數科院11習題選講P4－42023/9/5阜陽師范學院數科院12存在性得證；下證唯一性.2023/8/2阜陽師范學院數科院12存在性得證；下證2023/9/5阜陽師范學院數科院13當b為奇數時，②式中的等號不能成立，

當b為偶數時,s,t可以不唯一，舉例如下：注：該例為簡化輾轉相除法求最大公約數提供了依據。2023/8/2阜陽師范學院數科院13當b為奇數時，②式2023/9/5阜陽師范學院數科院142023/8/2阜陽師范學院數科院142023/9/5阜陽師范學院數科院15§1.2最大公因數與輾轉相除法一、最大公因數例1已知兩個自然數的和為165，它們的最大公約數為15，求這兩個數。15與150，或30與135，或45與120，或60與105，或75與90.2023/8/2阜陽師范學院數科院15§1.2最大公因2023/9/5阜陽師范學院數科院16練習：100個正整數之和為101101，則它們的最大公約數的最大可能值是多少?證明你的結論。若這100個數互不相同呢？1001定理1：〔有關最大公因數的結論〕注：定理1(3)給出了求最大公因數的方法——輾轉相除法.2023/8/2阜陽師范學院數科院16練習：100個正整2023/9/5阜陽師范學院數科院17二、輾轉相除法定義：設有整數的帶余數除法中，每次用余數去除除數，直到余數為0停止，這種運算方法稱為輾轉相除法。即有(*)或2023/8/2阜陽師范學院數科院17二、輾轉相除法定義2023/9/5阜陽師范學院數科院18定理2

在上面的表達式(*)中，有證明：另一方面，2023/8/2阜陽師范學院數科院18定理2在上面的表2023/9/5阜陽師范學院數科院19證明：先考慮兩個數的情形，一方面，另一方面，由輾轉相除法可以得到，對于多個整數的公因數，利用可以證明.2023/8/2阜陽師范學院數科院19證明：先考慮兩個數2023/9/5阜陽師范學院數科院20例2

求下面各組數的最大公因數。解：18591573115732865143014322860注：亦可通過分解因數的方法求最大公因數.2023/8/2阜陽師范學院數科院20例2求下面各組數2023/9/5阜陽師范學院數科院21補充說明：利用§1.1習題4的結論，可以使得輾轉相除法求最大公因數更為快速一些。每次除得余數的絕對值不超過除數的一半，余數可以為負。例3

求（76501，9719）.765019719877752125181000828941156953285424961440=1.2023/8/2阜陽師范學院數科院21補充說明：利用§12023/9/5阜陽師范學院數科院22定理4說明：（1）在(*)式中，所有各項都乘以m可以得證。（2）由(1)即可得證。2023/8/2阜陽師范學院數科院22定理4說明：（1）2023/9/5阜陽師范學院數科院23定理52023/8/2阜陽師范學院數科院23定理52023/9/5阜陽師范學院數科院24例4

求最大公約數：方法一：利用定理5.方法二：分解因數.48721082243654212182734692023/8/2阜陽師范學院數科院24例4求最大公約數2023/9/5阜陽師范學院數科院25例5利用輾轉相除法計算(27090,21672,11352).270902167211352222704（2）22704438610321111352441280258410320所以，(27090,21672,11352)=258.2023/8/2阜陽師范學院數科院25例5利用輾轉相除2023/9/5阜陽師范學院數科院26例6證明：若n是正整數，則

2023/8/2阜陽師范學院數科院26例6證明：若n2023/9/5阜陽師范學院數科院27定理6設a，b不全為0，則存在整數s,t，使得證明：利用P4習題1-3的結論.一方面，另一方面，2023/8/2阜陽師范學院數科院27定理6設a，b2023/9/5阜陽師范學院數科院28特別地，證：必要性的證明由定理6直接可得。2023/8/2阜陽師范學院數科院28特別地，證：必要性2023/9/5阜陽師范學院數科院29推論1證明：2023/8/2阜陽師范學院數科院29推論1證明：2023/9/5阜陽師范學院數科院30推論2證明：另解：利用推論12023/8/2阜陽師范學院數科院30推論2證明：另解：2023/9/5阜陽師范學院數科院31.思考題：用輾轉相除法求x，y，使得125x

17y

=(125,17).2023/8/2阜陽師范學院數科院31.思考題：用輾轉相2023/9/5阜陽師范學院數科院32習題選講2023/8/2阜陽師范學院數科院32習題選講2023/9/5阜陽師范學院數科院33

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

證：由P3§1習題4知：

2023/8/2阜陽師范學院數科院334、證明：在輾轉2023/9/5阜陽師范學院數科院342023/8/2阜陽師范學院數科院342023/9/5阜陽師范學院數科院35§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|。2023/8/2阜陽師范學院數科院35§1.3最小公2023/9/5阜陽師范學院數科院36定理2

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

ak1=bk2.

2023/8/2阜陽師范學院數科院36定理2對任意2023/9/5阜陽師范學院數科院37推論1兩個整數的任何公倍數一定是最小公倍數的倍數。推論2設m，a，b是正整數，則[ma,mb]=m[a,b]。2023/8/2阜陽師范學院數科院37推論1兩個整2023/9/5阜陽師范學院數科院38定理3注：把多個整數的公倍數化為兩個數的公倍數來計算。推論若m是a1,a2,

,an的公倍數，則[a1,a2,,an]

m

。2023/8/2阜陽師范學院數科院38定理3注：把多個整2023/9/5阜陽師范學院數科院39定理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))代入即得證.2023/8/2阜陽師范學院數科院39定理4整數2023/9/5阜陽師范學院數科院40多項式的帶余式除法稱為n次多項式.注：整數的帶余數除法推廣到多項式的帶余式除法，其他方面的性質〔整除的性質、輾轉相除法、約數、倍數等〕也可以作類似地推廣。2023/8/2阜陽師范學院數科院40多項式的帶余式除法2023/9/5阜陽師范學院數科院41習題講解：2023/8/2阜陽師范學院數科院41習題講解：2023/9/5阜陽師范學院數科院42構造方程其有理根只能為2023/8/2阜陽師范學院數科院42構造方程其有理根2023/9/5阜陽師范學院數科院432023/8/2阜陽師范學院數科院432023/9/5阜陽師范學院數科院44§1.4質數算術基本定理一、質數與合數定義：若整數a

0，1，并且只有約數1和a，則稱a是素數（或質數）；否則稱a為合數。

注：本書中若無特別說明，素數總是指正素數。定理1設a是大于1的整數，則（1）a除1外的最小正因數q是質數；（2）若a是合數，則2023/8/2阜陽師范學院數科院44§1.4質數2023/9/5阜陽師范學院數科院45求質數的方法例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.2023/8/2阜陽師范學院數科院45求質數的方法例12023/9/5阜陽師范學院數科院46分析：利用定理2反證即得.注意：在推論中，若p不是質數，則結論不能成立。2023/8/2阜陽師范學院數科院46分析：利用定理2反2023/9/5阜陽師范學院數科院47二、算術基本定理定理3〔算術基本定理〕任一大于1的整數n能表示成質數的乘積，且其分解的結果是唯一的[不考慮次序].即有：n=p1p2

pm

(1)其中pi（1

i

m）是素數.

證明當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)顯然成立。若k

1是合數，則存在素數p與整數d，使得k

1=pd。2023/8/2阜陽師范學院數科院47二、算術基本定理定2023/9/5阜陽師范學院數科院48推論3.1〔標準分解式〕推論3.2a的正因數可以表示為a的分解式中的部分因數的乘積。推論3.3設a,b是任意兩個正整數，且推論3.3是分解質因數方法求最大公因數和最小公倍數的依據。2023/8/2阜陽師范學院數科院48推論3.1〔標準分2023/9/5阜陽師范學院數科院49定理4質數的個數是無窮的。證：假設質數的個數有限，記為所以存在質數p,

所以，質數的個數是無窮的。2023/8/2阜陽師范學院數科院49定理4質數的個2023/9/5阜陽師范學院數科院50例2寫出51480的標準分解式。解：51480=2

25740=22

12870=23

5

1287=23

5

3

429=23

5

32

143=23

32

5

11

13。=23

64352023/8/2阜陽師范學院數科院50例2寫出5142023/9/5阜陽師范學院數科院51例3證明：(a,b)[a,b]=ab.

其中p1,p2,

,pk是互不相同的素數，

i，

i（1

i

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

2023/8/2阜陽師范學院數科院51例3證明：(a2023/9/5阜陽師范學院數科院522023/8/2阜陽師范學院數科院522023/9/5阜陽師范學院數科院53三、費馬數及其他費馬數尺規(guī)作圖問題：正n邊形可尺規(guī)作圖的充要條件是n的最大單因數是不同的費馬質數的乘積。例如：正3、5、15、17邊形等。

2023/8/2阜陽師范學院數科院53三、費馬數及其他2023/9/5阜陽師范學院數科院54證：（反證法）2023/8/2阜陽師范學院數科院54證：（反證法）2023/9/5阜陽師范學院數科院552023/8/2阜陽師范學院數科院552023/9/5阜陽師范學院數科院56§1.5函數[x]與{x}及其在數論中的應用定義：設x是實數，以[x]表示不超過x的最大整數，稱它為x的整數部分，稱{x}=x

[x]為x的小數部分.一、函數[x]與{x}及其性質2023/8/2阜陽師范學院數科院56§1.5函數[2023/9/5阜陽師范學院數科院57定理1