第一篇：數(shù)論感想

本學(xué)期，我們分了專業(yè)方向，我選擇的是信息安全，有幸聽了數(shù)論基礎(chǔ)課。根據(jù)這一學(xué)期的所學(xué)所想，我做了簡(jiǎn)單的總結(jié)。

其實(shí)，在分專業(yè)方向的時(shí)候，我對(duì)“信息安全”這個(gè)名詞并沒有什么概念，只是通過老師的介紹和查閱相關(guān)資料，才對(duì)這個(gè)方向有了淺顯的認(rèn)識(shí)。在信息膨脹、全球化網(wǎng)絡(luò)化的今天，大量的數(shù)據(jù)信息在互聯(lián)網(wǎng)上傳播。因此，對(duì)于私密信息的保密處理顯得尤為重要。

依然記得自己QQ號(hào)被盜時(shí)候的憤懣，雖然沒有什么隱私可以泄漏，但是我對(duì)這種現(xiàn)象的出現(xiàn)就感到很不愉快。加上互聯(lián)網(wǎng)正值壯年，蓬勃發(fā)展的時(shí)期，黑客的瘋狂出現(xiàn)與信息的泄露成為互聯(lián)網(wǎng)維護(hù)的一大難題。因此，我非常想擁有保護(hù)自己隱私的能力。同時(shí)，我個(gè)人一直對(duì)網(wǎng)絡(luò)攻防方面很有興趣，對(duì)這個(gè)新生起的環(huán)境有著極大的好奇心。因此，我毅然選擇了信息安全這條道路。

通過老師的講授、相關(guān)資料的查詢以及與同學(xué)的討論，我了解到信息安全的基礎(chǔ)是加密處理，掌握了最基本的加密原理，才能對(duì)破密及防盜有進(jìn)一步的研究。所以，這就需要密碼學(xué)這門課來完善我們的基礎(chǔ)知識(shí)體系。同時(shí)，記得老師說過信息安全的尖端拼的是數(shù)學(xué)功底，我們需要的是強(qiáng)大的數(shù)學(xué)思維以及深厚的數(shù)學(xué)功底。所以，我們學(xué)院安排了密碼學(xué)基礎(chǔ)和抽象代數(shù)這兩大專業(yè)課。這兩門課將對(duì)我們今后的學(xué)習(xí)工作提供最基礎(chǔ)的理論與邏輯的支持，但是，同時(shí)又要求有更加基礎(chǔ)的學(xué)科來做鋪墊，那就是我們這堂課所學(xué)的數(shù)論基礎(chǔ)。由于種種原因，我們這屆的數(shù)論基礎(chǔ)課是第一屆開課，也將是最后一節(jié)課，我不免對(duì)未來失去學(xué)習(xí)這門課的學(xué)弟學(xué)妹們表示遺憾。

我對(duì)“數(shù)論”這個(gè)名詞的概念來自于高中數(shù)學(xué)競(jìng)賽期間參加的培訓(xùn)班，當(dāng)時(shí)有許多名師來為我們講授各種競(jìng)賽知識(shí)，包括蘇遠(yuǎn)東教授和陶平生教授的初等數(shù)論。因此，當(dāng)我聽說我們要學(xué)習(xí)這門課的時(shí)候，我很是高興，感覺毫無壓力。但是，當(dāng)我翻開《數(shù)論講義》這本教材的時(shí)候，頓時(shí)心中一涼。正如前言所述，初等數(shù)論是主要用算術(shù)方法研究整數(shù)性質(zhì)的一個(gè)數(shù)論分支，它是數(shù)學(xué)中最古老的分支之一。同時(shí)，在數(shù)學(xué)發(fā)展史上，常?？梢园l(fā)現(xiàn)，對(duì)初等數(shù)論中某些問題的研究，曾促使數(shù)學(xué)中新分支的發(fā)展。近幾十年來，初等數(shù)論在計(jì)算機(jī)科學(xué)、組合數(shù)學(xué)、代數(shù)編碼、信號(hào)的數(shù)字處理等領(lǐng)域內(nèi)得到廣泛的應(yīng)用，而且許多較深刻的結(jié)果都得到了應(yīng)用。其實(shí)大學(xué)的數(shù)論基礎(chǔ)知識(shí)數(shù)論領(lǐng)域中的一角，而我們高中所接觸的數(shù)論知識(shí)只占了本教材的第一章內(nèi)容，是皮毛中的皮毛。所以，我頓時(shí)感覺任重而道遠(yuǎn)啊。詳細(xì)翻閱本教材里面的內(nèi)容，涉及范圍很廣，從整數(shù)性質(zhì)引出同余關(guān)系，進(jìn)而延伸到二次剩余及原根次數(shù)的求解，并在最后逐步涉及到素性的判別。這么多的內(nèi)容包含在區(qū)區(qū)180頁(yè)的書中，可想“教材內(nèi)部的空虛”。但是，郭老師講課的風(fēng)格很適合我們這些初學(xué)者，教材、ppt和板書的結(jié)合，不僅將整個(gè)書的內(nèi)容做了充分的擴(kuò)充，還教會(huì)了我們解決數(shù)學(xué)問題的基本思想。這種處理問題的思想是在課上潛移默化習(xí)得的，也是成為一名網(wǎng)絡(luò)高手不可或缺的財(cái)富。雖然這門課程結(jié)束了，但是老師教給我們的這些思想是永恒的。結(jié)合本學(xué)期所學(xué)的抽象代數(shù)，可以看出，數(shù)論是抽象代數(shù)的具體體現(xiàn)，而抽象代數(shù)則是數(shù)論的抽象化、代數(shù)化、邏輯化、理論化延伸，兩者相生相和，結(jié)合成了我們這學(xué)期所收獲的對(duì)信息安全課程最基本的認(rèn)識(shí)。

最后，感謝老師這學(xué)期教給我們的一切知識(shí)、解題方法以及數(shù)學(xué)思想。我現(xiàn)在對(duì)信息安全這個(gè)分支的了解還只是停留在表面，以后的學(xué)習(xí)工作中還會(huì)向您請(qǐng)教，并在自己選擇的方向上作出一番成績(jī)。

第二篇：初等數(shù)論復(fù)習(xí)題

1、如果(a,b)?1，則(ab,a?b)=

2、求[136,221,391]=

3、{-9/7}=；

4、當(dāng)x不是整數(shù)時(shí)，{-x}=；

5、模11的最小正完全剩余系是 {} ；

6、設(shè)2a與3b是正整數(shù)，則在1, 2, …,2 a中能被3b整除的整數(shù)有7、154440的標(biāo)準(zhǔn)分解式是；

8、今天是星期一，過10100天后是；

9、2000！中末尾0的個(gè)數(shù)有。

10、求15！的標(biāo)準(zhǔn)分解式。

11、解不定方程6x?17y?18.12、求不定方程25x?13y?7z?4的所有正整數(shù)解。

13、將17/105 寫成三個(gè)既約分?jǐn)?shù)之和，它們的分母分別是3，5和7。

14、用數(shù)學(xué)歸納法證明：證明相鄰兩個(gè)偶數(shù)的乘積是8的倍數(shù).15、證明：素?cái)?shù)的個(gè)數(shù)無窮多。

16、證明：如果a,b是兩個(gè)整數(shù),b?0,則存在唯一的整數(shù)對(duì)q,r,使得a?bq?r,其中0?r?b.17、第一章課后練習(xí)選兩題。；

第三篇：初等數(shù)論學(xué)習(xí)心得

《初等數(shù)論》學(xué)習(xí)心得

要寫學(xué)習(xí)心得并不是什么難事，不過我覺得這一次的學(xué)習(xí)心得又有些不太一樣的地方。在選課的時(shí)候，我并不盲目跟隨，不僅僅是為了拿學(xué)分，我有自己的想法。因?yàn)?，作為一個(gè)即將走向教師講臺(tái)的師范類數(shù)學(xué)專業(yè)的畢業(yè)生，如果連一些比較基本的東西都不了解，那怎么能夠在學(xué)生面前講解呢?；诖?，我選擇了《初等數(shù)論》這門課程，并希望能在此收獲一些東西。

雖然之前就了解過一些關(guān)于數(shù)論的知識(shí)，但僅僅是皮毛上的了解，再說也不能系統(tǒng)地接觸到這門課程。不過，通過這幾節(jié)課的學(xué)習(xí)，我對(duì)初等數(shù)論》這門課程有了進(jìn)一步的了解和認(rèn)識(shí)。通過一個(gè)多星期的學(xué)習(xí)，我了解到這門課程主要研究的一些內(nèi)容。

一、整除理論。引入整除、因數(shù)、倍數(shù)、質(zhì)數(shù)與合數(shù)等基本概念。這一理論的主要成果有：唯一分解定理、裴蜀定理、歐幾里德的輾轉(zhuǎn)相除法、算術(shù)基本定理、素?cái)?shù)個(gè)數(shù)無限證明。

二、同余理論。主要出自于高斯的《算術(shù)研究》內(nèi)容。定義了同余、原根、指數(shù)、平方剩余、同余方程等概念。主要成果： 二次互反律、歐拉定理、費(fèi)馬小定理、威爾遜定理、孫子定理（即中國(guó)剩余定理）等等。

三、連分?jǐn)?shù)理論。引入了連分?jǐn)?shù)概念和算法等等。特別是研究了整數(shù)平方根的連分?jǐn)?shù)展開。主要成果： 循環(huán)連分?jǐn)?shù)展開、最佳逼近問題、佩爾方程求解。

四、不定方程。主要研究了低次代數(shù)曲線對(duì)應(yīng)的不定方程，比如勾股方程的商高定理、佩爾方程的連分?jǐn)?shù)求解。也包括了4次費(fèi)馬方程的求解問題等等。

五、數(shù)論函數(shù)。比如歐拉函數(shù)、莫比烏斯變換等等。

六、高斯函數(shù)。在數(shù)學(xué)領(lǐng)域，高斯函數(shù)在厄爾米特多項(xiàng)式的定義中起著重要作用。

我知道一個(gè)星期的時(shí)間是不可能把《初等數(shù)論》這門課程學(xué)得很好的，只能大致的了解它的全貌或者說是對(duì)某一部分的內(nèi)容進(jìn)行研究。在這些天的學(xué)習(xí)中，我對(duì)數(shù)學(xué)這個(gè)浩瀚海洋里的《初等數(shù)論》部分的內(nèi)容有了更進(jìn)一步的認(rèn)識(shí)，這為我以后走上教學(xué)崗位，提升專業(yè)素養(yǎng)有著不可分割的關(guān)系，也許就是這么一些點(diǎn)點(diǎn)滴滴的學(xué)習(xí)和積累才能讓一個(gè)數(shù)學(xué)教師在自己的三尺講臺(tái)上站得更穩(wěn)，才能成為學(xué)生眼中知識(shí)淵博的老師。

總之，這一個(gè)多星期的學(xué)習(xí)讓我受益匪淺，讓我在專業(yè)知識(shí)上又邁進(jìn)了一步，雖然不能深入研究，但在面上的了解更廣了，至少能夠收獲一些之前我所想要的，開拓和豐富了我對(duì)數(shù)學(xué)世界的視野。尤其是老師主要講解的整除理論和同余理論與我以后走上講臺(tái)后所需要用到的知識(shí)聯(lián)系非常密切，它會(huì)在我的教師成長(zhǎng)之路上一直伴我前行！

第四篇：ZJZ數(shù)論練習(xí)(一)

ZJZ數(shù)論練習(xí)

（一）1.設(shè)Mp=2p-1，p是素?cái)?shù)，證明：若p≠q，則 Mp，Mq =1.2.設(shè)p是素?cái)?shù)，且p2+71的不同正因數(shù)的個(gè)數(shù)不超過10個(gè)，求p.3.已知m，n，k是正整數(shù)，且mn|nm，nk|kn，證明：mk|km.4.已知a是正整數(shù)，且a4+a3+a2+a+1是完全平方數(shù)，求所有滿足條件的a

5.設(shè)n為正整數(shù).證明：22+22nn?1+1至少有n個(gè)不同的素因子.6.證明：若正整數(shù)a、b滿足2a2+a=3b2+b，則a-b是完全平方數(shù).7.證明：有無窮多個(gè)奇數(shù)m，使8m+9m2是合數(shù).8.設(shè)m，n，k都是正整數(shù)，滿足[m+k，m]=[n+k，n]，證明：m=n.9.設(shè)正整數(shù)a，b，c，d滿足ab=cd，證明：a+b+c+d不是素?cái)?shù).10.設(shè)整數(shù)a、b、c、d滿足a>b>c>d>0，且a2+ac-c2=b2+bd-d2.證明：ab+cd不是

素?cái)?shù).

第五篇：初等數(shù)論教案1

第二節(jié) 最大公因數(shù)與輾轉(zhuǎn)相除法

第三節(jié) 最小公倍數(shù)

教學(xué)目的：

1、掌握最大公因數(shù)與最小公倍數(shù)性質(zhì)；

2、掌握輾轉(zhuǎn)相除法；

3、會(huì)求最大公因數(shù)與最小公倍數(shù).教學(xué)重點(diǎn)：最大公因數(shù)與最小公倍數(shù)性質(zhì) 教學(xué)難點(diǎn)：輾轉(zhuǎn)相除法 教學(xué)課時(shí)：6課時(shí) 教學(xué)過程

一、最大公因數(shù)

1、定義

1整數(shù)a1, a2, ?, ak的公共約數(shù)稱為a1, a2, ?, ak的公約數(shù).不全為零的整數(shù)a1, a2, ?, ak的公約數(shù)中最大的一個(gè)叫做a1, a2, ?, ak的最大公約數(shù)（或最大公因數(shù)），記為(a1, a2, ?, ak).注：

1、由于每個(gè)非零整數(shù)的約數(shù)的個(gè)數(shù)是有限的，所以最大公約數(shù)是存在的，并且是正整數(shù).2、如果(a1, a2, ?, ak)= 1，則稱a1, a2, ?, ak是互素的（或互質(zhì)的）；如果

(ai, a j)= 1，1 ? i, j ? k，i ? j，則稱a1, a2, ?, ak是兩兩互素的（或兩兩互質(zhì)的）.顯然，a1, a2, ?, ak兩兩互素可以推出(a1, a2, ?, ak)= 1，反之則不然，例如(2, 6, 15)= 1，但(2, 6)= 2.2、定理

1下面的等式成立：(ⅰ)(a1, a2, ?, ak)=(|a1|, |a2|, ?, |ak|)；(ⅱ)(a, 1)= 1，(a, 0)= |a|，(a, a)= |a|；(ⅲ)(a, b)=(b, a)；

(ⅳ)若p是素?cái)?shù)，a是整數(shù)，則(p, a)= 1或p?a；(ⅴ)若a = bq ? r，則(a, b)=(b, r).證明：(ⅰ)??(ⅳ)留作習(xí)題.(ⅴ)由第一節(jié)定理1可知，如果d?a，d?b，則有d?r = a ? bq，反之，若d?b，d?r，則d?a = bq ? r.因此a與b的全體公約數(shù)的集合就是b與r的全體公約數(shù)的集合，這兩個(gè)集合中的最大正數(shù)當(dāng)然相等，即(a, b)=(b, r).證畢

3、定理

2設(shè)a1, a2, ?, ak?Z，記

A = { y；y =?aixi，xi?Z，? ? i ? k }.i?1k如果y0是集合A中最小的正數(shù)，則y0 =(a1, a2, ?, ak).證明

設(shè)d是a1, a2, ?, ak的一個(gè)公約數(shù)，則d?y0，所以d ? y0.另一方面，由第一節(jié)例2知，y0也是a1, a2, ?, ak的公約數(shù).因此y0是a1, a2, ?, ak的公約數(shù)中的最大者，即y0 =(a1, a2, ?, ak).證畢

推論

1設(shè)d是a1, a2, ?, ak的一個(gè)公約數(shù)，則d?(a1, a2, ?, ak).注：這個(gè)推論對(duì)最大公約數(shù)的性質(zhì)做了更深的刻劃：最大公約數(shù)不但是公約數(shù)中的最大的，而且是所有公約數(shù)的倍數(shù).推論2

(ma1, ma2, ?, mak)= |m|(a1, a2, ?, ak).推論

3記? =(a1, a2, ?, ak)，則

(aa1a2，?,k)= 1，???特別地,(ab,)= 1.(a,b)(a,b)

4、定理

3(a1, a2, ?, ak)= 1的充要條件是存在整數(shù)x1, x2, ?, xk，使得

a1x1 ? a2x2 ? ? ? akxk = 1.(1)證明

必要性

由定理2得到.充分性

若式(1)成立，如果(a1, a2, ?, ak)= d > 1，那么由d?ai（1 ? i ? k）推出d?a1x1 ? a2x2 ? ? ? akxk = 1，這是不可能的.所以有(a1, a2, ?, ak)= 1.證畢

5、定理

4對(duì)于任意的整數(shù)a，b，c，下面的結(jié)論成立：(ⅰ)由b?ac及(a, b)= 1可以推出b?c；(ⅱ)由b?c，a?c及(a, b)= 1可以推出ab?c.證明

(ⅰ)若(a, b)= 1，由定理2，存在整數(shù)x與y，使得

ax ? by = 1.因此

acx ? bcy = c.(2)由上式及b?ac得到b?c.結(jié)論(ⅰ)得證；

(ⅱ)若(a, b)= 1，則存在整數(shù)x，y使得式(2)成立.由b?c與a?c得到ab?ac，ab?bc，再由式(2)得到ab?c.結(jié)論(ⅱ)得證.證畢

推論

1若(a, b)= 1，則(a, bc)=(a, c).證明

設(shè)d是a與bc的一個(gè)公約數(shù)，則d?a，d?bc，由式（2）得到，d|c, 即d是a與c的公約數(shù).另一方面，若d是a與c的公約數(shù)，則它也是a與bc的公約數(shù).因此，a與c的公約數(shù)的集合，就是a與bc的公約數(shù)的集合，所以(a, bc)=(a, c).證畢

推論

2若(a, bi)= 1，1 ? i ? n，則(a, b1b2?bn)= 1.證明

留作習(xí)題.6、定理

5對(duì)于任意的n個(gè)整數(shù)a1, a2, ?, an，記

(a1, a2)= d2，(d2, a3)= d3，?，(dn ? 2, an ? 1)= dn ? 1，(dn ? 1, an)= dn，則

dn =(a1, a2, ?, an).證明

由定理2的推論，我們有

dn =(dn ? 1, an)? dn?an，dn?dn ? 1，dn ? 1 =(dn ? 2, an ? 1)? dn ? 1?an ? 1，dn ? 1?dn ? 2，? dn?an，dn?an ? 1，dn?dn ? 2，dn ? 2 =(dn ? 3, an ? 2)? dn ? 2?an ? 2，dn ? 2?dn ? 3

? dn?an，dn?an ? 1，dn?an ? 2，dn?dn ? 3，? ?

d2 =(a1, a2)? dn?an，dn?an ? 1，?，dn?a2，dn?a1，即dn是a1, a2, ?, an的一個(gè)公約數(shù).另一方面，對(duì)于a1, a2, ?, an的任何公約數(shù)d，由定理2的推論及d2, ?, dn的定義，依次得出

d?a1，d?a2 ? d?d2，d?d2，d?a3 ? d?d3，? ?

d?dn ? 1，d?an ? d?dn，因此dn是a1, a2, ?, an的公約數(shù)中的最大者，即dn =(a1, a2, ?, an).例

1證明：若n是正整數(shù)，則21n?414n?3是既約分?jǐn)?shù).解：由定理1得到

(21n ? 4, 14n ? 3)=(7n ? 1, 14n ? 3)=(7n ? 1, 1)= 1.注：一般地，若(x, y)= 1，那么，對(duì)于任意的整數(shù)a，b，有(x, y)=(x ?ay, y)=(x ?ay, y ? b(x ?ay))=(x ?ay,(ab ? 1)y ? bx)，因此，x?ay(ab?1)y?bx是既約分?jǐn)?shù).例

2證明：121?|n2 ? 2n ? 12，n?Z.解：由于121 = 112，n2 ? 2n ? 12 =(n ? 1)2 ? 11，所以，若

112?(n ? 1)2 ? 11，則11?(n ? 1)2，因此，由定理4的推論1得到

11?n ? 1，112?(n ? 1)2.再由式(3)得到

112?11，這是不可能的.所以式(3)不能成立.注：這個(gè)例題的一般形式是： 設(shè)p是素?cái)?shù)，a，b是整數(shù)，則

pk?|(an ? b)k ? pk ? 1c，其中c是不被p整除的任意整數(shù)，k是任意的大于1的整數(shù).例

3設(shè)a，b是整數(shù)，且

9?a2 ? ab ? b2，則3?(a, b).(3)

(4)

解：由式(4)得到

9?(a ? b)2 ? 3ab ? 3?(a ? b)2 ? 3ab

? 3?(a ? b)2 ? 3?a ? b

(5)? 9?(a ? b)2.再由式(4)得到

9?3ab ? 3?ab.因此，由定理4的推論1，得到

3?a或3?b.若3?a，由式(5)得到3?b；若3?b，由(5)式也得到3?a.因此，總有3?a且3?b.由定理2的推論推出3?(a, b).例

4設(shè)a和b是正整數(shù)，b > 2，則2b ? 1?|2a ? 1.解：(ⅰ)若a < b，且

2b ? 1?2a ? 1.(6)成立，則

2b ? 1 ? 2a ? 1 ? 2b ? 2a ? 2 ? 2a(2b ? a ? 1)? 2，于是a = 1，b ? a = 1，即b = 2，這是不可能的，所以式(6)不成立.(ⅱ)若a = b，且式(6)成立，則由式(6)得到

2a ? 1?(2a ? 1)? 2 ? 2a ? 1?2 ? 2a ? 1 ? 2 ? 2a ? 3，于是b = a = 1，這是不可能的，所以式(6)不成立.(ⅲ)若a > b，記a = kb ? r，0 ? r < b，此時(shí)

2kb ? 1 =(2b ? 1)(2(k ? 1)b ? 2(k ? 2)b ? ? ? 1)=(2b ? 1)Q，其中Q是整數(shù).所以

2a ? 1 = 2kb + r ? 1 = 2r(2kb ? 1 ? 1)? 1 = 2r((2b ? 1)Q ? 1)? 1 =(2b ? 1)Q ? ?(2r ? 1)，其中Q?是整數(shù).因此

2b ? 1?2a ? 1 ? 2b ? 1?2r ? 1，在(ⅰ)中已經(jīng)證明這是不可能的，所以式(6)不能成立.綜上證得2b ? 1?|2a ? 1.二、最小公倍數(shù)

1、定義

1整數(shù)a1, a2, ?, ak的公共倍數(shù)稱為a1, a2, ?, ak的公倍數(shù).a1, a2, ?, ak的正公倍數(shù)中的最小的一個(gè)叫做a1, a2, ?, ak的最小公倍數(shù)，記為[a1, a2, ?, ak].2、定理

1下面的等式成立：(ⅰ)[a, 1] = |a|，[a, a] = |a|；(ⅱ)[a, b] = [b, a]；

(ⅲ)[a1, a2, ?, ak] = [|a1|, |a2| ?, |ak|]；(ⅳ)若a?b，則[a, b] = |b|.證明

留作習(xí)題.由定理1中的結(jié)論(ⅲ)可知，在討論a1, a2, ?, ak的最小公倍數(shù)時(shí)，不妨假定它們都是正整數(shù).在本節(jié)中總是維持這一假定.最小公倍數(shù)和最大公約數(shù)之間有一個(gè)很重要的關(guān)系，即下面的定理.3、定理

2對(duì)任意的正整數(shù)a，b，有

[a, b] =

ab(a,b).證明：設(shè)m是a和b的一個(gè)公倍數(shù)，那么存在整數(shù)k1，k2，使得m = ak1，m = bk2，因此

ak1 = bk2.(1)于是

abk1?k2.(a,b)(a,b)由于(ab,)= 1，所以(a,b)(a,b)b|k1，即k1?bt(a,b)(a,b)，其中t是某個(gè)整數(shù).將上式代入式(1)得到

m =

abt.(a,b)

(2)另一方面，對(duì)于任意的整數(shù)t，由式(2)所確定的m顯然是a與b的公倍數(shù)，因此a與b的公倍數(shù)必是式(2)中的形式，其中t是整數(shù).當(dāng)t = 1時(shí)，得到最小公倍數(shù)

[a, b] =

ab(a,b).推論

1兩個(gè)整數(shù)的任何公倍數(shù)可以被它們的最小公倍數(shù)整除.證明

由式(2)可得證.這個(gè)推論說明：兩個(gè)整數(shù)的最小公倍數(shù)不但是最小的正倍數(shù)，而且是另外的公倍數(shù)的約數(shù).推論2

設(shè)m，a，b是正整數(shù)，則[ma, mb] = m[a, b].證明

由定理2及前面的定理2的推論得到

m2abm2abmab??[ma, mb] == m[a, b].(ma,mb)m(a,b)(a,b)證畢

4、定理

3對(duì)于任意的n個(gè)整數(shù)a1, a2, ?, an，記

[a1, a2] = m2，[m2, a3] = m3，?，[mn?2, an?1] = mn?1，[mn?1, an] = mn，則

[a1, a2, ?, an] = mn.證明：我們有

mn = [mn?1, an] ? mn?1?mn，an?mn，mn?1 = [mn?2, an?1] ? mn?2?mn?1?mn，an?mn，an?1?mn?1?mn，mn?2 = [mn?3, an?2] ? mn?3?mn?2?mn，an?mn，an?1?mn，an?2?mn，? ?

m2 = [a1, a2] ? an?mn，?，a2?mn，a1?mn，即mn是a1, a2, ?, an的一個(gè)公倍數(shù).另一方面，對(duì)于a1, a2, ?, an的任何公倍數(shù)m，由定理2的推論及m2, ?, mn的定義，得

m2?m，m3?m，?，mn?m.即mn是a1, a2, ?, an最小的正的公倍數(shù).證畢

推論

若m是整數(shù)a1, a2, ?, an的公倍數(shù)，則[a1, a2, ?, an]?m.證明：留作習(xí)題.定理

4整數(shù)a1, a2, ?, an兩兩互素，即

(ai, aj)= 1，1 ? i, j ? n，i ? j 的充要條件是

[a1, a2, ?, an] = a1a2?an.(3)證明：必要性

因?yàn)?a1, a2)= 1，由定理2得到

[a1, a2] =

a1a2(a1,a2)= a1a2.由(a1, a3)=(a2, a3)= 1及前面的定理4推論得到

(a1a2, a3)= 1，由此及定理3得到

[a1, a2, a3] = [[a1, a2], a3] = [a1a2, a3] = a1a2a3.如此繼續(xù)下去，就得到式(3).充分性

用歸納法證明.當(dāng)n = 2時(shí)，式(3)成為[a1, a2] = a1a2.由定理2 a1a2 = [a1, a2] =即當(dāng)n = 2時(shí)，充分性成立.假設(shè)充分性當(dāng)n = k時(shí)成立，即

[a1, a2, ?, ak] = a1a2?ak ?(ai, aj)= 1，1 ? i, j ? k，i ? j.對(duì)于整數(shù)a1, a2, ?, ak, ak + 1，使用定理3中的記號(hào)，由定理3可知

[a1, a2, ?, ak, ak + 1] = [mk, ak + 1].(4)其中mk = [a1, a2, ?, ak].因此，如果

[a1, a2, ?, ak, ak + 1] = a1a2?akak + 1，那么，由此及式(4)得到

[a1, a2, ?, ak, ak + 1] = [mk, ak + 1] =即

mk(mk,ak?1)mkak?1(mk,ak?1)a1a2(a1,a2)?(a1, a2)= 1，= a1a2?akak + 1，= a1a2?ak，顯然mk ? a1a2?ak，(mk, ak + 1)? 1.所以若使上式成立，必是

(mk, ak + 1)= 1，(5)并且

mk = a1a2?ak.(6)由式(6)與式(5)推出

(ai, ak + 1)= 1，1 ? i ? k；

(7)由式(6)及歸納假設(shè)推出

(ai, aj)= 1，1 ? i, j ? k，i ? j.(8)綜合式(7)與式(8)，可知當(dāng)n = k ? 1時(shí)，充分性成立.由歸納法證明了充分性.證畢

定理4有許多應(yīng)用.例如，如果m1, m2, ?, mk是兩兩互素的整數(shù)，那么，要證明m = m1m2?mk整除某個(gè)整數(shù)Q，只需證明對(duì)于每個(gè)i，1 ? i ? k，都有mi?Q.這一點(diǎn)在實(shí)際計(jì)算中是很有用的.對(duì)于函數(shù)f(x)，要驗(yàn)證命題“m?f(n)，n?Z”是否成立，可以用第二節(jié)例5中的方法，驗(yàn)證“m?f(r)，r = 0, 1, ?, m ? 1”是否成立.這需要做m次除法.但是，若分別驗(yàn)證“mi?f(ri)，ri = 0, 1, ?, mi ? 1，1 ? i ? k”是否成立，則總共需要做m1 ? m2 ? ? ? mk次除法.后者的運(yùn)算次數(shù)顯然少于前者.例

1設(shè)a，b，c是正整數(shù)，證明：[a, b, c](ab, bc, ca)= abc.解：由定理3和定理2有

[a, b, c] = [[a, b], c] =由第三節(jié)定理5和定理2的推論，(ab, bc, ca)=(ab,(bc, ca))=(ab, c(a, b))

=(ab,abc)?(ab[a,b],abc)?ab([a,b],c).[a,b][a,b][a,b][a,b]c，([a,b],c)

(9)

(10)聯(lián)合式(9)與式(10)得到所需結(jié)論.例

2對(duì)于任意的整數(shù)a1, a2, ?, an及整數(shù)k，1 ? k ? n，證明：

[a1, a2, ?, an] = [[a1, ?, ak],[ak + 1, ?, an]].解：因?yàn)閇a1, a2, ?, an]是a1, ?, ak, ak + 1, ?, an的公倍數(shù)，所以由定理2推論，推出

[a1, ?, ak]?[a1, a2, ?, an]，[ak + 1, ?, an]?[a1, a2, ?, an]，再由定理3推論知

[[a1, ?, ak], [ak + 1, ?, an]]?[a1, a2, ?, an].另一方面，對(duì)于任意的ai（1 ? i ? n），顯然

ai?[[a1, ?, ak], [ak + 1, ?, an]]，所以由定理3推論可知

[a1, a2, ?, an]?[[a1, ?, ak], [ak + 1, ?, an]]，聯(lián)合上式與式(11)得證.例3

設(shè)a，b，c是正整數(shù)，證明：

[a, b, c][ab, bc, ca] = [a, b][b, c][c, a].解：由定理2推論2及例2，有

[a, b, c][ab, bc, ca] = [[a, b, c]ab, [a, b, c]bc, [a, b, c]ca] = [[a2b, ab2, abc], [abc, b2c, bc2], [a2c, abc, ac2]] = [a2b, ab2, abc, abc, b2c, bc2, a2c, abc, ac2] = [abc, a2b, a2c, b2c, b2a, c2a, c2b] 以及

(11)

[a, b][b, c][c, a] = [[a, b]b, [a, b]c][c, a] = [ab, b2, ac, bc][c, a] = [ab[c, a], b2[c, a], ac[c, a], bc[c, a]] = [abc, a2b, b2c, b2a, ac2, a2c, bc2, bca] = [abc, a2b, a2c, b2c, b2a, c2a, c2b]，由此得證.三、輾轉(zhuǎn)相除法

本節(jié)要介紹一個(gè)計(jì)算最大公約數(shù)的算法——輾轉(zhuǎn)相除法，又稱Euclid算法.它是數(shù)論中的一個(gè)重要方法，在其他數(shù)學(xué)分支中也有廣泛的應(yīng)用.1、定義

1下面的一組帶余數(shù)除法，稱為輾轉(zhuǎn)相除法.設(shè)a和b是整數(shù)，b ? 0，依次做帶余數(shù)除法：

a = bq1 ? r1，0 < r1 < |b|，b = r1q2 ? r2，0 < r2 < r1，? ?

rk ? 1 = rkqk + 1 ? rk + 1，0 < rk + 1 < rk，(1)

? ?

rn ? 2 = rn ? 1qn ? rn，0 < rn < rn-1，rn ? 1 = rnqn + 1.由于b是固定的，而且

|b| > r1 > r2 > ?，所以式(1)中只包含有限個(gè)等式.下面，我們要對(duì)式(1)所包含的等式的個(gè)數(shù)，即要做的帶余數(shù)除法的次數(shù)進(jìn)行估計(jì).2、引理

1用下面的方式定義Fibonacci數(shù)列{Fn}：

F1 = F2 = 1，F(xiàn)n = Fn ? 1 ? Fn ? 2，n ? 3，那么對(duì)于任意的整數(shù)n ? 3，有

Fn > ? n ? 2，(2)其中? =1?52.證明：容易驗(yàn)證

? 2 = ? ? 1.當(dāng)n = 3時(shí)，由

F3 = 2 >1?可知式(2)成立.假設(shè)式(2)對(duì)于所有的整數(shù)k ? n（n ? 3）成立，即

Fk > ? k ? 2，k ? n，則

Fn + 1 = Fn ? Fn ? 1 > ? n ? 2 ? ? n ? 3 = ? n ? 3(? ? 1)= ? n ? 3? 2 = ? n? 1，即當(dāng)k = n ? 1時(shí)式(2)也成立.由歸納法知式(2)對(duì)一切n ? 3成立.證畢.3、定理1(Lame)設(shè)a, b?N，a > b，使用在式(1)中的記號(hào)，則

n < 5log10b.證明：在式(1)中，rn ? 1，qn + 1 ? 2，qi ? 1（1 ? i ? n），因此

rn ? 1 = F2，rn ? 1 ? 2rn ? 2 = F3，52= ? rn ? 2 ? rn ? 1 ? rn ? F3 ? F2 = F4，? ?

b ? r1 ? r2 ? Fn + 1 ? Fn = Fn + 2，由此及式(2)得

b ? ?n =(1?即

log10b ? nlog101?這就是定理結(jié)論.證畢

4、定理

2使用式(1)中的記號(hào)，記

P0 = 1，P1 = q1，Pk = qkPk ? 1 ? Pk ? 2，k ? 2，Q0 = 0，Q1 = 1，Qk = qkQk ? 1 ? Qk ? 2，k ? 2，則

aQk ? bPk =(?1)k ? 1rk，k = 1, 2, ?, n.(3)證明：當(dāng)k = 1時(shí)，式(3)成立.當(dāng)k = 2時(shí)，有

Q2 = q2Q1 ? Q0 = q2，P2 = q2P1 ? P0 = q2q1 ? 1，此時(shí)由式(1)得到

aQ2 ? bP2 = aq2 ? b(q2q1 ? 1)=(a ? bq1)q2 ? b = r1q2 ? b = ?r2，即式(3)成立.假設(shè)對(duì)于k < m（1 ? m ? n）式(3)成立，由此假設(shè)及式(1)得到

aQm ? bPm= a(qmQm ? 1 ? Qm ? 2)? b(qmPm ? 1 ? Pm ? 2)

52)n，52?1n，5=(aQm ? 1 ? bPm ? 1)qm ?(aQm ? 2 ? bPm ? 2)=(?1)m ? 2rm ? 1qm ?(?1)m ? 3rm ? 2 =(?1)m ? 1(rm ? 2 ? rm ? 1qm)=(?1)m? 1rm，即式(3)當(dāng)k = m時(shí)也成立.定理由歸納法得證.證畢

5、定理

3使用式(1)中的記號(hào)，有rn =(a, b).證明：由第三節(jié)定理1，從式(1)可見

rn =(rn ? 1, rn)=(rn ? 2, rn ? 1)= ? =(r1, r2)=(b, r1)=(a, b).證畢.現(xiàn)在我們已經(jīng)知道，利用輾轉(zhuǎn)相除法可以求出整數(shù)x，y，使得

ax ? by =(a, b).(4)為此所需要的除法次數(shù)是O(log10b).但是如果只需要計(jì)算(a, b)而不需要求出使式(4)成立的整數(shù)x與y，則所需要的除法次數(shù)還可更少一些.例

1設(shè)a和b是正整數(shù)，那么只使用被2除的除法運(yùn)算和減法運(yùn)算就可以計(jì)算出(a, b).解：下面的四個(gè)基本事實(shí)給出了證明：(ⅰ)若a?b，則(a, b)= a；

(ⅱ)若a = 2?a1，2?|a1，b?2?b1，2?|b1，? ? ? ? 1，則

(a, b)= 2?(2? ? ?a1, b1)；

(ⅲ)若2?|a，b?2?b1，2?|b1，則(a, b)=(a, b1)；

a?b(ⅳ)若2?|a，2?|b，則(a,b)?(||,b).2在實(shí)際計(jì)算過程中，若再靈活運(yùn)用最大公約數(shù)的性質(zhì)（例如第三節(jié)定理4的推論），則可使得求最大公約數(shù)的過程更為簡(jiǎn)單.例

2用輾轉(zhuǎn)相除法求(125, 17)，以及x，y，使得

125x ? 17y =(125, 17).解：做輾轉(zhuǎn)相除法：

= 7?17 ? 6，q1 = 7，r1 = 6，= 2?6 ? 5，q2 = 2，r2 = 5，6 = 1?5 ? 1，q3 = 1，r3 = 1，5 = 5?1，q4 = 5.由定理4，(125, 17)= r3 = 1.利用定理2計(jì)算（n = 3）

P0 = 1，P1 = 7，P2 = 2?7 ? 1 = 15，P3 = 1?15 ? 7 = 22，Q0 = 0，Q1 = 1，Q2 = 2?1 ? 0 = 2，Q3 = 1?2 ? 1 = 3，取x =(?1)3 ? 1Q3 = 3，y =(?1)3P3 = ?22，則

125?3 ? 17?(?22)=(125, 17)= 1.例3

求(12345, 678).解：(12345, 678)=(12345, 339)=(12006, 339)=(6003, 339)=(5664, 339)=(177, 339)=(177, 162)=(177, 81)=(96, 81)=(3, 81)= 3.例

4在m個(gè)盒子中放若干個(gè)硬幣，然后以下述方式往這些盒子里繼續(xù)放硬幣：每一次在n（n < m）個(gè)盒子中各放一個(gè)硬幣.證明：若(m, n)= 1，那么無論開始時(shí)每個(gè)盒子中有多少硬幣，經(jīng)過若干次放硬幣后，總可使所有盒子含有同樣數(shù)量的硬幣.解：由于(m, n)= 1，所以存在整數(shù)x，y，使得mx ? ny = 1.因此對(duì)于任意的自然數(shù)k，有 ? m(?x ? kn)= n(km ? y)，這樣，當(dāng)k充分大時(shí)，總可找出正整數(shù)x0，y0，使得 ? mx0 = ny0.上式說明，如果放y0次（每次放n個(gè)），那么在使m個(gè)盒子中各放x0個(gè)后，還多出一個(gè)硬幣.把這個(gè)硬幣放入含硬幣最少的盒子中（這是可以做到的），就使它與含有最多硬幣的盒子所含硬幣數(shù)量之差減少1.因此經(jīng)過若干次放硬幣后，必可使所有盒子中的硬幣數(shù)目相同.四、小結(jié).五、作業(yè)

24頁(yè)ex5、ex6、ex7、ex8、ex11 25頁(yè)ex16 26頁(yè)ex29、ex36