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