讓時間在知識的枝條上、智慧的綠葉上、成熟的果實上留下它勤奮的印痕！以下是為大家整理的《2018年自考公共課數論初步章節(jié)講義》供您查閱。
【同余】
一、 主要內容
同余的定義、性質、剩余類和完全剩余系、歐拉函數、簡化剩余系、歐拉定理、費爾馬小定理、循環(huán)小數、特殊數2，3，4，5，6，7，8，9，11，13的整除規(guī)律
二、 基本要求
通過本章的學習，能夠掌握同余的定義和性質，區(qū)別符號：“三”和=”之間的差異。能利用同余的一些基本性質進行一些計算，深刻理解完全剩余系，簡化剩余系的定義、性質及構造。能判斷一組數是否構成模m的一個完全剩余系或一個簡化剩余系。能計算歐拉函數的值，掌握歐拉定理、費爾馬小定理的內容以及證明方法。能應用這二個定理證明有關的整除問題和求余數問題。能進行循環(huán)小數與分數的互化。
三、難點和重點
(1)同余的概念及基本性質
(2)完全剩余系和簡化剩余系的構造、判別
(3)歐拉函數計算、歐拉定理、費爾馬小定理的證明及應用
(4)循環(huán)小數與分數的互化
(5)特殊數的整除規(guī)律。
四、自學指導
同余理論是初等數論中核心的內容之一，由同余定義可知，若a≡b(mod m)，則a和b被m除后有相同的余數。這里m為正整數，一般要求m大于1，稱為模，同余這一思想本質上是將整數按模m分類，然后討論每一個類中整數所具有的共性及不同類之間的差異。第一章中用帶余除法定理將整數分類解決一些問題的方法只不過是同余理論中的一個特殊例子。從同余的定理上看，同余和整除實際上是同一回事，故同余還有二個等價的定義：①用整除來定義即 m∣a-b 。②用等號來定義a=b+mt 。值得注意a和b關于m同余是個相對概念。即它是相對于模m來講，二個整數a和b關于一個整數模m同余。則對于另一個整數模m
，a和b未必會同余。
從定義上看，同余和整除是同一個事情，但引進了新的符號“三”后，無論從問題的敘述上，還是解決問題的方法上都有了顯著的變化，同時也帶來了一些新的知識和方法。在引進了同余的代數性質和自身性質后，同余符號“三”和等號“=”相比，在形式上有幾乎一致的性質，這便于我們記憶。事實上在所有等號成立的運算中，只有除法運算是個例外，即除法的消去律不成立。為此對于同余的除法運算我們有二種除法：
(i)模不改變的除法，若ak≡bk(mod m) ，(k,m)=1，則a≡b(mod m)
(ii)模改變的除法, 若ak≡bk(mod m) (k,m)=d,則a≡b
這一點讀者要特別注意。
完全剩余系和簡化剩余系是二個全新的概念，讀者只要搞清引成這些概念的過程。因為同余關系是一個等價關系，利用等價關系可以進行將全體整數進行分類，弄清來朧去脈，對于更深刻理解其本質是很有好處的。完全剩余系或簡化剩余系是一個以整數為元素的集合，在每個剩余類各取一個數組成的m個不同數的集合，故一組完全剩余系包含m個整數，由于二個不同的剩余類中的數關于m兩兩不同余，故可得判別一組數是否為模m的一個完全剩余系的條件有二條為
(1) 個數=m
(2) 關于m兩兩不同余
另外要能用已知完全剩余系構造新的完全剩余系。即有定理
設(a，m)=1，x為m的完全剩余系，則ax+b也是m的完全剩余系。
當
時，能由
的完全剩余系和
的完全剩余系，構造
完全剩余系。為討論簡化剩余系，需要引進歐拉函數φ(m)，歐拉函數φ(m)定義為不超過m且與m互素的正整數的個數，記為φ(m)，要掌握φ(m)的計算公式，了解它的性質。這些性質主要的是當(a ,b)=1時，φ(ab) = φ(a) φ(b)，和
現在在剩余類中把與m互素的集合分出來，從中可在各個集合中任取一個數即可構造模m的一個簡化剩余系。另一方面，簡化剩余數也可從模m的一個完全剩余系中得到簡化剩余系，一組完全剩余系中與m互素的的數組成的φ(m)個不同數的集合稱為m簡化剩余系。同樣簡化剩余系也有一個判別條件。
判別一組整數是否為模m的簡化剩余系的條件為
(1) 個數=φ(m)
(2) 關于m兩兩不同余
(3) 每個數與m互素
關于m的簡化剩余系也能用已知完全剩余系構造新的簡化剩余系。
設(a，m)=1，x為m的簡化剩余系，則ax也是m的簡化剩余系。
當
時，能由
的簡化剩余系和
的簡化剩余系，構造
簡化剩余系。
歐拉定理、費爾馬小定理是同余理論非常重要的定理之一。要注意歐拉定理和費爾馬定理的條件和結論。
歐拉定理：設m為大于1的整數，(a，m)=1，則有
費爾馬小定理：若p是素數，則有
除此以外，歐拉定理的證明的思想是非常好的，在各個地方都有應用。就歐拉定理、費爾馬小定理來講，它在某些形如a
數的整除問題應用起來顯得非常方便。同余方法也是解決整除問題的方法之一。
另外同余方法在證明不定方程時也非常有用，即要掌握同余“三”和相等“=”的關系：相等必同余，同余未必相等，不同余肯定不相等。
對于特殊數的整除規(guī)律要求能掌握其一般定理的證明，并熟記一些特殊數的整除規(guī)律
1、 一個整數被2整除的充要條件是它的末位為偶數。
2、 一個整數被3整除的充要條件是它的各位數字之和能被3整除。
3、 一個整數被9整除的充要條件是它的各位數字之和能被9整除。
4、 一個整數被5整除的充要條件是它的末位為0或5。
5、 一個整數被4，25整除的充要條件是它的末二位能被4，25整除。
6、 一個整數被8，125整除的充要條件是它的末三位能被8，125整除。
7、 設
，則7或11或13整除a的充要條件是7或11或13整除
五、例子選講
例1：求3406的末二位數。
解：∵ (3，100)=1，∴3
≡1(mod 100)
(100)=
(22·52)=40, ∴ 340≡1(mol 100)
∴ 3406=(340)10·36≡(32)2·32≡-19×9≡-171≡29(mod 100)
∴ 末二位數為29。
例2：證明(a+b)p≡ap+bp(mod p)
證：由費爾馬小定理知對一切整數有：ap≡a(p)，bp≡b(P)，
由同余性質知有：ap+bp≡a+b(p)
又由費爾馬小定理有(a+b)p≡a+b (p)
(a+b)p≡ap+bp(p)
【不定方程】
一、 主要內容
不定方程有解的條件、解數、解法、通解表示，不定方程x2+y2=z2通解公式、無窮遞降法、費爾馬大定理。
二、 基本要求
1、 了解不定方程的概念，理解對“解”的認識，掌握不定方程
有解的條件，能熟練求解不定方程的特解，正整數解及通解。了解多元不定方程
有解的條件，在有解的條件下的解法。
2、掌握不定方程x2+y2=z2在一定條件下的通解公式，并運用這個通解公式作簡單的應用。
3、對費爾馬大定理應有在常識性的了解，掌握無窮遞降法求證不定方程x4+y4=z2無解的方法。
4、掌握證明不定方程無解的若干方法。
三、難點和重點
(1)重點為求解不定方程的方法
(2)掌握第二節(jié)中引證的應用。
(1) 費爾馬無窮遞降法。
四、自學指導
不定方程主要講解以下幾個問題
(i)給定一類不定方程，判別在什么條件下有解。
(ii)在有解的條件下，有多少解
(iii)在有解的條件下，求出所給的不定方程的所有解。
二元不定方程的一般形式為ax+by=c 。若(a ,b)∣c，則該二元不定方程一定有解，若已知一個特解，則一切解可以用公式表示出來，因此求它的通解只要求出一個特解即可。求解二元不定方程的一個通解有好多種方法。讀者應該總結一下，各種方法都有獨到之處。特別要指出用大公因數的方法。它的根據是求(a ,b)時所得的結果。由于注意通解公式x=x0-b1t，y=y0+a1t中a1，b1的意義和位置。以免出錯。
多元不定方程
也有類似的結果，但在求解的過程中將它轉化二元不定方程組，從后一個二元不定方程解起，可逐一解出x1 ,x2 ,……xn 。所用的方法一般選擇大公因數的方法。由于n元不定方程可轉化為n-1個二元不定方程組，故在通解中依賴于n-1個任意常數。但不象二元不定方程那樣有公式來表示。
x2+y2=z2的正整數解稱為勾股數，在考慮這個方程時，我們對(x ,y)作了一些限制，而這些限制并不影響其一般性。在條件x>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，則也有相應的一個通解公式。在證明這個通解公式的過程中，用到了引理 uv=w2，u>0，v>0，(u ,v)=1，則u=a2，v=b2，w=ab 。a>0，b>0，(a ,b)=1 。利用這個結論可以求解某些不定方程。特別當w=1或素數p 。則由uv=1或uv=P 可將原不定方程轉化為不定方程組。從而獲得一些不定方程的解。上述解不定方程的方法叫因子分解法。希望讀者能掌握這種方法。
為了解決的費爾馬大定理：xn+yn=zn ，n≥3無正整數解時，當n=4時可以用較初等的方法給出證明。證明由費爾馬本人給出的，一般稱為費爾馬無窮遞降法。其基本思想為由一組解出發(fā)通過構造得出另一組解，使得兩組解之間有某種特定的關系，而且這種構造可以無限重復的。從而可得到矛盾。因此無窮遞降法常用來證明某些不定方程無整數解。
證明一類不定方程無解是研究不定方程鄰域中常見的形式，一般的要求解不定方程比證明不定方程無解要容易些。證明不定方程無解的證明方法常采用以下形式：(反證法)
若A有解
A1有解
A2有解
……
An有解，而An本身無解，這樣來構造矛盾。從而說明原不定方程無解。
對于證明不定方程的無解性通常在幾種方法，一般是總的幾種方法交替使用。特別要求掌握：簡單同余法、因子分解法、不等式法，以及中學數學中所涉及的判別式法。
五、例子選講
例1：利用整數分離系數法求得不定方程15x+10y+6z=61。
解：注意到z的系數小，把原方程化為
z=
令t1=
，即-3x+2y-6t1+1=0 此時y系數小，
令t2 =
,即
,反推依次可解得
y=x+3t1+t2=2t2+1+3t1+t2=1+3t1+3t2
z=-2x-2y+10+t1=6-5t1+10t2
∴原不定方程解為
t1t2∈z. 例2:證明
是無理數證：假設
是有理數，則存在自數數a,b使得滿足
即
，容易知道a是偶數，設a=2a1，代入得
，又得到b為偶數，
，設
，則
,這里
這樣可以進一步求得a2，b2…且有a>b>a1>b1> a2>b2>…
但是自然數無窮遞降是不可能的，于是產生了矛盾，∴
為無理數。
例3：證明：整數勾股形的勾股中至少一個是3的倍數。
證：設N=3m±1(m為整數) ， ∴N2=9m2±6m+1=3(3m2±2m)+1
即一個整數若不是3的倍數，則其平方為3k+1,或者說3k+2不可能是平方數，設x,y為勾股整數，且x,y都不是3的倍數，則x2,y2都是3k+1，但z2=x2+y2=3k+2形，這是不可能，∴勾股數中至少有一個是3的倍數。
【整除】
一、主要內容
整除的定義、帶余除法定理、余數、大公因數、小公倍數、輾轉相除法、互素、兩兩互素、素數、合數、算術基本定理、Eratosthesen篩法、[x]和{x}的性質、n!的標準分解式。
二、基本要求
通過本章的學習，能了解引進整除概念的意義，熟練掌握整除 整除的定義以及它的基本性質，并能應用這些性質，了解解決整除問題的若干方法，熟練掌握本章中二個的定理：帶余除法定理和算術基本定理。認真體會求二個數的大公因數的求法的理論依據，掌握素數的定義以及證明素數有無窮多個的方法。能熟練求出二個整數的大公因數和小公倍數，掌握高斯函數[x]的性質及其應用。
三、重點和難點
(1)素數以及它有關的性質，判別正整數a為素數的方法，算術基本定理及其應用。
(2)素數有無窮多個的證明方法。
(3)整除性問題的若干解決方法。
(4)[x]的性質及其應用，n!的標準分解式。
四、自學指導
整除是初等數論中基本的概念之一，b∣a的意思是存在一個整數q，使得等式a=bq成立。因此這一標準作為我們討論整除性質的基礎。也為我們提供了解決整除問題的方法。即當我們無法用整除語言來敘述或討論整除問題時，可以將其轉化為我們很熟悉的等號問題。
對于整除的若干性質，主要的性質為傳遞性和線性組合性，即
(1) a∣b, b∣c, 則有a∣c
(2) a∣b, a∣c, 則有a∣mb+nc
讀者要熟練掌握并能靈活應用。特別要注意，數論的研究對象是整數集合，比小學數學中非負整數集合要大。
本章中重要的定理之一為帶余除法定理，即為
設a是整數，b是非零整數，則存在兩個整數q，r，使得
a=bq+r (0)
它可以重作是整除的推廣。同時也可以用帶余除法定理來定義整除性，(即當余數r=0時)。帶余除法可以將全體整數進行分類，從而可將無限的問題轉化為有限的問題。這是一種很重要的思想方法，它為我們解決整除問題提供了又一條常用的方法。同時也為我們建立同余理論建立了基礎。讀者應熟知常用的分類方法，例如把整數可分成奇數和偶數，特別對素數的分類方法。例全體奇素數可以分成4k+1，4k+3;或6k+1，6k+5等類型。
和整除性一樣，二個數的大公約數實質上也是用等號來定義的，因此在解決此類問題時若有必要可化為等式問題，大公因數的性質中重要的性質之一為 a=bq+c，則一定有(a，b)=(b，c)，就是求二個整數的大公約數的理論根據。也是解決關于大公約數問題的常用方法之一。讀者應有盡有認真體會該定理的證明過程。
互素與兩兩互素是二個不同的概念，既有聯系，又有區(qū)別。要認真體會這些相關的性質，例如，對于任意a ,b∈Z，可設(a ,b)=d，則a=da1 ,b=db1，則(a1 ,b1)=1，于是可對a1 ,b1使用相應的定理，要注意，相關定理及推論中互素的條件是經常出現的。讀者必須注意定理成立的條件，也可以例舉反例來進行說明以加深影響。順便指出，若a∣c，b∣c，(a ,b)=1，則ab∣c是我們解決當除數為合數時的一種方法。好處是不言而喻的。
小公倍數實際上與大公因數為對偶命題。特別要指出的是a和b的公倍數是有無窮多個。所以一般地在無窮多個數中尋找一個小數是很困難的，為此在定義中所有公倍數中的小的正整數。這一點實際上是應用自然數的小自然數原理，即自然數的任何一個子集一定有一個小自然數有在。小公倍數的問題一般都可以通過以下式子轉化為大公因數的問題。兩者的關系為
a ,b∈N， [a ,b]=ab/(a,b)
上述僅對二個正整數時成立。當個數大于2時，上述式子不再成立。證明這一式子的關鍵是尋找a , b的所有公倍數的形式，然后從中找一個小的正整數。
解決了兩個數的小公倍數與大公因數問題后，就可以求出n個數的小公倍數與大公因數問題，可以兩個兩個地求。即有下面定理
設a1,a2,a3...ax
是n個整數，(a1,a2)=d2;
(d2,a3)=d3,...
(dn-q,an)=dn,
則(a1,a2,...ax)=dx
a1,a2,...an]=mn
素數是數論研究的核心，許多中外聞名的題目都與素數有關。除1外任何正整數不是質數即為合數。判斷一個已知的正整數是否為質數可用判別定理去實現。判別定理又是證明素數無窮的關鍵。實際上，對于任何正整數n>1，由判別定理一定知存在素數p，使得p∣n 。即任何大于1的整數一定存在一個素因數p 。素數有幾個屬于內在本身的性質，這些性質是在獨有的，讀者可以用反例來證明：素數這一條件必不可少。以加深對它們的理解。其中p∣ab
→p∣a或p∣b也是常用的性質之一。也是證明算術基本定理的基礎。
算術基本定理是整數理論中重要的定理之一，即任何整數一定能分解成一些素數的乘積，而且分解是的，不是任何數集都能滿足算術基本定理的，算術基本定理為我們提供了解決其它問題的理論保障。它有許多應用，由算術基本定理我們可以得到自然數的標準分解問題。
設a=
，b=
，
則有 (a，b)=
[a，b]=
例如可求大公約數，正整數正約數的個數等方面問題，對具體的n，真正去分解是件不容易的事。對于較特殊的n，例如n!分解還是容易的。應用[x]的性質，n!的標準分解式可由一個具體的公式表示出來，這一公式結合[x]的性質又提供了解決帶有乘除符號的整除問題的方法。
本章的許多問題都圍繞著整除而展開，讀者應對整除問題的解決方法作一簡單的小結。
五、例子選講
補充知識
①小自然數原理：自然數的任意非空子集中一定存在小自然數。
②抽屜原理：
(1)設n是一個自然數，有n個盒子，n+1個物體，把n+1個物體放進n個盒子，至少有一個盒子放了兩個或兩個以上物體;
(2)km+1個元素，分成k組，至少有一組元素其個數大于或等于m+1;
(3)無限個元素分成有限組，至少有一組其元素個數為無限。
③梅森數：形如2n-1的數叫梅森數，記成Mn=2n-1。
④費爾馬數：n為非負整數，形如
的數叫費爾馬數，記成Fn=
。 ⑤設n=
，設n的正因子個數為d(n)，所有正因子之和為
，則有
⑥有關技巧
1. 整數表示a=a0×10n+a1×10n-1+…+an，
a=2kb(b為奇數)
2.整除的常用方法
a. 用定義
b. 對整數按被n除的余數分類討論
c. 連續(xù)n個整數的積一定是n的倍數
d. 因式分解
an-bn=(a-b)M1,
an+bn=(a+b)M2, 2
n
e. 用數學歸納法
f. 要證明a|b，只要證明對任意素數p，a中p的冪指數不超過b中p的冪指數即可，用p(a)表示a中p的冪指數，則a|b
p(a)
p(b)
例題選講
例1.請寫出10個連續(xù)正整數都是合數.
解: 11!+2，11!+3，……，11!+11。
例2. 證明連續(xù)三個整數中，必有一個被3整除。
證：設三個連續(xù)正數為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)。
【同余】
一、 主要內容
同余的定義、性質、剩余類和完全剩余系、歐拉函數、簡化剩余系、歐拉定理、費爾馬小定理、循環(huán)小數、特殊數2，3，4，5，6，7，8，9，11，13的整除規(guī)律
二、 基本要求
通過本章的學習，能夠掌握同余的定義和性質，區(qū)別符號：“三”和=”之間的差異。能利用同余的一些基本性質進行一些計算，深刻理解完全剩余系，簡化剩余系的定義、性質及構造。能判斷一組數是否構成模m的一個完全剩余系或一個簡化剩余系。能計算歐拉函數的值，掌握歐拉定理、費爾馬小定理的內容以及證明方法。能應用這二個定理證明有關的整除問題和求余數問題。能進行循環(huán)小數與分數的互化。
三、難點和重點
(1)同余的概念及基本性質
(2)完全剩余系和簡化剩余系的構造、判別
(3)歐拉函數計算、歐拉定理、費爾馬小定理的證明及應用
(4)循環(huán)小數與分數的互化
(5)特殊數的整除規(guī)律。
四、自學指導
同余理論是初等數論中核心的內容之一，由同余定義可知，若a≡b(mod m)，則a和b被m除后有相同的余數。這里m為正整數，一般要求m大于1，稱為模，同余這一思想本質上是將整數按模m分類，然后討論每一個類中整數所具有的共性及不同類之間的差異。第一章中用帶余除法定理將整數分類解決一些問題的方法只不過是同余理論中的一個特殊例子。從同余的定理上看，同余和整除實際上是同一回事，故同余還有二個等價的定義：①用整除來定義即 m∣a-b 。②用等號來定義a=b+mt 。值得注意a和b關于m同余是個相對概念。即它是相對于模m來講，二個整數a和b關于一個整數模m同余。則對于另一個整數模m
，a和b未必會同余。
從定義上看，同余和整除是同一個事情，但引進了新的符號“三”后，無論從問題的敘述上，還是解決問題的方法上都有了顯著的變化，同時也帶來了一些新的知識和方法。在引進了同余的代數性質和自身性質后，同余符號“三”和等號“=”相比，在形式上有幾乎一致的性質，這便于我們記憶。事實上在所有等號成立的運算中，只有除法運算是個例外，即除法的消去律不成立。為此對于同余的除法運算我們有二種除法：
(i)模不改變的除法，若ak≡bk(mod m) ，(k,m)=1，則a≡b(mod m)
(ii)模改變的除法, 若ak≡bk(mod m) (k,m)=d,則a≡b
這一點讀者要特別注意。
完全剩余系和簡化剩余系是二個全新的概念，讀者只要搞清引成這些概念的過程。因為同余關系是一個等價關系，利用等價關系可以進行將全體整數進行分類，弄清來朧去脈，對于更深刻理解其本質是很有好處的。完全剩余系或簡化剩余系是一個以整數為元素的集合，在每個剩余類各取一個數組成的m個不同數的集合，故一組完全剩余系包含m個整數，由于二個不同的剩余類中的數關于m兩兩不同余，故可得判別一組數是否為模m的一個完全剩余系的條件有二條為
(1) 個數=m
(2) 關于m兩兩不同余
另外要能用已知完全剩余系構造新的完全剩余系。即有定理
設(a，m)=1，x為m的完全剩余系，則ax+b也是m的完全剩余系。
當
時，能由
的完全剩余系和
的完全剩余系，構造
完全剩余系。為討論簡化剩余系，需要引進歐拉函數φ(m)，歐拉函數φ(m)定義為不超過m且與m互素的正整數的個數，記為φ(m)，要掌握φ(m)的計算公式，了解它的性質。這些性質主要的是當(a ,b)=1時，φ(ab) = φ(a) φ(b)，和
現在在剩余類中把與m互素的集合分出來，從中可在各個集合中任取一個數即可構造模m的一個簡化剩余系。另一方面，簡化剩余數也可從模m的一個完全剩余系中得到簡化剩余系，一組完全剩余系中與m互素的的數組成的φ(m)個不同數的集合稱為m簡化剩余系。同樣簡化剩余系也有一個判別條件。
判別一組整數是否為模m的簡化剩余系的條件為
(1) 個數=φ(m)
(2) 關于m兩兩不同余
(3) 每個數與m互素
關于m的簡化剩余系也能用已知完全剩余系構造新的簡化剩余系。
設(a，m)=1，x為m的簡化剩余系，則ax也是m的簡化剩余系。
當
時，能由
的簡化剩余系和
的簡化剩余系，構造
簡化剩余系。
歐拉定理、費爾馬小定理是同余理論非常重要的定理之一。要注意歐拉定理和費爾馬定理的條件和結論。
歐拉定理：設m為大于1的整數，(a，m)=1，則有
費爾馬小定理：若p是素數，則有
除此以外，歐拉定理的證明的思想是非常好的，在各個地方都有應用。就歐拉定理、費爾馬小定理來講，它在某些形如a
數的整除問題應用起來顯得非常方便。同余方法也是解決整除問題的方法之一。
另外同余方法在證明不定方程時也非常有用，即要掌握同余“三”和相等“=”的關系：相等必同余，同余未必相等，不同余肯定不相等。
對于特殊數的整除規(guī)律要求能掌握其一般定理的證明，并熟記一些特殊數的整除規(guī)律
1、 一個整數被2整除的充要條件是它的末位為偶數。
2、 一個整數被3整除的充要條件是它的各位數字之和能被3整除。
3、 一個整數被9整除的充要條件是它的各位數字之和能被9整除。
4、 一個整數被5整除的充要條件是它的末位為0或5。
5、 一個整數被4，25整除的充要條件是它的末二位能被4，25整除。
6、 一個整數被8，125整除的充要條件是它的末三位能被8，125整除。
7、 設
，則7或11或13整除a的充要條件是7或11或13整除
五、例子選講
例1：求3406的末二位數。
解：∵ (3，100)=1，∴3
≡1(mod 100)
(100)=
(22·52)=40, ∴ 340≡1(mol 100)
∴ 3406=(340)10·36≡(32)2·32≡-19×9≡-171≡29(mod 100)
∴ 末二位數為29。
例2：證明(a+b)p≡ap+bp(mod p)
證：由費爾馬小定理知對一切整數有：ap≡a(p)，bp≡b(P)，
由同余性質知有：ap+bp≡a+b(p)
又由費爾馬小定理有(a+b)p≡a+b (p)
(a+b)p≡ap+bp(p)
【不定方程】
一、 主要內容
不定方程有解的條件、解數、解法、通解表示，不定方程x2+y2=z2通解公式、無窮遞降法、費爾馬大定理。
二、 基本要求
1、 了解不定方程的概念，理解對“解”的認識，掌握不定方程
有解的條件，能熟練求解不定方程的特解，正整數解及通解。了解多元不定方程
有解的條件，在有解的條件下的解法。
2、掌握不定方程x2+y2=z2在一定條件下的通解公式，并運用這個通解公式作簡單的應用。
3、對費爾馬大定理應有在常識性的了解，掌握無窮遞降法求證不定方程x4+y4=z2無解的方法。
4、掌握證明不定方程無解的若干方法。
三、難點和重點
(1)重點為求解不定方程的方法
(2)掌握第二節(jié)中引證的應用。
(1) 費爾馬無窮遞降法。
四、自學指導
不定方程主要講解以下幾個問題
(i)給定一類不定方程，判別在什么條件下有解。
(ii)在有解的條件下，有多少解
(iii)在有解的條件下，求出所給的不定方程的所有解。
二元不定方程的一般形式為ax+by=c 。若(a ,b)∣c，則該二元不定方程一定有解，若已知一個特解，則一切解可以用公式表示出來，因此求它的通解只要求出一個特解即可。求解二元不定方程的一個通解有好多種方法。讀者應該總結一下，各種方法都有獨到之處。特別要指出用大公因數的方法。它的根據是求(a ,b)時所得的結果。由于注意通解公式x=x0-b1t，y=y0+a1t中a1，b1的意義和位置。以免出錯。
多元不定方程
也有類似的結果，但在求解的過程中將它轉化二元不定方程組，從后一個二元不定方程解起，可逐一解出x1 ,x2 ,……xn 。所用的方法一般選擇大公因數的方法。由于n元不定方程可轉化為n-1個二元不定方程組，故在通解中依賴于n-1個任意常數。但不象二元不定方程那樣有公式來表示。
x2+y2=z2的正整數解稱為勾股數，在考慮這個方程時，我們對(x ,y)作了一些限制，而這些限制并不影響其一般性。在條件x>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，則也有相應的一個通解公式。在證明這個通解公式的過程中，用到了引理 uv=w2，u>0，v>0，(u ,v)=1，則u=a2，v=b2，w=ab 。a>0，b>0，(a ,b)=1 。利用這個結論可以求解某些不定方程。特別當w=1或素數p 。則由uv=1或uv=P 可將原不定方程轉化為不定方程組。從而獲得一些不定方程的解。上述解不定方程的方法叫因子分解法。希望讀者能掌握這種方法。
為了解決的費爾馬大定理：xn+yn=zn ，n≥3無正整數解時，當n=4時可以用較初等的方法給出證明。證明由費爾馬本人給出的，一般稱為費爾馬無窮遞降法。其基本思想為由一組解出發(fā)通過構造得出另一組解，使得兩組解之間有某種特定的關系，而且這種構造可以無限重復的。從而可得到矛盾。因此無窮遞降法常用來證明某些不定方程無整數解。
證明一類不定方程無解是研究不定方程鄰域中常見的形式，一般的要求解不定方程比證明不定方程無解要容易些。證明不定方程無解的證明方法常采用以下形式：(反證法)
若A有解
A1有解
A2有解
……
An有解，而An本身無解，這樣來構造矛盾。從而說明原不定方程無解。
對于證明不定方程的無解性通常在幾種方法，一般是總的幾種方法交替使用。特別要求掌握：簡單同余法、因子分解法、不等式法，以及中學數學中所涉及的判別式法。
五、例子選講
例1：利用整數分離系數法求得不定方程15x+10y+6z=61。
解：注意到z的系數小，把原方程化為
z=
令t1=
，即-3x+2y-6t1+1=0 此時y系數小，
令t2 =
,即
,反推依次可解得
y=x+3t1+t2=2t2+1+3t1+t2=1+3t1+3t2
z=-2x-2y+10+t1=6-5t1+10t2
∴原不定方程解為
t1t2∈z. 例2:證明
是無理數證：假設
是有理數，則存在自數數a,b使得滿足
即
，容易知道a是偶數，設a=2a1，代入得
，又得到b為偶數，
，設
，則
,這里
這樣可以進一步求得a2，b2…且有a>b>a1>b1> a2>b2>…
但是自然數無窮遞降是不可能的，于是產生了矛盾，∴
為無理數。
例3：證明：整數勾股形的勾股中至少一個是3的倍數。
證：設N=3m±1(m為整數) ， ∴N2=9m2±6m+1=3(3m2±2m)+1
即一個整數若不是3的倍數，則其平方為3k+1,或者說3k+2不可能是平方數，設x,y為勾股整數，且x,y都不是3的倍數，則x2,y2都是3k+1，但z2=x2+y2=3k+2形，這是不可能，∴勾股數中至少有一個是3的倍數。
【整除】
一、主要內容
整除的定義、帶余除法定理、余數、大公因數、小公倍數、輾轉相除法、互素、兩兩互素、素數、合數、算術基本定理、Eratosthesen篩法、[x]和{x}的性質、n!的標準分解式。
二、基本要求
通過本章的學習，能了解引進整除概念的意義，熟練掌握整除 整除的定義以及它的基本性質，并能應用這些性質，了解解決整除問題的若干方法，熟練掌握本章中二個的定理：帶余除法定理和算術基本定理。認真體會求二個數的大公因數的求法的理論依據，掌握素數的定義以及證明素數有無窮多個的方法。能熟練求出二個整數的大公因數和小公倍數，掌握高斯函數[x]的性質及其應用。
三、重點和難點
(1)素數以及它有關的性質，判別正整數a為素數的方法，算術基本定理及其應用。
(2)素數有無窮多個的證明方法。
(3)整除性問題的若干解決方法。
(4)[x]的性質及其應用，n!的標準分解式。
四、自學指導
整除是初等數論中基本的概念之一，b∣a的意思是存在一個整數q，使得等式a=bq成立。因此這一標準作為我們討論整除性質的基礎。也為我們提供了解決整除問題的方法。即當我們無法用整除語言來敘述或討論整除問題時，可以將其轉化為我們很熟悉的等號問題。
對于整除的若干性質，主要的性質為傳遞性和線性組合性，即
(1) a∣b, b∣c, 則有a∣c
(2) a∣b, a∣c, 則有a∣mb+nc
讀者要熟練掌握并能靈活應用。特別要注意，數論的研究對象是整數集合，比小學數學中非負整數集合要大。
本章中重要的定理之一為帶余除法定理，即為
設a是整數，b是非零整數，則存在兩個整數q，r，使得
a=bq+r (0)
它可以重作是整除的推廣。同時也可以用帶余除法定理來定義整除性，(即當余數r=0時)。帶余除法可以將全體整數進行分類，從而可將無限的問題轉化為有限的問題。這是一種很重要的思想方法，它為我們解決整除問題提供了又一條常用的方法。同時也為我們建立同余理論建立了基礎。讀者應熟知常用的分類方法，例如把整數可分成奇數和偶數，特別對素數的分類方法。例全體奇素數可以分成4k+1，4k+3;或6k+1，6k+5等類型。
和整除性一樣，二個數的大公約數實質上也是用等號來定義的，因此在解決此類問題時若有必要可化為等式問題，大公因數的性質中重要的性質之一為 a=bq+c，則一定有(a，b)=(b，c)，就是求二個整數的大公約數的理論根據。也是解決關于大公約數問題的常用方法之一。讀者應有盡有認真體會該定理的證明過程。
互素與兩兩互素是二個不同的概念，既有聯系，又有區(qū)別。要認真體會這些相關的性質，例如，對于任意a ,b∈Z，可設(a ,b)=d，則a=da1 ,b=db1，則(a1 ,b1)=1，于是可對a1 ,b1使用相應的定理，要注意，相關定理及推論中互素的條件是經常出現的。讀者必須注意定理成立的條件，也可以例舉反例來進行說明以加深影響。順便指出，若a∣c，b∣c，(a ,b)=1，則ab∣c是我們解決當除數為合數時的一種方法。好處是不言而喻的。
小公倍數實際上與大公因數為對偶命題。特別要指出的是a和b的公倍數是有無窮多個。所以一般地在無窮多個數中尋找一個小數是很困難的，為此在定義中所有公倍數中的小的正整數。這一點實際上是應用自然數的小自然數原理，即自然數的任何一個子集一定有一個小自然數有在。小公倍數的問題一般都可以通過以下式子轉化為大公因數的問題。兩者的關系為
a ,b∈N， [a ,b]=ab/(a,b)
上述僅對二個正整數時成立。當個數大于2時，上述式子不再成立。證明這一式子的關鍵是尋找a , b的所有公倍數的形式，然后從中找一個小的正整數。
解決了兩個數的小公倍數與大公因數問題后，就可以求出n個數的小公倍數與大公因數問題，可以兩個兩個地求。即有下面定理
設a1,a2,a3...ax
是n個整數，(a1,a2)=d2;
(d2,a3)=d3,...
(dn-q,an)=dn,
則(a1,a2,...ax)=dx
a1,a2,...an]=mn
素數是數論研究的核心，許多中外聞名的題目都與素數有關。除1外任何正整數不是質數即為合數。判斷一個已知的正整數是否為質數可用判別定理去實現。判別定理又是證明素數無窮的關鍵。實際上，對于任何正整數n>1，由判別定理一定知存在素數p，使得p∣n 。即任何大于1的整數一定存在一個素因數p 。素數有幾個屬于內在本身的性質，這些性質是在獨有的，讀者可以用反例來證明：素數這一條件必不可少。以加深對它們的理解。其中p∣ab
→p∣a或p∣b也是常用的性質之一。也是證明算術基本定理的基礎。
算術基本定理是整數理論中重要的定理之一，即任何整數一定能分解成一些素數的乘積，而且分解是的，不是任何數集都能滿足算術基本定理的，算術基本定理為我們提供了解決其它問題的理論保障。它有許多應用，由算術基本定理我們可以得到自然數的標準分解問題。
設a=
，b=
，
則有 (a，b)=
[a，b]=
例如可求大公約數，正整數正約數的個數等方面問題，對具體的n，真正去分解是件不容易的事。對于較特殊的n，例如n!分解還是容易的。應用[x]的性質，n!的標準分解式可由一個具體的公式表示出來，這一公式結合[x]的性質又提供了解決帶有乘除符號的整除問題的方法。
本章的許多問題都圍繞著整除而展開，讀者應對整除問題的解決方法作一簡單的小結。
五、例子選講
補充知識
①小自然數原理：自然數的任意非空子集中一定存在小自然數。
②抽屜原理：
(1)設n是一個自然數，有n個盒子，n+1個物體，把n+1個物體放進n個盒子，至少有一個盒子放了兩個或兩個以上物體;
(2)km+1個元素，分成k組，至少有一組元素其個數大于或等于m+1;
(3)無限個元素分成有限組，至少有一組其元素個數為無限。
③梅森數：形如2n-1的數叫梅森數，記成Mn=2n-1。
④費爾馬數：n為非負整數，形如
的數叫費爾馬數，記成Fn=
。 ⑤設n=
，設n的正因子個數為d(n)，所有正因子之和為
，則有
⑥有關技巧
1. 整數表示a=a0×10n+a1×10n-1+…+an，
a=2kb(b為奇數)
2.整除的常用方法
a. 用定義
b. 對整數按被n除的余數分類討論
c. 連續(xù)n個整數的積一定是n的倍數
d. 因式分解
an-bn=(a-b)M1,
an+bn=(a+b)M2, 2
n
e. 用數學歸納法
f. 要證明a|b，只要證明對任意素數p，a中p的冪指數不超過b中p的冪指數即可，用p(a)表示a中p的冪指數，則a|b
p(a)
p(b)
例題選講
例1.請寫出10個連續(xù)正整數都是合數.
解: 11!+2，11!+3，……，11!+11。
例2. 證明連續(xù)三個整數中，必有一個被3整除。
證：設三個連續(xù)正數為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)。