初等數論ppt (1)

1、初等數論,一、數論發(fā)展史 數論是研究整數性質的一門很古老的數學分支， 其初等部分是以整數的整除性為中心的，包括整除性、不定方程、同余式、連分數、素數（即整數）分布 以及數論函數等內容，統(tǒng)稱初等數論（Elementary Number Theory）。,初等數論的大部分內容早在古希臘歐幾里德的《 幾何原本》中就已出現。歐幾里得證明了素數有無窮多個，他還給出求兩個自然數的最大公約數的方法， 即所謂歐幾里得算法。我國古代在數論方面

2、亦有杰出之貢獻，現在一般數論書中的“中國剩余定理”正是我國古代《孫子算經》中的下卷第26題，我國稱之為“孫子定理”。,近代初等數論的發(fā)展得益于費馬、歐拉、拉格朗日、勒讓德和高斯等人的工作。1801年，高斯的《算術探究》是數論的劃時代杰作。 “數學是科學之王，數論是數學之王”。 -----高斯,由于自20世紀以來引進了抽象數學和高等分析的巧妙工具，數論得到進一步的發(fā)展，從而開闊了新的研究領域，出現了代數數論、解析數論、幾何

3、數論等 新分支。而且近年來初等數論在計算器科學、組合數學、密碼學、代數編碼、計算方法等領域內更得到了 廣泛的應用，無疑同時間促進著數論的發(fā)展。,二 幾個著名數論難題,初等數論是研究整數性質的一門學科，歷史上遺留下來沒有解決的大多數數論難題其問題本身容易搞懂，容易引起人的興趣，但是解決它們卻非常困難。,其中，非常著名的問題有：哥德巴赫猜想 ；費爾馬大定理 ；孿生素數問題 ；完全數問題等。,1742年,由德國中學教師哥德巴赫在教學中首

4、先發(fā)現的。1742年6月7日，哥德巴赫寫信給當時的大數學家歐拉,正式提出了以下的猜想： 一個大于6的偶數可以表示為不同的兩個質數之和。 陳景潤在1966年證明了“哥德巴赫猜想”的“一個大偶數可以表示為一個素數和一個不超過兩個素數的乘積之和”〔所謂的1+2〕，是篩法的光輝頂點，至今仍是“哥德巴赫猜想”的最好結果。,1、哥德巴赫猜想：,2、費爾馬大定理：,費馬是十七世紀最卓越的數學家之一，他在數學許多領域中都有極大的貢獻，因為他的

5、本行是專業(yè)的律師，世人冠以“業(yè)余王子”之美稱。在三百七十多年前的某一天，費馬正在閱讀一本古希臘數學家戴奧芬多斯的數學書時，突然心血來潮在書頁的空白處，寫下一個看起來很簡單的定理。,經過8年的努力，英國數學家 安德魯·懷爾斯 終于在1995年完成了該定理的證明。,3、孿生素數問題,存在無窮多個素數 p, 使得 p+2 也是素數。,究竟誰最早明確提出這一猜想已無法考證，但是1849年法國數學 Alphonse de Po

6、lignac（阿爾方·波利尼亞克 ） 提出猜想：對 于任何偶數 2k, 存在無窮多組以2k為間隔的素數。對于 k=1，這就是孿生素數猜想，因此人們有時把 Alphonse de Polignac 作為孿生素數猜想的提出者。不同的 k 對應的素數對的命名也很有趣，k=1 我們已經知道叫做孿生素數； k=2 (即間隔為4) 的素數對被稱為 cousin prime ；而 k=3 (即間隔為 6) 的素數對竟然被稱為 sexy pr

7、ime (不過別想歪了，之所以稱為 sexy prime 其實是因為 sex 正好是拉丁文中的 6。),1966年利用篩法 (sieve method) 陳景潤證明了： 存在無窮多個素數 p， 使得 p+2 要么是素數， 要么是兩個素數的乘積。 一般認為， 由于篩法本身的局限性， 這一結果在篩法范圍內很難被超越,2013年，5月14日，《自然》（Nature）雜志在線報道張益唐證明了“存在無窮多個之差小于7000萬的素數對”，這一研究隨

8、即被認為在孿生素數猜想這一終極數論問題上取得了重大突破，甚至有人認為其對學界的影響將超過陳景潤的“1+2”證明。,4、最完美的數——完全數問題,下一個具有同樣性質的數是28, 28=1+2+4+7+14.接著是496和8128.他們稱這類數為完美數. 歐幾里德在大約公元前350-300年間證明了:,注意以上談到的完全數都是偶完全數,至今仍然不知道有沒有奇完全數。,完美數又稱為完全數,最初是由畢達哥拉斯的信徒發(fā)現的,他們注意到

9、,數6有一個特性,它等于它自己的因子(不包括它自身)的和， 如：6=1+2+3.,三、我國古代數學的偉大成就,公元前100多年，漢朝人撰，是一部既談天體又談數學的天文歷算著作，主要討論蓋天說，提出了著名的“勾三股四弦五”這個勾股定理的一個特例。,1、周髀算經,2、孫子算經 約成書于四、五世紀，作者生平和編寫年代都不清楚?，F在傳本的《孫子算經》共三卷。卷上敘述算籌記數的縱橫相間制度和籌算乘除法則，卷中舉例說明籌算分數算法

10、和籌算開平方法。卷下第31題，可謂是后世“雞兔同籠”題的始祖，后來傳到日本，變成“鶴龜算”。,具有重大意義的是卷下第26題：今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？《孫子算經》不但提供了答案，而且還給出了解法。南宋大數學家秦九韶則進一步開創(chuàng)了對一次同余式理論的研究工作，推廣“物不知數”的問題。德國數學家高斯﹝1777-1855﹞于1801年出版的《算術探究》中明確地寫出了上述定理。1852年，

11、英國基督教士偉烈亞士將《孫子算經》中物不知數問題的解法傳到歐洲，1874年馬蒂生指出孫子的解法符合高斯的定理，從而在西方的數學史里將這一個定理稱為“中國剩余定理” 。,周髀算經,孫子算經,1983年在湖北省江陵縣張家山，出土了一批西漢初年，即呂后至文帝初年的竹簡，共千余支。經初步整理，其中有律令、《脈書》、《引書》、歷譜、日書等多種古代珍貴的文獻，還有一部數學著作，據寫在一支竹簡背面的字跡辨認，這部竹簡算書的書名叫《算

12、數書》。 《算數書》是中國現已發(fā)現的最古的一部算書，大約比現有傳本的《九章算術》還要早近二百年，而且《九章算術》是傳世抄本或刊書，《算數書》則是出土的竹筒算書，屬于更可珍貴的第一手資料，所以《算數書》引起了國內外學者的廣泛關注，目前正在被深入研究之中。,3、算數書,《數術記遺》相傳是漢末徐岳所作，亦有數學史家認為本書是北周甄鸞自著。 《數術記遺》把大數的名稱按不同的涵義排列三個不同的數列，另一部份是關于一個

13、幻方的清楚的說明，它成為數論中這一發(fā)現的最古的文字記載之一，書中至少提到了四種算盤，因此它是談到算盤的最古老的書籍。,4、數術記遺,算數書,數術記遺 中的算盤,根據研究，西漢的張蒼 、耿壽昌曾經做過增補和整理，其時大體已成定本。最后成書最遲在東漢前期。九章算術將書中的所有數學問題分為九大類，就是“九章”。 三國時期的劉徽為《九章》作注，加上自己心得體會，使其便于了解，可以流傳下來。 唐代的李淳風又重新做注(

14、656年)，作為《算數十經》之一，版刻印刷，作為通用教材。,5、九章算術,《九章算術》的出現，標志著我國古代數學體系的正式確立，當中有以下的一些特點：1.是一個應用數學體系，全書表述為應用問題集的形式；2.以算法為主要內容，全書以問、答、術構成，“術”是主要需闡述的內容；3.以算籌為工具。 《九章算術》取得了多方面的數學成就，包括：分數運算、比例問題、雙設法、一些面積、體積計算、一次方程組解法、負數概念的引入及負

15、數加減法則、開平方、開立方、一般二次方程解法等?！毒耪滤阈g》的思想方法對我國古代數學產生了巨大的影響。自隋唐之際，《九章算術》已傳入朝鮮、日本，現在更被譯成多種文字。,6、海島算經 《海島算經》由三國劉徽所著，最初是附于他所注的《九章算術》（263）之后，唐初開始單行，體例亦是以應用問題集的形式。 全書共9題，全是利用測量來計算高深廣遠的問題，首題測算海島的高、遠，故得名。《海島算經》是中國最早的一部測量

16、數學事著，亦為地圖學提供了數學基礎。,7、算經十書 　 唐代國子監(jiān)內設立算學館，置博士、助教指導學生學習數學，規(guī)定《周髀算經》、《九章算術》、《孫子算經》、《五曹算經》、《夏侯陽算經》、《張丘建算經》、《海島算經》、《五經算術》、《綴術》、《緝古算經》十部算經為課本，用以進行數學教育和考試，后世通稱為算經十書．算經十書是中國漢唐千余年間陸續(xù)出現的十部數學著作．北宋時期（1084年），曾將一部算經刊刻發(fā)行，這是世界上

17、最早的印刷本數學書．（此時《綴術》已經失傳，實際刊刻的只有九種）。,8、測圓海鏡《測圓海鏡》由中國金、元時期數學家 李冶所著，成書于1248年。全書共有12卷，170問。這是中國古代論述容圓的一部專箸，也是天元術的代表作?！稖y圓海鏡》所討論的問題大都是已知 勾股形而求其內切圓、旁切圓等的直徑一類的問題。在《測圓海鏡》問世之前，我國雖有文字代表未知數用以列方程和多項式的工作，但是沒有留下很有系統(tǒng)的記載。李冶在《測圓海鏡》中系統(tǒng)而概

18、栝地總結了天元術，使文詞代數開始演變成符號代數。 所謂天元術，就是設“天元一”為未知數，根據問題的已知條件，列出兩個相等的多項式，經相減后得出一個高次方式程，稱為天元開方式，這與現代設x為未知數列方程一樣。歐洲的數學家，到了16世紀以后才完全作到這一點。,測圓海鏡,費馬 [法]1601-1665，是數學史上最偉大的業(yè)余數學家，提出了費馬大、小定理；在坐標幾何，無窮小，概率論等方面有巨大貢獻。,哥德巴赫 1690-1764，

19、德國數學家；曾擔任中學教師，1725年到俄國，被選為彼得堡科學院院士.,希爾伯特[德]1862～1943，他領導的數學學派是19世紀末20世紀初數學界的一面旗幟，希爾伯特被稱為“數學界的無冕之王”。著《數論報告》、《幾何基礎》、《線性積分方程一般理論基礎》.,華羅庚1910—1985，是中國解析數論、矩陣幾何學、典型群、自安函數論等多方面研究的創(chuàng)始人和開拓者。以華氏命名的數學科研成果很多。被列為芝加哥科學技術博物

20、館中當今世界88位數學偉人之一。,陳景潤1933－1996，主要研究解析數論，他研究哥德巴赫猜想和其他數論問題的成就，至今仍然在世界上遙遙領先。其成果也被稱之為陳氏定理。,王元1930－50年代至60年代初，首先在中國將篩法用于哥德巴赫猜想研究，并證明了命題3+4，1957年又證明2+3，這是中國學者首次在此研究領域躍居世界領先地位.,數論是以嚴格和簡潔著稱，內容既豐富又深刻。我將會介紹數論中最基本的概念和理論，希望大家能對這

21、門學問產生興趣，并且對中小學時代學習過的一些基本概念，例如整除性、最大公因子、最小公倍數、輾轉相除法等，有較深入的了解。,第一章 整數的整除性第一節(jié) 整除的概念,一、基本概念 1、自然數、整數 2、正整數、負整數 3、奇數、偶數一個性質： 整數+整數=整數 整數-整數=整數 整數*整數=整數,,,關于奇數和偶數性質：1.奇數+奇數=偶數； 奇數+偶數=奇數； 偶數+偶數=偶數；2

22、.兩個數之和是奇（偶）數，則這兩個數的奇偶性相反（同）。3.若干個整數之和為奇數，則這些數中必有奇數，且奇數的個數為奇數個；若干個整數之和為偶數，則這些數中若有奇數，奇數的個數必為偶數個。,關于奇數和偶數性質：4.奇數×奇數=奇數； 奇數×偶數=偶數； 偶數×偶數=偶數；5.若干個整數之積為奇數，則這些數必為奇數；若干個整數之積為偶數，則這些數中至少有一個是偶數。6.若a是整數，則|a| 與

23、a 有相同的奇偶性。7.若a ，b 是整數，則a +b 與a -b 奇偶性相同。,例1 在1,2,3，? ，1998,1999這1999個數的前面任意添加一個正號或負號，問它們的代數和是奇數還是偶數？例2 設n 為奇數， 是1,2， ? ，n 的任意一個排列，證明 必是偶

24、數。,例3 將正方形ABCD分割成 個相等的小方格（n 是正整數），把相對的頂點A,C染成紅色，B,D染成藍色，其他交點任意染成紅藍兩色中的一種顏色，證明：恰有三個頂點同顏色的小方格的數目必是偶數。,例4 設正整數d 不等于2,5,13，證明集合 中可以找到兩個數a ，b ，使得a b-1 不是完全平方數。,,二、整除,1、定義：設a，b是整數，b≠0。如果存在一個整數q使得

25、等式： a=bq 成立，則稱b能整除a或a能被b整除，記b∣a；如果這樣的q不存在，則稱b不能整除a，記為b a。,注：顯然每個非零整數a都有約數 ?1，?a，稱這四個數為a的平凡約數，a的另外的約數稱為非平凡約數。,,,素數：定義 設整數n≠0，±1.如果除了顯然因數±1，±n以外，n沒有其他因數，那么，n叫做素數（或質數或不可約數），否則，n叫做合數.

26、規(guī)定：若沒有特殊說明，素數總是指正整數，通常寫成p或 p1， p2，…， pn. 例 整數2，3，5，7都是素數，而整數4，6，8，10，21都是合數.,2、整除的性質,設a，b，c是整數 （1）a ∣ a （2）如果 a ∣ b ， b ∣ c ，則a ∣ c （3）如果 a ∣b ， a ∣c ,則對任意整數m，n 有a ∣mb+cn.,（4）如果a ∣ c ，則對任何整數b ， a ∣ b c.

27、 （5）若（ a，b ）=1，且a ∣ b c，則a ∣ c （6）若（ a，b ）=1，且a ∣c， b ∣ c則a b ∣ c （7）若（ a，b ）=1，且a b ∣c，則a ∣c， b ∣ c,（8）若在等式 中，除某一項外，其余各項都能被c整除，則這一項也能被c整除。,（3）素數判定法則：設n是一個正整數，如果對所有的素數p≤ ，

28、都有p n，則n一定是素數.,（1）設p為素數 ，若p ∣ b a ，則p ∣a 或 p ∣b .（2） p|a 或 (p，a)=1 . p ? ? p?a,常用結論：,（4） 任何大于1的整數a都至少有一個素約數。,推論 任何大于1的合數a必有一個不超過 的素約數。,,,,例6 證明：121 ，n?Z。,,10以內

29、的素數是 2,3,5,7，用它們除100以內大于10的數，刪去所有能被它們整除的數，剩下的(含2,3,5, 7在內)就是100以內的所有素數．,表19.2 篩 法,最后剩下2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89和97 . 這25個數就是100 以內的全部素數．再用這

30、25個素數除1002＝10000以內大于100的數，刪去所有能被它們整除的數，可以得到10000以內的所有素數．重復這個做法可以得到任意給定的正整數以內的所有素數．這個方法叫做埃拉托斯特尼(Eratosthene)篩法．,人們一直在尋找更大的素數。近代已知的最大素數差不多總是形如 2n – 1 的數。當n是合數時， 2n – 1 一定是合數．設n=ab，其中a>1,b>1，有,當n為素數時, 22 – 1=3, 23

31、 – 1＝7, 24 – 1＝31, 27 – 1=127 都是素數, 而 211 – 1 = 2047 = 23 x 89 是合數．,設P為素數, 稱如 2p–1的數為梅森(Matin Merdenne)數.到 2002年為止找到的最大梅森素數是213466917 – 1, 這個數有 4百萬位．,可除性判別方法,判別方法1：（整數被2整除） 如果一個整數的末尾數字能被2整除，則該數能被2整除。即：若2∣a0，

32、，則2 ∣N.判別方法2：（整數被5整除） 如果一個整數的末尾數字能被5整除，則該數能被5整除。即：若5∣a0，，則5∣N.判別方法3：（整數被3整除） 如果一個整數的各位數字之和能被3整除，則該數能被3整除。即：若3∣an+an-1+…a1+a0，，則3 ∣N.判別方法4：（整數被9整除）如果一個整數的各位數字之和能被9整除，則該數能被9整除。即：若9∣an+an-1+…a1+a0，，則9 ∣

33、N.,例6 有一個自然數乘以9后，得到一個僅由數字1組成的多位數，求這個自然數最小為多少？,12345679,判別方法5：（整數被4或25整除） 如果一個數的末兩位數能被4或25整除，那么，這個數就一定能被4或25整除．判別方法6：（整數被8或125整除） 如果一個數的末三位數能被8或125整除，那么，這個數就一定能被8或125整除．,可除性判別方法,可除性判別方法,判別方法7：（整數被11整除）

34、(1) 如果一個整數將其最后三位數字去掉后得到的位數少3位的新整數與該整數末三位數字組成的數之差能被11整除，則該整數能11整除.即如果 ，則11︱N.(2)把一個數由右邊向左邊數,將奇位上的數字與偶位上的數字分別加起來,再求它們的差,如果這個差是11的倍數(包括0),那么,原來這個數就一定能被11整除。例如：判斷491678能不能被11整除。

35、 →奇位數字的和9+6+8=23 ，→偶位數位的和4+1+7=12  ，23-12=11因此,491678能被11整除。這種方法叫“奇偶位差法”。,可除性判別方法,判別方法8：（整數被13整除） 如果一個整數將其最后三位數字去掉后得到的位數少3位的新整數與該整數末三位數字組成的數之差能被13整除，則該整數能13整除.即如果

36、 ， 則13︱N.判別方法9：（整數被7整除）（適用于數字位數少時）一個數割去末位數字，再從留下來的數中減去所割去數字的2倍，這樣，一次次減下去，如果最后的結果是7的倍數（包括0），那么，原來的這個數就一定能被7整除．例如：判斷133是否7的倍數的過程如下：13－3×2＝7，所以133是7的倍數,例7 設a，b，c是三個互不相等的正整數，求證：三數中至少有一個能被10整除。,例8 設n 為自然數，

37、求證：能被1985整除。,例9 設p為大于5的素數 ，求證：240︱,例10 p ? 5是素數 ，且2 p +1也是素數，證明： 4 p +1必是合數。,例11 請確定最小正整數A，其末位數為6，若將末位的6移至首位，其余數字不變，則為原數的4倍。,,例12 一個正整數，如果用7進位制表示，則為 ，如果用5進位制表示為 ，請用10進位制表示此數。,,例13 證明：對任何自然數n 和k

38、 ，數都不能分解成若干個連續(xù)的自然數之積。,例14 設r是正奇數，證明：對任意的正整數n，有,例15 設A = { }是n的所有約數的集合，則B = { } 也是n的所有約數的集合。,例16 以d(n)表示n的正約數的個數， 例如： d(1) = 1，d(2) = 2，d

39、(3) = 2， d(4) = 3，? 。 問：d(1) ? d(2) ? ? ? d(1997)是否為偶數？,例17 設凸2n邊形M的頂點是 ，點O在M的內部，用1, 2, ?, 2n將M的2n條邊分別編號，又將 也同樣進行編號，若把這些編號作為相應的線段的長度，證明

40、：無論怎么編號，都不能使得三角形 的周長都相等。,第二節(jié) 帶余除法,第二節(jié) 帶余除法,可以看出：b整除a的充要條件是 r=0。,設a，b是兩個整數，其中b>0.則存在唯一的整數q，r使得a=bq+r，0≤r<b. 證明（存在性）考慮一個整數序列 …，

41、-3b，-2b，-b，0，b，2b，3b，…它們將實數軸分成長度為b的區(qū)間，而a必定落在其中的一個區(qū)間中，因此存在一個整數q使得 qb≤a<(q+1)b我們令r=a-bq，則有a=bq+r，0≤r<b,(唯一性) 如果分別有整數q，r和q1，r1滿足（2），則 a= bq+r， 0≤r<b， a= bq1+r1，0≤r1<b兩式相減，我

42、們有 b(q-q1) =-(r-r1)當q≠q1左邊的絕對值大于等于b，而右邊的絕對值小于b，這是不可能的.故q=q1，r=r1.,例1 利用帶余數除法，由a, b的值求q, r .,,,,如果允許b取負值，則要求,則a必在此序列的某兩項之間，,,存在性得證 ；下證唯一性.,當b為奇數時，②式中的等號不能成立，,當b為偶數時,s, t可以不唯一，舉例如下：,注：該例為簡化輾轉相除法求最大公約數提供了依據。,帶

43、余數除法的應用舉例,例2 證明：形如3n-1的數不是平方數。,例3、任意給出的5個整數中，必有3個數之和被3整除。,證明：,由帶余除法有,例6 設a，b，x，y是整數，k和m是正整數，并且則ax ? by 和 ab 被 m 除的余數分別與 和 被m除的余數相同。特別地， 與 被m除的余數相同。,例7 設

44、 為不全為零的整數，以 表示集合A = { y | y = ， ，1 ? i ? n } 中的最小正數，則 對于任何 y?A， ；特別地， 1 ? i ? n。,例8 設

45、 ?Z，f(x) = ，已知f(0) 與f(1)都不是3的倍數，證明：若方程f(x) = 0有整數解，則3?f(?1) = 。,例9 證明：若a被9除的余數是3，4，5或6，則方程

46、 沒有整數解。,第三節(jié) 最大公約數,如果 ，1 ? i, j ? n ，i ? j，則稱 是兩兩互素的（或兩兩互質的）。,例1 已知兩個自然數的和為165，它們的最大公約數 為15，求這兩個數。,15與150，或30與135，或45與120，或60與105，或

47、75與90.,【定理2】設b是任一正整數，則（i)0與b的公因數就是,b的因數，反之， b的因數也就是0與b的公因數。,(ii)(0,b)=b,(a, 1) = 1， (a, a) = |a|； (a, b) = (b, a)；,【定理3】設 a = qb+r, 其中a,b,q,r都是整數, 則 (a，b) = (b，r)．,證：只需證 a與b 和 b與r 有相同的公因子．設d是a與b的公因子, 即d|a且d

48、|b．注意到 r=a-qb, 由 性質有 d|r. 從而, d|b且 d|r, 即 d也是 b與r 的公因子．反之一樣, 設 d 是 b與 r的公因子, 即 dlb且 dlr．注意到, a=qb+r, 故有 d|a . 從而, d|a且 d|b，即 d也是a與b的公因子．,【定理4】 設 ，記A = { y | y =

49、 ，? ? i ? k }。如果 是集合A中最小的正數，則 。,推論1 設d是 的一個公約數，則 。,推論2 ( ) = |m|(

50、 )。,推論3 記? = ( )，則= 1，特別地, = 1,【定理5】( ) = 1的充要條件是存在整數 ，使得

51、 = 1。,【定理6】若 (a, b) = 1，則(a, bc) = (a, c)。,推論 若 (a, ) = 1，1 ? i ? n，則(a, ) = 1。,【定理7】,例1 證明：若n是正整數，則 是既約分數。,例2 設a，b是整數，且9? ，則3?(a, b

52、)。,例3,設a和b是正整數，b > 2，則 。,第四節(jié) 輾轉相除法,定義 下面的一組帶余數除法，稱為輾轉相除法。,例1 求下面各組數的最大公因數。,解：,1859 1573,,,1,1573,,286,5,1430,143,2,286,,0,注：亦可通過分解因數的方法求最大公因數.,補充說明：利用§1.1習題4的結論，可以使得輾轉相除法求最大公因數更

53、為快速一些。每次除得余數的絕對值不超過除數的一半，余數可以為負。,例2 求（76501，9719）.,76501 9719,,,8,,77752,1251,8,10008,289,4,1156,,95,3,285,4,24,96,,1,4,4,0,=1.,例3 利用輾轉相除法計算 (27090, 21672, 11352).,27090 21672 11352,,,2,22704,（2）,22704,,4386,1032,

54、11,11352,4,4128,0,,258,4,1032,0,所以，(27090, 21672, 11352)=258.,定理2 設a，b不全為0，則存在整數 s, t，使得,證明：利用P4習題1-3的結論.,一方面，,另一方面，,特別地，,證：必要性的證明由定理2直接可得。,例 用輾轉相除法求(125, 17)，以及x，y，使得 125x ? 17y = (125, 17)。,解 做輾轉相除法：,,,本節(jié)最后

55、介紹另外一種求兩個整數最大公因數的方法，先給出下面幾個結果：,即當a與b是正整數時，只要使用被2除的除法運算和減法運算就可以計算出(a,b),例1、求（12345,678）,解： （12345,678）=（12345，339）,=（12006,339）,=（6003,339）,=（5664,339）,=（177,339）,=（177,162）,=（177，81）,=（96,81）,=（3,81）=3,,第五節(jié) 最小公倍數,定

56、義1 ： 整數a1, a2, ?, ak的公共倍數稱為a1, a2, ?, ak的公倍數。a1, a2, ?, ak的正公倍數中的最小的一個叫做a1, a2, ?, ak的最小公倍數，記為[a1, a2, ?, ak].,定理1： 下面的等式成立：(ⅰ) [a, 1] = |a|，[a, a] = |a|；(ⅱ) [a, b] = [b, a]；(ⅲ) [a1, a2, ?, ak] = [|a1|, |a2| ?,

57、|ak|]；(ⅳ) 若a?b，則[a, b] = |b|。,定理2 對任意的正整數a，b，有,推論1 兩個整數的任何公倍數可以被它們的最小公倍數整除。,推論2 設m，a，b是正整數，則[ma, mb] = m[a, b]。,定理3,注：把多個整數的公倍數化為兩個數的公倍數來計算。,推論 若m是a1, a2, ?, an的公倍數，則[a1, a2, ?, an]?m 。,定理4 整數a1, a2, ?,

58、an兩兩互素，即(ai, aj) = 1，1 ? i, j ? n，i ? j 的充要條件是,[a1, a2, ?, an] = a1a2?an .,例3 設a，b，c是正整數，證明 [a, b, c](ab, bc, ca) = abc 。,證：[a, b, c] = [[a, b], c] =,(ab, bc, ca) = (ab, (bc, ca)) = (ab, c(a, b)),代入即得證.,例4 對于任意的整數 及

59、整數k，1 ? k ? n，證明：[ ] = [[ ],[ ]],例5 設a，b，c是正整數，證明：[a, b, c][ab, bc, ca] = [a, b][b, c][c, a]。,第六節(jié) 算術基本定理,證明 當n = 2時，結論顯

60、然成立。,由于2 ? d ? k，由歸納假定知存在素數q1, q2, ?, ql，使得d = q1q2?ql，從而k ? 1 = pq1q2?ql。,假設對于2 ? n ? k，式(1)成立，下證式(1)對于n = k ? 1也成立，,從而由歸納法推出式(1)對任何大于1的整數n成立。,如果k ? 1是素數，式(1)顯然成立。,若k ? 1是合數，則存在素數p與整數d，使得k ? 1 = pd。,引理1 任何大于1的正整數n可以寫

61、成素數之積，即n = p1p2?pm， (1)其中pi（1 ? i ? m）是素數。,定理1(算術基本定理) 任何大于1的整數n可以唯一地表示成 ， (2)其中p1, p2, ?, pk是素數，p1 < p2 < ? < pk，?1, ?2, ?, ?k是正

62、整數。,證明 由引理1，任何大于1的整數n可以表示成式(2)的形式，因此，只需證明表示式(2)的唯一性。,假設pi（1 ? i ? k）與qj（1 ? j ? l）都是素數，p1 ? p2 ? ? ? pk，q1 ? q2 ? ? ? ql， (3)并且 n = p1p2?pk = q1q2?ql ， (4)則由第三節(jié)定理4推論1，必有某個qj（1 ?

63、j ? l），使得p1?qj，所以p1 = qj；又有某個pi（1 ? i ? k），使得q1?pi，所以q1 = pi。,于是，由式(3)可知p1 = q1，從而由式(4)得到p2?pk = q2?ql 。重復上述這一過程，得到k = l，pi = qi ，1 ? i ? k 。,定義1 使用定理1中的記號，稱 是n的標準分解式, 其中pi（1 ? i ? k）是素數, p1 < p2 < ? < pk

64、，? i（1 ? i ? k）是正整數.,推論1 使用式(2)中的記號，有(ⅰ) n的正因數d必有形 ， ?i?Z，0 ? ?i ? ? i，1 ? i ? k；(ⅱ) n的正倍數m必有形式 M?N，?i?N，?i ? ? i，1 ? i ? k。,推論2 設正整數a與b的標準分解式是

65、其中pi(1 ? i ? k)，qi(1 ? i ? l)與ri(1 ? i ? s)是兩兩不相同的素數，?i，?i(1 ? i ? k)，?i(1 ? i ? l)與?i(1 ? i ? s)都是非負整數，則,(a, b) = ， ?i = min{?i, ?i}，1 ? i ? k，[a, b] =

66、 ， ?i = max{?i, ?i}，1 ? i ? k。,推論2 ? 設正整數a與b的標準分解式是其中p1, p2, ?, pk 是互不相同的素數，?i，?i（1 ? i ? k）都是非負整數，則,例1 寫出51480的標準分解式。,解 我們有51480 = 2?25740 = 22 ? 12870 = 23 ? 6435= 23 ? 5 ? 128

67、7 = 23 ? 5 ? 3 ? 429= 23 ? 5 ? 32 ? 143 = 23 ? 32 ? 5 ? 11 ? 13.,例2 設a，b，c是整數，證明： (ⅰ) (a, b)[a, b] = ab；,證明 為了敘述方便，不妨假定a，b，c是正整數。(ⅰ) 設,其中p1, p2, ?, pk是互不相同的素數, ?i，?i(1 ? i ? k)都是非負整數。由定理1推論2 ?，有由此知,例2 設a，

68、b，c是整數，證明： (ⅱ) (a, [b, c]) = [(a, b), (a, c)]。,(ⅱ) 設其中p1, p2, ?, pk是互不相同的素數, ?i，?i，?i(1 ? i ? k)都是非負整數. 由定理1推論2 ?, 有 其中，對于1 ? i ? k，有 ?i = min{?i, max{?i, ?i}}，,?i = max{min{?i, ?i}, min{?i, ?i}}，不妨設?i ? ?i，