初等數(shù)論總復(fù)習(xí)題及知識點總結(jié)-2023修改整理

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦初等數(shù)論總復(fù)習(xí)題及知識點總結(jié)初等數(shù)論學(xué)習(xí)總結(jié)

本課程只介紹初等數(shù)論的的基本內(nèi)容。因為初等數(shù)論的基本學(xué)問和技巧與中學(xué)數(shù)學(xué)有著密切的關(guān)系，因此初等數(shù)論對于中學(xué)的數(shù)學(xué)老師和數(shù)學(xué)系(特殊是師范院校)的本科生來說，是一門有著重要意義的課程，在可能狀況下學(xué)習(xí)數(shù)論的一些基礎(chǔ)內(nèi)容是有益的．一方面通過這些內(nèi)容可加深對數(shù)的性質(zhì)的了解，更深化地理解某些他鄰近學(xué)科，另一方面，大概更重要的是可以加強他們的數(shù)學(xué)訓(xùn)練，這些訓(xùn)練在無數(shù)方面都是有益的．正由于如此，許多高等院校，特殊是高等師范院校，都開設(shè)了數(shù)論課程。

最后，給大家提一點數(shù)論的學(xué)習(xí)辦法，即一定不能忽視習(xí)題的作用，通過做習(xí)題來理解數(shù)論的辦法和技巧，華羅庚教授曾經(jīng)說過假如學(xué)習(xí)數(shù)論時只注重到它的內(nèi)容而忽視習(xí)題的作用，則相當(dāng)于只身來到寶庫而空手返回而異。

數(shù)論有豐盛的學(xué)問和悠久的歷史，作為數(shù)論的學(xué)習(xí)者，應(yīng)當(dāng)懂得一點數(shù)論的常識，為此在輔導(dǎo)材料的最后給大家介紹數(shù)論中聞名的“哥德巴赫猜測”和費馬大定理的閱讀材料。

初等數(shù)論自學(xué)支配

第一章：整數(shù)的可除性（6學(xué)時）自學(xué)18學(xué)時

整除的定義、帶余數(shù)除法最大公因數(shù)和輾轉(zhuǎn)相除法整除的進一步性質(zhì)和最小公倍數(shù)素數(shù)、算術(shù)基本定理

[x]和{x}的性質(zhì)及其在數(shù)論中的應(yīng)用

習(xí)題要求3p：2，3；8p：4；12p：1；17p：1，2，5；20p：1。

其次章：不定方程（4學(xué)時）自學(xué)12學(xué)時

二元一次不定方程cbyax=+

多元一次不定方程cxaxaxann=++2211勾股數(shù)費爾馬大定理。

習(xí)題要求29p：1，2，4；31p：2，3。

第三章：同余（4學(xué)時）自學(xué)12學(xué)時

同余的定義、性質(zhì)剩余類和徹低剩余系歐拉函數(shù)、簡化剩余系

歐拉定理、費爾馬小定理及在循環(huán)小數(shù)中的應(yīng)用習(xí)題要求43p：2，6；46p：1；49p：2，3；53p1，2。

第四章：同余式（方程）（4學(xué)時）自學(xué)12學(xué)時

同余方程概念孫子定理

高次同余方程的解數(shù)和解法素數(shù)模的同余方程威爾遜定理。

習(xí)題要求60p：1；64p：1，2；69p：1，2。第五章：二次同余式和平方剩余（4學(xué)時）自學(xué)12學(xué)時

二次同余式

單素數(shù)的平方剩余與平方非剩余勒讓德符號二次互反律雅可比符號、

素數(shù)模同余方程的解法

習(xí)題要求78p：2；81p：1，2，3；85p：1，2；89p：2；93p：1。第一章：原根與指標(biāo)（2學(xué)時）自學(xué)8學(xué)時

指數(shù)的定義及基本性質(zhì)原根存在的條件指標(biāo)及n次乘余模2

及合數(shù)模指標(biāo)組、

特征函數(shù)

習(xí)題要求

p：3。

123

第一章整除

一、主要內(nèi)容

篩法、[x]和{x}的性質(zhì)、n！的標(biāo)準(zhǔn)分解式。

二、基本要求

通過本章的學(xué)習(xí)，能了解引進整除概念的意義，嫻熟把握整除整除的定義以及它的基本性質(zhì)，并能應(yīng)用這些性質(zhì)，了解解決整除問題的若干辦法，嫻熟把握本章中二個聞名的定理：帶余除法定理和算術(shù)基本定理。仔細(xì)體味求二個數(shù)的最大公因數(shù)的求法的理論依據(jù)，把握素數(shù)的定義以及證實素數(shù)有無窮多個的辦法。能嫻熟求出二個整數(shù)的最大公因數(shù)和最小公倍數(shù)，把握高斯函數(shù)[x]的性質(zhì)及其應(yīng)用。

三、重點和難點

（1）素數(shù)以及它有關(guān)的性質(zhì)，判別正整數(shù)a為素數(shù)的辦法，算術(shù)基本定理及其應(yīng)用。

（2）素數(shù)有無窮多個的證實辦法。

（3）整除性問題的若干解決辦法。

（4）[x]的性質(zhì)及其應(yīng)用，n！的標(biāo)準(zhǔn)分解式。

四、自學(xué)指導(dǎo)

整除是初等數(shù)論中最基本的概念之一，b∣a的意思是存在一個整數(shù)q，使得等式a=bq成立。因此這一標(biāo)準(zhǔn)作為我們研究整除性質(zhì)的基礎(chǔ)。也為我們提供了解決整除問題的辦法。即當(dāng)我們無法用整除語言來講述或研究整除問題時，可以將其轉(zhuǎn)化為我們很認(rèn)識的等號問題。

讀者要嫻熟把握并能靈便應(yīng)用。特殊要注重，數(shù)論的討論對象是整數(shù)集合，比學(xué)校數(shù)學(xué)中非負(fù)整數(shù)集合要大。

本章中最重要的定理之一為帶余除法定理，即為

它可以重作是整除的推廣。同時也可以用帶余除法定理來定義整除性，（即當(dāng)余數(shù)r=0

時）

種很重要的思想辦法，它為我們解決整除問題提供了又一條常用的辦法。同時也為我們建立同余理論建立了基礎(chǔ)。讀者應(yīng)熟知常用的分類辦法，例如把整數(shù)可分成奇數(shù)和偶數(shù)，特殊對素數(shù)的分類辦法。例全體奇素數(shù)可以分成4k+1，4k+3；或6k+1，6k+5等類型。

和整除性一樣，二個數(shù)的最大公約數(shù)實質(zhì)上也是用等號來定義的，因此在解決此類問題

題的常用辦法之一。讀者應(yīng)有盡有仔細(xì)體味該定理的證實過程。

既有聯(lián)系，又有區(qū)分。要仔細(xì)體味這些相關(guān)的性質(zhì)，

a1,b1使用相應(yīng)的定理，要注重，相關(guān)定理及推論中互素的條件是常常浮現(xiàn)的。讀者必需注重定理

成立的條件，也可以例舉反例來舉行說明以加深影響。順便指出，若

最小公倍數(shù)實際上與最大公因數(shù)為對偶命題。特殊要指出的是a和b的公倍數(shù)是有無窮多個。所以普通地在無窮多個數(shù)中尋覓一個最小數(shù)是很困難的，為此在定義中全部公倍數(shù)中

的最小的正整數(shù)。即自然數(shù)的任何一個子集一定有一個最小自然數(shù)有在。最小公倍數(shù)的問題普通都可以通過以下式子轉(zhuǎn)化為最大公因數(shù)的問題。兩者的關(guān)系為

上述僅對二個正整數(shù)時成立。當(dāng)個數(shù)大于2時，上述式子不再成立。證實這一式子的關(guān)鍵是尋覓a,b的全部公倍數(shù)的形式，然后從中找一個最小的正整數(shù)。

解決了兩個數(shù)的最小公倍數(shù)與最大公因數(shù)問題后，就可以求出

素數(shù)是數(shù)論討論的核心，許多中外著名的題目都與素數(shù)有關(guān)。除1外任何正整數(shù)不是質(zhì)數(shù)即為合數(shù)。推斷一個已知的正整數(shù)是否為質(zhì)數(shù)可用判別定理去實現(xiàn)。判別定理又是證實素數(shù)無窮的關(guān)鍵。實際上，對于任何正整數(shù)n>1，由判別定理一定知存在素數(shù)p，使得p∣n。即任何大于1的整數(shù)一定存在一個素因數(shù)p。素數(shù)有幾個屬于內(nèi)在本身的性質(zhì)，這些性質(zhì)是

算術(shù)基本定理是整數(shù)理論中最重要的定理之一，即任何整數(shù)一定能分解成一些素數(shù)的乘積，而且分解是唯一的，不是任何數(shù)集都能滿足算術(shù)基本定理的，算術(shù)基本定理為我們提供

了解決其它問題的理論保障。它有許多應(yīng)用，

例如可求最大公約數(shù)，正整數(shù)正約數(shù)的個數(shù)等方面問題，對詳細(xì)的n，真正去分解是件

不簡單的事。對于較特別的n，例如

[x]的性質(zhì)又提供了解決帶有乘除符號的整

除問題的辦法。

本章的許多問題都圍圍著整除而綻開，讀者應(yīng)對整除問題的解決辦法作一容易的小結(jié)。

五、例子選講

補充學(xué)問

①最小自然數(shù)原理：自然數(shù)的隨意非空子集中一定存在最小自然數(shù)。②抽屜原理：

（1）設(shè)n是一個自然數(shù)，有n個盒子，n+1個物體，把n+1個物體放進n個盒子，至少有一個盒子放了兩個或兩個以上物體；

（2）km+1個元素，分成k組，至少有一組元素其個數(shù)大于或等于m+1；（3）無限個元素分成有限組，至少有一組其元素個數(shù)為無限。③梅森數(shù)：形如

④費爾馬數(shù)：n

⑤設(shè)n=kkppα

α(1)

1，設(shè)n的正因子個數(shù)為d(n)，全部正因子之和為)(nσ，則有

⑥有關(guān)技巧

1.整數(shù)表示a=a0×10n+a1×10n-1+…+an，

2.整除的常用辦法

a.用定義

b.對整數(shù)按被n除的余數(shù)分類研究

c.延續(xù)n個整數(shù)的積一定是n的倍數(shù)

d.因式分解

e.用數(shù)學(xué)歸納法

f.要證實a|b，只要證實對隨意素數(shù)p，a中p的冪指數(shù)不超過b中p的冪指數(shù)即可，

用p(a)表示a中p的冪指數(shù)，則例題選講

例1.請寫出10個延續(xù)正整數(shù)都是合數(shù).解:11!+2，11!+3，……，11！+11。

例2.證實延續(xù)三個整數(shù)中，必有一個被3整除。

證：設(shè)三個延續(xù)正數(shù)為a，a+1，a+2，而a惟獨3k，3k+1，3k+2三種狀況，令a=3k，顯

然成立，a=3k+1時，a+2=3(k+1)，a=3k+2時，a+1=3(k+1)。

例3.證實lg2是無理數(shù)。

證：假設(shè)lg2是有理數(shù)，則存在二個正整數(shù)p，q，使得lg2=

q

p

，由對數(shù)定義可得10p=2q，則有2p·5p=2q,則同一個數(shù)左邊含因子5，右邊不含因子5，與算術(shù)基本定理沖突?！鄉(xiāng)g2為無理數(shù)。

例4.求(21n+4，14n+3)

解：原式=(21n+4,14n+3)=(7n+1,14n+3)=(7n+1,7n+2)=(7n+1,1)=1

例5.求2022!末尾零的個數(shù)。解：由于10=2×5，而2比5多，所以只要考慮2022！中5的冪指數(shù)，即

5（2022！）=4995

20225

202212520222520225202254=??

???+??

???+??

???+??

???+??

???

例6.證實（n!）(n-1)!|(n!)!

證：對隨意素數(shù)p,設(shè)（n!）(n-1)!中素數(shù)p的指數(shù)為α，（n!）!中p的指數(shù)β，則

∑??????-=∞=11kkpnn)!(α，∑???

?

??-=∞=11kkpnn!)!(β,)()(xnnx≥α=∑???

?

??-=∑????

??

-≥∑??????-=∑??????∴∞=∞=∞=∞=1111111kkkkkkkkpnnpnnpnnp

n!

)!(!)!()!(!

即α

β≥，即左邊整除右邊。

例7.證實2022|（20222022+20222022-2022）證：∵20222022=（2022-1）2022=2022M1+1

20222022=（2022+1）2022=2022M2+1∴20222022+20222022-2022=2022（M1+M2-1）由定義2022|（20222022+20222022-2022）

例8.設(shè)d(n)為n的正因子的個數(shù)，σ(n)為n的全部正因子之和，求d(1000)，σ(1000)。解：∵1000=23·53

∴d(1000)=(3+1)(3+1)=16，σ(1000)=1

51

5121244--?

--

例9.設(shè)c不能被素數(shù)平方整除，若a2|b2c，則a|b證：由已知p(c)?1，且p(a2)?p(b2c)

∴2p(a)?2p(b)+p(c),∴p(a)?p(b)+2

)

(cp

即p(a)?p(b),∴a|b

例10.若Mn為素數(shù)，則n一定為素數(shù)。證：若n為合數(shù)，則設(shè)n=ab，（1∴2ab-1=(2a)b-1=(2a-1)M為合數(shù)，與Mn為素數(shù)沖突，∴n為素數(shù)。

例11.證實對隨意m,n，m≠n,(Fn,Fm)=1。證：不妨設(shè)n>m，則Fn-2=（121

2

--n）（121

2

+-n）=(Fn-1-2)（121

2

+-n）

=Fn-1Fn-2……Fm-F0

設(shè)（Fn,Fm）=d,則d|Fn,d|Fm?d|2但Fn為奇數(shù)，∴d=1,即證。

例12.設(shè)m,n是正整數(shù)。證實

(,)(21,21)21mnmn--=-

證:不妨設(shè)nm≥。由帶余數(shù)除法得

,11rnqm+=

.nr≤≤10

我們有

121221222121111111-+-=-+-=-+rnqrrrrnqm)(

由此及12121--n

qn|得,),(1212--n

m=),(12121--rn

注重到),(),(1rnnm=,若01=r,則n

nm=),(,結(jié)論成立.若01>r,則繼續(xù)對),(12121--rn作同樣的討

論，由輾轉(zhuǎn)相除法知，結(jié)論成立。顯見，2用任一大于1的自然a代替，結(jié)論都成立。

例13.證實：對隨意的正整數(shù)n，成立如下不等式2lglgkn≥。

其中nlg是數(shù)n的以10為底的對數(shù)，k是n的不同的素因數(shù)（正的）的個數(shù)。

證：設(shè)n是大于1的整數(shù)（假如n=1，上述不等式明顯成立，因k=0），kppp,...,,21是n的k個

相異的素因素。n的素因數(shù)分解式為

klkllpppn(2)

121=.(kili,...,,,211=≥),因為),...,,(,kipi212=≥，從而

kkklllllllkllpppn+++=???≥=212121222221，

而klllk≥+++...21，故kn2≥。

將上述不等式取對數(shù)（設(shè)底1>a）,則有2aaknloglog≥。特殊有2lglgkn≥。

例14.試證實隨意一個整數(shù)與它的數(shù)字和的差必能被9整除，并且它與它的數(shù)字作隨意調(diào)后

換后所成整數(shù)的差也能被9整除。

證：設(shè)整數(shù)m的個位、十位、百位…的數(shù)字分離為1a,2a，…，na，則m可表作：

n

naaaam132********-++++=...

)()...(nnnaaaaaaa

個132321999999-++++++++=)()...(nnnaaaaaaa

個132321111119-++++++++=所以)...(naaaam++++-321)(nnaaa

個132111119-+++=

由于2a，3a,…，na都是整數(shù)，所以任一整數(shù)與其數(shù)字之和的差必能被9整除。再設(shè)將1a,2a，…，na按任一種挨次排成1'a,2'a，…，na'，并令

n

aaa+++=...21σ，naaa'...'''+++=21σ，nnaaam12

11010-+++=...，

n

naaam'...'''1211010-+++=。

按照前面證實的結(jié)果，知存在整數(shù)A，B，使.'',BmAm99=-=-σσ

由于'σσ=，所以)(''BABAmm-=--+=-999σσ

。

因為A-B是整數(shù)，這就證實了'mm-能被9整除。

注：若對某個整數(shù))(nkk≤≤1，有0≠ka'，但當(dāng)nik≤0，y>0，z>0，（x，y）=1，2∣x的條件可以給出x2+y2=z2

的通解公式，x=2ab，y=a2-b2，z2=a2+b2，a>b>0,(a,b)=1，a,b一奇一偶。若將2∣x限為2∣y，則也有相應(yīng)的一個通解公式。在證實這個通解公式的過程中，用到了引理uv=w2，u>0，v>0，（u,v）=1，則u=a2，v=b2，w=ab。a>0，b>0，（a,b）=1。利用這個結(jié)論可以求解某些不定方程。特殊當(dāng)w=1或素數(shù)p。則由uv=1或uv=P可將原不定方程轉(zhuǎn)化為不定方程組。

從而獲得一些不定方程的解。希翼讀者能把握這種辦法。

為了解決聞名的費爾馬大定理：xn+yn=zn，n?3無正整數(shù)解時，當(dāng)n=4時可以用較初等的辦法給出證實。證實由費爾馬本人給出的，普通稱為費爾馬無窮遞降法。其基本思想為由一組解動身通過構(gòu)造得出另一組解，使得兩組解之間有某種特定的關(guān)系，而且這種構(gòu)造可以無限重復(fù)的。從而可得到?jīng)_突。因此無窮遞降法常用來證實某些不定方程無整數(shù)解。

證實一類不定方程無解是討論不定方程鄰域中常見的形式，普通的要求解不定方程比證實不定方程無解要簡單些。證實不定方程無解的證實辦法常采納以下形式：（反證法）

若A有解?A1有解?A2有解?……?An有解，而An本身無解，這樣來構(gòu)造沖突。從而說明原不定方程無解。

對于證實不定方程的無解性通常在幾種辦法，普通是總的幾種辦法交替使用。特殊要求把握：容易同余法、因子分解法、不等式法，以及中學(xué)數(shù)學(xué)中所涉及的判別式法。

五、例子選講

例1：利用整數(shù)分別系數(shù)法求得不定方程15x+10y+6z=61。解：注重到z的系數(shù)最小，把原方程化為

z=)()(1236

110226110156

1++-++--=+--yxyxyx

令t1=zyx∈++-)(1236

1，即-3x+2y-6t1+1=0

此時y系數(shù)最小，)()(12

131632

111-++=-++=∴xtxtxy

令t2=z

x

∈-)(12

1,即122+=tx,反推依次可解得

y=x+3t1+t2=2t2+1+3t1+t2=1+3t1+3t2z=-2x-2y+10+t1=6-5t1+10t2

∴原不定方程解為??

???--=++=+=21212

105633121t

tzttytxt1t2∈z.

例2:證實2是無理數(shù)

證：假設(shè)

2

是有理數(shù)，則存在自數(shù)數(shù)a,b使得滿足22

2yx=即22

2ba

=，簡單知道a是偶數(shù)，

設(shè)a=2a1，代入得2

1

22ab=,又得到b為偶數(shù)，abab>a1>b1>a2>b2>…但是自然數(shù)無窮遞降是不行能的，于是產(chǎn)生了沖突，∴2

為無理數(shù)。

例3：證實：整數(shù)勾股形的勾股中至少一個是3的倍數(shù)。

證：設(shè)N=3m±1(m為整數(shù))，∴N2=9m2±6m+1=3(3m2±2m)+1

即一個整數(shù)若不是3的倍數(shù)，則其平方為3k+1,或者說3k+2不行能是平方數(shù)，設(shè)x,y為勾股整數(shù)，且x,y都不是3的倍數(shù)，則x2,y2都是3k+1，但z2=x2+y2=3k+2形，這是不行能，∴勾股數(shù)中至少有一個是3的倍數(shù)。

例4：求x2+y2=328的正整數(shù)解

解：∵328為偶數(shù)，∴x,y奇偶性相同，即x±y為偶數(shù)，設(shè)x+y=2u,x-y=2v，代入原方程即為

u2+v2=164,同理令u+v=2u1,u-v=2v1有

2

1121121212282vvuuvuvu=-=+=+,,,412222=+vu22vu,為一偶一奇，且

0cd,.

按照(1)，僅當(dāng)v=8時滿足此要求，從而.

d

=c

25=

,51

因此該支票原為25元51分.

第三章同余

一、主要內(nèi)容

同余的定義、性質(zhì)、剩余類和徹低剩余系、歐拉函數(shù)、簡化剩余系、歐拉定理、費爾馬小定理、循環(huán)小數(shù)、特別數(shù)2，3，4，5，6，7，8，9，11，13的整除邏輯

二、基本要求

通過本章的學(xué)習(xí)，能夠把握同余的定義和性質(zhì)，區(qū)分符號：“三”和=”之間的差異。能利用同余的一些基本性質(zhì)舉行一些計算，深刻理解徹低剩余系，簡化剩余系的定義、性質(zhì)及構(gòu)造。能推斷一組數(shù)是否構(gòu)成模m的一個徹低剩余系或一個簡化剩余系。能計算歐拉函數(shù)的值，把握歐拉定理、費爾馬小定理的內(nèi)容以及證實辦法。能應(yīng)用這二個定理證實有關(guān)的整除問題和求余數(shù)問題。能舉行循環(huán)小數(shù)與分?jǐn)?shù)的互化。

三、難點和重點

（1）同余的概念及基本性質(zhì)

（2）徹低剩余系和簡化剩余系的構(gòu)造、判別

（3）歐拉函數(shù)計算、歐拉定理、費爾馬小定理的證實及應(yīng)用

（4）循環(huán)小數(shù)與分?jǐn)?shù)的互化

（5）特別數(shù)的整除邏輯。

四、自學(xué)指導(dǎo)

同余理論是初等數(shù)論中最核心的內(nèi)容之一，由同余定義可知，若a≡b(modm)，則a和

b被m除后有相同的余數(shù)。這里m為正整數(shù)，普通要求m大于1

第一章中用帶余除法定理將整數(shù)分類解決一些問題的辦法只不過是同余理論中的一個特別

。值得注重a和b關(guān)于m同余是個相對概念。即它是相對于模m來講，二個整數(shù)a和b關(guān)于一個整數(shù)模m同余。則對于另一個整數(shù)模m

，a和b未必會同余。

1

從定義上看，同余和整除是同一個事情，但引進了新的符號“三”后，無論從問題的講述上，還是解決問題的辦法上都有了顯著的變化，同時也帶來了一些新的學(xué)問和辦法。在引進了同余的代數(shù)性質(zhì)和自身性質(zhì)后，同余符號“三”和等號“=”相比，在形式上有幾乎全都的性質(zhì)，這便于我們記憶。事實上在全部等號成立的運算中，惟獨除法運算是個例外，即除法的消去律不成立。為此對于同余的除法運算我們有二種除法：

這一點讀者要特殊注重。

徹低剩余系和簡化剩余系是二個全新的概念，讀者只要搞清引成這些概念的過程。由于同余關(guān)系是一個等價關(guān)系，利用等價關(guān)系可以舉行將全體整數(shù)舉行分類，弄清來朧去脈，對于更深刻理解其本質(zhì)是很有益處的。徹低剩余系或簡化剩余系是一個以整數(shù)為元素的集合，在每個剩余類各取一個數(shù)組成的m個不同數(shù)的集合，故一組徹低剩余系包含m個整數(shù)，因為二個不同的剩余類中的數(shù)關(guān)于m兩兩不同余，故可得判別一組數(shù)是否為模m的一個徹低剩余系的條件有二條為

另外要能用已知徹低剩余系構(gòu)造新的徹低剩余系。即有定理

為研究簡化剩余系，需要引進歐拉函數(shù)φ(m)，歐拉函數(shù)φ(m)定義為不超過m且與m互素的正整數(shù)的個數(shù)，記為φ(m)，要把握φ(m)的計算公式，了解它的性質(zhì)。這些性質(zhì)最主要

現(xiàn)在在剩余類中把與m互素的集合分出來，從中可在各個集合中任取一個數(shù)即可構(gòu)造模m的一個簡化剩余系。另一方面，簡化剩余數(shù)也可從模m的一個徹低剩余系中得到簡化剩余系，一組徹低剩余系中與m互素的的數(shù)組成的φ(m)個不同數(shù)的集合稱為m簡化剩余系。同樣簡化剩余系也有一個判別條件。

判別一組整數(shù)是否為模m的簡化剩余系的條件為關(guān)于m的簡化剩余系也能用已知徹低剩余系構(gòu)造新的簡化剩余系。設(shè)（a，m）=1，x為m的簡化剩余系，則ax也是m的簡化剩余系。

當(dāng)1),(21=mm時，能由1m的簡化剩余系和2m的簡化剩余系，構(gòu)造21mm簡化剩余系。

歐拉定理、費爾馬小定理是同余理論十分重要的定理之一。要注重歐拉定理和費爾馬定理的條件和結(jié)論。

決整除問題的辦法之一。

另外同余辦法在證實不定方程時也十分實用，即要把握同余“三”和相等“=”的關(guān)系：相等必同余，同余未必相等，不同余絕對不相等。

對于特別數(shù)的整除邏輯要求能把握其普通定理的證實，并熟記一些特別數(shù)的整除邏輯

五、例子選講

例1：求3406的末二位數(shù)。

解：∵（3，100）=1，∴3)100(φ≡1（mod100）

φ(100)=φ(22·52)=40,∴340≡1(mol100)

∴3406=(340)10·36≡(32)2·32≡-19×9≡-171≡29(mod100)∴末二位數(shù)為29。

例2：證實（a+b）p≡ap+bp(modp)

證：由費爾馬小定理知對一切整數(shù)有：ap≡a（p），bp≡b(P)，

由同余性質(zhì)知有：ap+bp≡a+b(p)

又由費爾馬小定理有（a+b）p≡a+b(p)（a+b）p≡ap+bp(p)

例3：設(shè)素數(shù)p>2，則2P-1的質(zhì)因數(shù)一定是2pk+1形。證：設(shè)q是2p-1的質(zhì)因數(shù)，因為2p-1為奇數(shù)，∴q≠2，

∴（2·q）=1,由條件q|2p-1,即2p≡1（modq），又∵（q,2）=1，2p≡1（modq）設(shè)i是使得2x≡1（modp）成立最小正整數(shù)

若13，p只能為p≡±1(mod3)且???-≡??

???1

1

3p

)

4(mod1)

4(mod1-≡≡pp

∴

13=???

?

??p只能下列狀況?

?

?≡≡)(mod)

(mod4131pp???-≡-≡)4

(mod1)3

(mod1pp

∴)(mod121≡p或)(mod121-≡p

例3：證實形如4m+1的素數(shù)有無窮多個。

證：假設(shè)形如4m+1的素數(shù)惟獨有限個，設(shè)為p1…pk，

明顯(2p1…pk)2+1的最小素因數(shù)p是奇數(shù)，且p與p1…pk不同，

設(shè)p為4m+3形的素數(shù)，但p整除(2p1…pk)2+1，表明(2p1…pk)2+1≡0（modp）即x

2

≡(-1)(modp)有解，即11=????

??-p，但1)1()

1(1122

1

-=-≡-≡???

???-+-mpp沖突，

∴p為4m+1形，這與4m+1的素數(shù)惟獨k個沖突。

例4：證實不定方程x2+23y=17無解。證：只要證x2≡17(mod23)無解即可，

∵17≡1(mod4)∴

13231717317317217617232317-=??

?

??=?????=?????=??????????=?????=?????=?????∴x2≡17(mod23)無解，即原方程無解。

例5設(shè)x為整數(shù)，證實形如12+x的整數(shù)的全部奇因數(shù)都有

4h+1的形式，（其中h為整數(shù)）

證：設(shè)2n+1是整數(shù)12

+x的任一奇素因數(shù)，于是有

),(mod12022+≡+nx即).(mod1212+-≡nx

可以證實，這時)(mod1202+≡nx，否則有)(mod1201+≡n，這是不行能的。

因此，由12+n是奇素數(shù)，便有1)12,(2=+nx。

從而112=+),(nx，這樣由費馬定理，有)(mod1212+≡nxn。

但是),(mod)()(12122+-≡=nxxnnn

因此有).(mod)(1211+≡-nn

由此可知，n必為偶數(shù)，記n=2h,便有2n+1=4h+1.這樣便證實了整數(shù)12

+x的的全部奇

素因數(shù)形式必為4h+1形式。又因為兩個4h+1形式的數(shù)的乘積仍為4h+1形式的數(shù)，故1

2+x形式的數(shù)的奇因數(shù)必為4h+1形式的數(shù)。證2：由上面可知，-1是模2n+1的平方剩余，即.1121=??

?

??+-n

其中2n+1是奇素數(shù)。由定理3知)(mod4112≡+n

從而)4(mod02≡n，故)(mod20≡n，所以n是偶數(shù)，其余同上。

例6：證實：形如)8(mod1≡p的素數(shù)有無窮多個。

證：設(shè)N是隨意正整數(shù)，sppp,...,,21是不超過N的一切形如)(mod81≡p的素數(shù)。記

12421+=)...(spppq。

明顯q的隨意素因數(shù)a異于2，且spppx...212=是同余式)

(modax014≡+的解。

由)(mod81≡a.又因為是),...,,(sipi21=不是q的因數(shù)，

故),...,,(sipai21=≠，從而Na>。因此形如)(mod81≡p的素數(shù)有無窮多個。

例7:解如下二次同余式)(mod125112≡x

解：(1)125=53。先解)(mod51112

≡≡x。它的一個解是x=1。

再解)(mod22

511≡x。令yx51+=，

則有)(mod)(22

51151≡+y.化簡得)(mod)(2511101≡+y，

得到)(mod51≡y,從而有)(mod2555≡y，)(mod25651≡+y，所以)(mod22511≡x的一個解為6=x,最后解)(mod32511≡x。

設(shè)z

x

256+=。代入有)(mod)(32251156≡+z，

化簡得).(mod32525512-≡?z即).(mod5112-≡z

它的一個解是2=z.因此562256=?+=x是同余式125112(mod)≡x的一個解，

所以由定理，125112(mod)≡x的兩個解是12556(mod)≡x，.(mod)12556-≡x

例8：推斷同余方程)(mod4432862

≡x是否有解。

解：286=2×143，433是素數(shù)，(143，443)=1

奇數(shù)143不是素數(shù)，但可用判定可比符號計算的生勒讓德符號

??

?

???????=?????=?????-?-=???

???????=?????-?--1437143214314143443)

1()1(44314324324432862

1

443211432

14432??

?

??-?-=-?--7143)

1()

1(2

1

1432178

1

14313173=??

???=?????-=∴原方程有解。

第六章原根與指標(biāo)

一、主要內(nèi)容

原根、指數(shù)的定義及基本性質(zhì)、原根存在的條件、指標(biāo)及n次乘余、模2α及合數(shù)模指標(biāo)組、特征函數(shù)

二、基本要求

理解原根，指數(shù)的定義，把握指數(shù)的性質(zhì)，原根存在的條件以及在一定條件下求已知模的原根。能推斷怎樣的數(shù)為模m的原根，用指數(shù)以及指標(biāo)組能構(gòu)造模m的簡化乘余系。

三、重點和難點：

本章內(nèi)容都比較抽象，具有一定的理論性。原根與指標(biāo)是重點。

四、自學(xué)指導(dǎo)：

上章介紹了x2≡a(modm)的解數(shù)。本章主要以解決x2≡a(modm)的解而引進原根，指數(shù)等概念。

，上述條件是以(a,m)=1為先決

條件。設(shè)

要弄清p和pα的原根之間的關(guān)系，及pα與2pα的原根之間的關(guān)系。弄清當(dāng)m在原根存在時，m的全部原根表達(dá)方式s={gn1?n?φ(m)，(n,φ(m))=1}

指標(biāo)是原根這一種另一個重要的概念，它有類似于對數(shù)函數(shù)的性質(zhì)，另用指標(biāo)可構(gòu)造適當(dāng)模m的簡化剩余系。

五、例子選講

例1：試10是模17的原根。

證：因φ(17)=16，其正因子為d=2,4,8,且10d1(mod17),

∴10為模17的原根。

例2：解同余方程x12≡2(mod31)

解：d=(12,30)=6,查表ind2=24,

6|24，解且本題有6個解，

x12≡2(mod31)?12indx=ind2(30)

即indx≡4(mod5)

∴indx≡2,7,12,17,22,27(mod30)

查模31指標(biāo)表，

∴x≡9,17,8,22,14,23(mod31)

例3:(1)若p和q=4p+1均為素數(shù)，則2是模q的一個原根。

(2)若p和q=6p+1均為奇素數(shù)，則3是模q的一個原根。證：(1)因為p和q=4p+1均為素數(shù)，故p≠2，從而(2,q)=1。

按照費馬定理有

)(modqqp12241≡=-

因此要證實2是模q的一原根，只需證實

)(modqpq12222

1-≡=-

即可。按照本章定理2，有

)(modqqqp

???

???≡=

-222

2

12而q是奇素數(shù)，必有)(mod,,,87531≡p之一，但不管那一種，均有)(mod844≡p，因此)(mod8514≡+=pq

所以由定理，2是模q的非平方剩余，即12-=???

?

??q。

從而有)(modqp122-≡。

故2關(guān)于模q的階為4p=q-1，所以2是模q的一個原根。(2)因為p和q=6p+1均為奇素數(shù)，故3q，從而(3,q)=1，

故由費馬定理有

)(mod13361qpq≡=-

為了證實3是模q的一個原根，只需證實

)(mod13

3

2

1

3qqp

-≡=-即可

由定理有

)(mod33

32

13qqqp???

???≡=-因為p是奇素數(shù)，故)(mod,,,,12117531≡p之一，不管那一種狀況，均有)(mod1266≡p，所以

)(mod12716≡+=pq。

所以3是模q的非平方剩余，即13-=???

?

??q，

所以)(mod133qp-≡

故3關(guān)于模q的階為6p=q-1，所以3是模q的一個原根。

《初等數(shù)論》模擬試卷（A）

說明：考生應(yīng)有將所有答案寫在答題紙上，否則作無效處理

一、填空（36分）

1、d（1000）=。σ（1000）=。φ（1000）=。

2、n1?，若)(mod01)!1(nn≡+-則n為。

3、不能表示成5X+3Y（X、Y非負(fù)）的最大整數(shù)為。

4、7在2022！中的最高冪指數(shù)是。

5、（1515，600）=。

6、)(modmbax≡有解的充要條件是。

7、威爾遜定理是。

8、寫出6的一個簡化系，要求每項都是5的倍數(shù)。

9、2

3.0化為分?jǐn)?shù)是。10、20222的末位數(shù)是。11、[-2.3]=。

12、φ（1）＋φ（P）＋…φ（nP）=。

13、1>x且能被4、5、7整除，則最小的x是。14、

50

50

6666688888?被7除后的余數(shù)為。15、兩個素數(shù)的和為31，則這兩個素數(shù)是。16、帶余除法定理是。

二、解同余方程組（12分）

??

?

??≡≡≡)7(mod1)8(mod3)5(mod2xxx

三、講述并且證實費爾馬小定理。（12分）

四、假如整系數(shù)的二次三項式1,0)(2=++=xcbxxxp當(dāng)時的值都是奇數(shù)，證實

0)(=xp沒有整數(shù)根（6分）

五、設(shè)Ｐ為奇素數(shù)，則有（8分）（1）)(mod1)1(21111ppppp-≡-+++（2）)(mod0)1(21ppppp≡-+++六、證實：對任何正整數(shù)ｋ，ｍ，ｎ

有１１|354525345+++++nmk（6分）

七、證實：3是無理數(shù)。（8分）

八、試證：對任何的正整數(shù)2,2+nn不能被4整除。（6分）九、解不定方程1054=+yx（6分）

《初等數(shù)論》模擬試卷（A）答案一、

1、16，2340，9360

2、素數(shù)

3、7

4、331

5、15

6、b|),(ma

7、)(mod01)!1(pp≡+-8、5，25

9、

90

2910、811、-3

12、np13、14014、515、2，2916、

查書

二、孫子定理)280(mod267≡x三、見書

四、證：由條件可得c為奇數(shù)，b為偶數(shù)

假如p（x）=0有根q，若q為偶數(shù)，則有cbqq++2為奇數(shù)，而p（q）=0為偶數(shù)，不行能，若q為奇數(shù)，則有cbqq++2為奇數(shù)，而p（q）=0為偶數(shù)，也不行能，所以0)(=xp沒有整數(shù)根五、證：由歐拉定理

)(mod11111)1(21111pppppp-≡-≡++≡-+++由費爾馬定理

)(mod0121)1(21111pppppp≡-++≡-+++六、（5，11）=1，（4，11）=1，（3，11）=1由歐拉定理得

)11(mod1510≡，)11(mod1310≡，)11(mod1410≡，進一步有)11(mod155≡，)11(mod135≡，)11(mod145≡對任何正整數(shù)ｋ，ｍ，ｎ有

)11(mod034534