第一篇：數論感想

本學期，我們分了專業方向，我選擇的是信息安全，有幸聽了數論基礎課。根據這一學期的所學所想，我做了簡單的總結。

其實，在分專業方向的時候，我對“信息安全”這個名詞并沒有什么概念，只是通過老師的介紹和查閱相關資料，才對這個方向有了淺顯的認識。在信息膨脹、全球化網絡化的今天，大量的數據信息在互聯網上傳播。因此，對于私密信息的保密處理顯得尤為重要。

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

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

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

最后，感謝老師這學期教給我們的一切知識、解題方法以及數學思想。我現在對信息安全這個分支的了解還只是停留在表面，以后的學習工作中還會向您請教，并在自己選擇的方向上作出一番成績。

第二篇：初等數論復習題

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

2、求[136,221,391]=

3、{-9/7}=；

4、當x不是整數時，{-x}=；

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

6、設2a與3b是正整數，則在1, 2, …,2 a中能被3b整除的整數有7、154440的標準分解式是；

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

9、2000！中末尾0的個數有。

10、求15！的標準分解式。

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

13、將17/105 寫成三個既約分數之和，它們的分母分別是3，5和7。

14、用數學歸納法證明：證明相鄰兩個偶數的乘積是8的倍數.15、證明：素數的個數無窮多。

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

第三篇：初等數論學習心得

《初等數論》學習心得

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

雖然之前就了解過一些關于數論的知識，但僅僅是皮毛上的了解，再說也不能系統地接觸到這門課程。不過，通過這幾節課的學習，我對初等數論》這門課程有了進一步的了解和認識。通過一個多星期的學習，我了解到這門課程主要研究的一些內容。

一、整除理論。引入整除、因數、倍數、質數與合數等基本概念。這一理論的主要成果有：唯一分解定理、裴蜀定理、歐幾里德的輾轉相除法、算術基本定理、素數個數無限證明。

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

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

四、不定方程。主要研究了低次代數曲線對應的不定方程，比如勾股方程的商高定理、佩爾方程的連分數求解。也包括了4次費馬方程的求解問題等等。

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

六、高斯函數。在數學領域，高斯函數在厄爾米特多項式的定義中起著重要作用。

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

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

第四篇：ZJZ數論練習(一)

ZJZ數論練習

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

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

素數.

第五篇：初等數論教案1

第二節 最大公因數與輾轉相除法

第三節 最小公倍數

教學目的：

1、掌握最大公因數與最小公倍數性質；

2、掌握輾轉相除法；

3、會求最大公因數與最小公倍數.教學重點：最大公因數與最小公倍數性質 教學難點：輾轉相除法 教學課時：6課時 教學過程

一、最大公因數

1、定義

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

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

(ai, a j)= 1，1 ? i, j ? k，i ? j，則稱a1, a2, ?, ak是兩兩互素的（或兩兩互質的）.顯然，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是素數，a是整數，則(p, a)= 1或p?a；(ⅴ)若a = bq ? r，則(a, b)=(b, r).證明：(ⅰ)??(ⅳ)留作習題.(ⅴ)由第一節定理1可知，如果d?a，d?b，則有d?r = a ? bq，反之，若d?b，d?r，則d?a = bq ? r.因此a與b的全體公約數的集合就是b與r的全體公約數的集合，這兩個集合中的最大正數當然相等，即(a, b)=(b, r).證畢

3、定理

2設a1, a2, ?, ak?Z，記

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

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

推論

1設d是a1, a2, ?, ak的一個公約數，則d?(a1, a2, ?, ak).注：這個推論對最大公約數的性質做了更深的刻劃：最大公約數不但是公約數中的最大的，而且是所有公約數的倍數.推論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的充要條件是存在整數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對于任意的整數a，b，c，下面的結論成立：(ⅰ)由b?ac及(a, b)= 1可以推出b?c；(ⅱ)由b?c，a?c及(a, b)= 1可以推出ab?c.證明

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

ax ? by = 1.因此

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

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

推論

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

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

推論

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

留作習題.6、定理

5對于任意的n個整數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的一個公約數.另一方面，對于a1, a2, ?, an的任何公約數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的公約數中的最大者，即dn =(a1, a2, ?, an).例

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

(21n ? 4, 14n ? 3)=(7n ? 1, 14n ? 3)=(7n ? 1, 1)= 1.注：一般地，若(x, y)= 1，那么，對于任意的整數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是既約分數.例

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)不能成立.注：這個例題的一般形式是： 設p是素數，a，b是整數，則

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

3設a，b是整數，且

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設a和b是正整數，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，此時

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

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

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

1、定義

1整數a1, a2, ?, ak的公共倍數稱為a1, a2, ?, ak的公倍數.a1, a2, ?, ak的正公倍數中的最小的一個叫做a1, a2, ?, ak的最小公倍數，記為[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|.證明

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

2對任意的正整數a，b，有

[a, b] =

ab(a,b).證明：設m是a和b的一個公倍數，那么存在整數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是某個整數.將上式代入式(1)得到

m =

abt.(a,b)

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

[a, b] =

ab(a,b).推論

1兩個整數的任何公倍數可以被它們的最小公倍數整除.證明

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

設m，a，b是正整數，則[ma, mb] = m[a, b].證明

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

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

4、定理

3對于任意的n個整數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的一個公倍數.另一方面，對于a1, a2, ?, an的任何公倍數m，由定理2的推論及m2, ?, mn的定義，得

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

推論

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

4整數a1, a2, ?, an兩兩互素，即

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

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

因為(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.如此繼續下去，就得到式(3).充分性

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

[a1, a2, ?, ak] = a1a2?ak ?(ai, aj)= 1，1 ? i, j ? k，i ? j.對于整數a1, a2, ?, ak, ak + 1，使用定理3中的記號，由定理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)及歸納假設推出

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

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

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

[a, b, c] = [[a, b], c] =由第三節定理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)聯合式(9)與式(10)得到所需結論.例

2對于任意的整數a1, a2, ?, an及整數k，1 ? k ? n，證明：

[a1, a2, ?, an] = [[a1, ?, ak],[ak + 1, ?, an]].解：因為[a1, a2, ?, an]是a1, ?, ak, ak + 1, ?, an的公倍數，所以由定理2推論，推出

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

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

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

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

設a，b，c是正整數，證明：

[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]，由此得證.三、輾轉相除法

本節要介紹一個計算最大公約數的算法——輾轉相除法，又稱Euclid算法.它是數論中的一個重要方法，在其他數學分支中也有廣泛的應用.1、定義

1下面的一組帶余數除法，稱為輾轉相除法.設a和b是整數，b ? 0，依次做帶余數除法：

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)中只包含有限個等式.下面，我們要對式(1)所包含的等式的個數，即要做的帶余數除法的次數進行估計.2、引理

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

F1 = F2 = 1，Fn = Fn ? 1 ? Fn ? 2，n ? 3，那么對于任意的整數n ? 3，有

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

? 2 = ? ? 1.當n = 3時，由

F3 = 2 >1?可知式(2)成立.假設式(2)對于所有的整數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，即當k = n ? 1時式(2)也成立.由歸納法知式(2)對一切n ? 3成立.證畢.3、定理1(Lame)設a, b?N，a > b，使用在式(1)中的記號，則

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?這就是定理結論.證畢

4、定理

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

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)證明：當k = 1時，式(3)成立.當k = 2時，有

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

aQ2 ? bP2 = aq2 ? b(q2q1 ? 1)=(a ? bq1)q2 ? b = r1q2 ? b = ?r2，即式(3)成立.假設對于k < m（1 ? m ? n）式(3)成立，由此假設及式(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)當k = m時也成立.定理由歸納法得證.證畢

5、定理

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

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

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

1設a和b是正整數，那么只使用被2除的除法運算和減法運算就可以計算出(a, b).解：下面的四個基本事實給出了證明：(ⅰ)若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在實際計算過程中，若再靈活運用最大公約數的性質（例如第三節定理4的推論），則可使得求最大公約數的過程更為簡單.例

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

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

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

24頁ex5、ex6、ex7、ex8、ex11 25頁ex16 26頁ex29、ex36