【正文】 時(shí)，． （2）若，則。若，則。由且得，又，得．（3）若，且，則．（4）若，則．證明 （定義法）由，有 ，得 ，即 ．（5）若，則．（6）若，則對(duì)任意整數(shù)，有．證明 （定義法）由，有 ，得 ，即 ．（7）若，且，則．證明 由知存在整數(shù)，使，有， 因?yàn)?，所以整除等式的左邊，進(jìn)而整除等式的右邊，即．注意 不能由且得出．如，但且．（8）若，且，則．證明 由知存在整數(shù)，使，有， 又由有代入得，所以． 注意 不能由且得出．如不能由且得出．（9）若為素?cái)?shù)，且，則或．證明 若不然，則且，由為素?cái)?shù)得，由互素的性質(zhì)（6）得，再由為素?cái)?shù)得，與矛盾．注意 沒有為素?cái)?shù)，不能由推出或．如，但且．定義6 對(duì)于整數(shù)，且，若，則稱關(guān)于模同余，記作；若，則稱關(guān)于模不同余，記作． 定理9（同余的性質(zhì)）設(shè)為整數(shù)，（1）若且，則；證明 由且，有 ，得．（2）若且，則且．證明 由且，有 ， ①對(duì)①直接相加 ，有，得 .對(duì)①分別乘以后相加，有，得 ．（3）若，則對(duì)任意的正整數(shù)有且.（4）若，且對(duì)非零整數(shù)有，則．證明 由、有 ，又，有均為整數(shù)，且，得 ．定理10 設(shè)為整數(shù)，為正整數(shù)，（1）若，則．．（2）若，則．．（3）若，則．．定義7 設(shè)為正整數(shù)，為大于2的正整數(shù), 是小于的非負(fù)整數(shù)，且．若 ，則稱數(shù)為的進(jìn)制表示．定理11 給定整數(shù)，對(duì)任意的正整數(shù)，都有唯一的進(jìn)制表示．如，（10進(jìn)制）．（２進(jìn)制）定理12 （算術(shù)基本定理）每個(gè)大于1的正整數(shù)都可分解為素?cái)?shù)的乘積，而且不計(jì)因數(shù)的順序時(shí)，這種表示是唯一的 ，其中為素?cái)?shù)，為正整數(shù)． （分解唯一性）證明1 先證明，正整數(shù)可分解為素?cái)?shù)的乘積 ． ①如果大于1的正整數(shù)為素?cái)?shù)，命題已成立．當(dāng)正整數(shù)為合數(shù)時(shí)，的正約數(shù)中必有一個(gè)最小的，記為，則為素?cái)?shù)，有，．如果為素?cái)?shù)，命題已成立．當(dāng)為合數(shù)時(shí)，的最小正約數(shù)為必為素?cái)?shù)，有 ，．這個(gè)過程繼續(xù)進(jìn)行下去，由于為有限數(shù)，而每進(jìn)行一步就要變小一次，于是，經(jīng)過有限次后，比如次，就變?yōu)樗財(cái)?shù)的乘積 ．下面證明分解式是唯一的．假設(shè)還有另一個(gè)分解式 ， ②則有 ． ③因?yàn)榈仁降挠疫吥鼙徽宰筮呉材鼙徽?，于是整除中的某一個(gè)，但為素?cái)?shù)，所以與相等，不妨設(shè)為，有 ．把等式③兩邊約去，得 ．再重復(fù)上述步驟，又可得，…，直到等式某一邊的因數(shù)被全部約完，這時(shí)，如果另一邊的因數(shù)沒有約完，比如右邊沒有被約完（），則有 ． ④但均為素?cái)?shù)，素?cái)?shù)都大于1，有，這表明等式④不可能成立，兩個(gè)分解式的因數(shù)必然被同時(shí)約完，即分解式是唯一的． 將分解式按的遞增排列，并將相同的合并成指數(shù)形式，即得．其中為素?cái)?shù)，為正整數(shù)． 證明2 用第二數(shù)學(xué)歸納法證明，．（1）當(dāng)，因?yàn)?為素?cái)?shù)，命題成立．（2）假設(shè)命題對(duì)一切大于1而小于的正整數(shù)已成立．這時(shí)，若為素?cái)?shù)，命題成立；若不為素?cái)?shù)，必存在，使 ，由歸納假設(shè)，小于的可分解為素?cái)?shù)的乘積 得 ，適當(dāng)調(diào)整的順序，可得命題對(duì)于正整數(shù)成立．由數(shù)學(xué)歸納法，命題對(duì)一切大于1的正整數(shù)成立．下面證明分解式是唯一的．假設(shè)的分解式不唯一，則至少有兩個(gè)分解式， ，得 ．有 且，這就存在，使且，但均為為素?cái)?shù)，所以， 又 ，所以 ．把等式兩邊約去，得 ．再重復(fù)上述步驟，又可得，…，直到等式某一邊的因數(shù)被全部約完，這時(shí)，如果另一邊的因數(shù)沒有約完，比如右邊沒有被約完（），則有 ．但均為素?cái)?shù)，素?cái)?shù)都大于1，有，這表明上述等式不可能成立，兩個(gè)分解式的因數(shù)必然被同時(shí)約完，即分解式是唯一的．將分解式按的遞增排列，并將相同的合并成指數(shù)形式，即得．其中為素?cái)?shù)，為正整數(shù)． 定理13 若正整數(shù)的素?cái)?shù)分解式為 則的正約數(shù)的個(gè)數(shù)為，的一切正約數(shù)之和為 ．證明 對(duì)于正整數(shù)，它的任意一個(gè)正約數(shù)可以表示為 ， ， ①由于有共種取值，據(jù)乘法原理得的約數(shù)的個(gè)數(shù)為．考慮乘積 ，展開式的每一項(xiàng)都是的某一個(gè)約數(shù)（參見①），反之，的每一個(gè)約數(shù)都是展開式的某一項(xiàng)，于是，的一切約數(shù)之和為．注 構(gòu)造法．定義8 （高斯函數(shù)）對(duì)任意實(shí)數(shù)，是不超過的最大整數(shù)．亦稱為的整數(shù)部分，．定理14 在正整數(shù)的素因子分解式中，素?cái)?shù)作為因子出現(xiàn)的次數(shù)是 ．證明 由于為素?cái)?shù)，故在中的次方數(shù)是各數(shù)中的次方數(shù)的總和（注意，若不為素?cái)?shù)，這句話不成立）．在中，有個(gè)的倍數(shù)；在個(gè)的倍數(shù)的因式中，有個(gè)的倍數(shù)；在個(gè)的倍數(shù)的因式中，有個(gè)的倍數(shù)；…，如此下去，在正整數(shù)的素因子分解式中，素?cái)?shù)作為因子出現(xiàn)的次數(shù)就為 ．注 省略號(hào)其實(shí)是有限項(xiàng)之和．畫線示意中2的指數(shù)．定理15 （費(fèi)瑪小定理）如果素?cái)?shù)不能整除整數(shù)，則．證明1 考察下面的個(gè)等式： ，……，由于素?cái)?shù)不能整除整數(shù)，所以，不能整除每個(gè)等式的左邊，得均不為0，只能?。旅孀C明各不相等．若不然，存在，使 相減 ．應(yīng)有素?cái)?shù)整除，但素?cái)?shù)不能整除，所以素?cái)?shù)整除，然而由可得 ，要素?cái)?shù)整除是不可能的，得各不相等．有 ．再把上述個(gè)等式相乘，有 ，即 ，其中是一個(gè)整數(shù)．亦即 ． 由于是素?cái)?shù)，不能整除，所以素?cái)?shù)整除，得證 證明2 改證等價(jià)命題：如果素?cái)?shù)不能整除整數(shù)，則．只需對(duì)證明成立，用數(shù)學(xué)歸納法．（1），命題顯然成立．（2）假設(shè)命題對(duì)成立，則當(dāng)時(shí)，由于，故有 ．（用了歸納假設(shè)）這表明，命題對(duì)是成立． 由數(shù)學(xué)歸納法得．又素?cái)?shù)不能整除整數(shù)，有，得．定義9 （歐拉函數(shù)）用表示不大于且與互素的正整數(shù)個(gè)數(shù)．定理16 設(shè)正整數(shù)，則 ．證明 用容斥原理．設(shè)，記為中能被整除的數(shù)所組成的集合（），用表示中元素的個(gè)數(shù)，有，．易知，中與互素的正整數(shù)個(gè)數(shù)為 ，由容斥原理得 注 示意的容斥原理．推論 對(duì)素?cái)?shù)有．定理17 整系數(shù)不定方程（）存在整數(shù)解的充分必要條件是．證明 記．（1）必要性（方程有解必須滿足的條件）．若方程存在整數(shù)解，記為，則，由， 有，得證．（2）充分性（條件能使方程有解）．若，可設(shè)由于形如的數(shù)中有最小正數(shù)滿足．兩邊乘以，得 這表明方程有解定理18 若,，且是整系數(shù)不定方程的一個(gè)整數(shù)解，則方程的一切整數(shù)解可以表示為 ． ①證明 直接代入知①是方程的整數(shù)解，下面證明任意一個(gè)整數(shù)解都有①的形式.由是方程的一個(gè)解，有， 又方程的任意一個(gè)解滿足 ， ②相減 ． ③ 但，故有 ，有 得方程的任意一個(gè)整數(shù)解可以表示為 ．定義10 （平面整點(diǎn)）在平面直角坐標(biāo)系上，縱橫坐標(biāo)都是整數(shù)的點(diǎn)稱為整點(diǎn)（也稱格點(diǎn)）．類似地可以定義空間整點(diǎn)．第二講 數(shù)論題的范例講解主要講幾個(gè)重要類型：奇數(shù)與偶數(shù)，約數(shù)與倍數(shù)（素?cái)?shù)與合數(shù)），平方數(shù)，整除，同余，不定方程，數(shù)論函數(shù)等．重點(diǎn)是通過典型范例來(lái)分析解題思路、提煉解題方法和鞏固基本內(nèi)容．一、奇數(shù)與偶數(shù)整數(shù)按照能否被2整除可以分為兩類，一類余數(shù)為0，稱為偶數(shù)，一類余數(shù)為1，稱為奇數(shù)．偶數(shù)可以表示為，奇數(shù)可以表示為或．一般地，整數(shù)被正整數(shù)去除，按照余數(shù)可以分為類，稱