初等數(shù)論ppt (1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、的素數(shù)是 2,3,5,7，用它們除100以內大于10的數(shù)，刪去所有能被它們整除的數(shù)，剩下的(含2,3,5, 7在內)就是100以內的所有素數(shù)．,表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個數(shù)就是100 以內的全部素數(shù)．再用這

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

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

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

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

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

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

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

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

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

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

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

41、-3b，-2b，-b，0，b，2b，3b，…它們將實數(shù)軸分成長度為b的區(qū)間，而a必定落在其中的一個區(qū)間中，因此存在一個整數(shù)q使得 qb≤a<(q+1)b我們令r=a-bq，則有a=bq+r，0≤r<b,(唯一性) 如果分別有整數(shù)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 利用帶余數(shù)除法，由a, b的值求q, r .,,,,如果允許b取負值，則要求,則a必在此序列的某兩項之間，,,存在性得證 ；下證唯一性.,當b為奇數(shù)時，②式中的等號不能成立，,當b為偶數(shù)時,s, t可以不唯一，舉例如下：,注：該例為簡化輾轉相除法求最大公約數(shù)提供了依據(jù)。,帶

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

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

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

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

47、75與90.,【定理2】設b是任一正整數(shù)，則（i)0與b的公因數(shù)就是,b的因數(shù)，反之， b的因數(shù)也就是0與b的公因數(shù)。,(ii)(0,b)=b,(a, 1) = 1， (a, a) = |a|； (a, b) = (b, a)；,【定理3】設 a = qb+r, 其中a,b,q,r都是整數(shù), 則 (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中最小的正數(shù)，則 。,推論1 設d是 的一個公約數(shù)，則 。,推論2 ( ) = |m|(

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

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

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

53、為快速一些。每次除得余數(shù)的絕對值不超過除數(shù)的一半，余數(shù)可以為負。,例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，則存在整數(shù) s, t，使得,證明：利用P4習題1-3的結論.,一方面，,另一方面，,特別地，,證：必要性的證明由定理2直接可得。,例 用輾轉相除法求(125, 17)，以及x，y，使得 125x ? 17y = (125, 17)。,解 做輾轉相除法：,,,本節(jié)最后

55、介紹另外一種求兩個整數(shù)最大公因數(shù)的方法，先給出下面幾個結果：,即當a與b是正整數(shù)時，只要使用被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é) 最小公倍數(shù),定

56、義1 ： 整數(shù)a1, a2, ?, ak的公共倍數(shù)稱為a1, a2, ?, ak的公倍數(shù)。a1, a2, ?, ak的正公倍數(shù)中的最小的一個叫做a1, a2, ?, ak的最小公倍數(shù)，記為[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 對任意的正整數(shù)a，b，有,推論1 兩個整數(shù)的任何公倍數(shù)可以被它們的最小公倍數(shù)整除。,推論2 設m，a，b是正整數(shù)，則[ma, mb] = m[a, b]。,定理3,注：把多個整數(shù)的公倍數(shù)化為兩個數(shù)的公倍數(shù)來計算。,推論 若m是a1, a2, ?, an的公倍數(shù)，則[a1, a2, ?, an]?m 。,定理4 整數(shù)a1, a2, ?,

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

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

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

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

62、整數(shù)。,證明 由引理1，任何大于1的整數(shù)n可以表示成式(2)的形式，因此，只需證明表示式(2)的唯一性。,假設pi（1 ? i ? k）與qj（1 ? j ? l）都是素數(shù)，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）是素數(shù), p1 < p2 < ? < pk

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

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

66、 ， ?i = max{?i, ?i}，1 ? i ? k。,推論2 ? 設正整數(shù)a與b的標準分解式是其中p1, p2, ?, pk 是互不相同的素數(shù)，?i，?i（1 ? i ? k）都是非負整數(shù)，則,例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是整數(shù)，證明： (ⅰ) (a, b)[a, b] = ab；,證明 為了敘述方便，不妨假定a，b，c是正整數(shù)。(ⅰ) 設,其中p1, p2, ?, pk是互不相同的素數(shù), ?i，?i(1 ? i ? k)都是非負整數(shù)。由定理1推論2 ?，有由此知,例2 設a，

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