大學(xué)數(shù)學(xué)---初等數(shù)論 (2)

1、大學(xué)數(shù)學(xué),初等數(shù)論線性代數(shù)射影幾何概率統(tǒng)計(jì),初等數(shù)論,趙爭(zhēng)Email:zhaoz@jssvc.edu.cn,序言,數(shù)論是研究整數(shù)性質(zhì)的一門(mén)很古老的數(shù)學(xué)分支， 其初等部分是以整數(shù)的整除性為中心的，包括整除性、不定方程、同余式、連分?jǐn)?shù)、素?cái)?shù)（即整數(shù)）分布 以及數(shù)論函數(shù)等內(nèi)容，統(tǒng)稱(chēng)初等數(shù)論（Elementary Number Theory）。,初等數(shù)論的大部份內(nèi)容早在古希臘歐幾里德的《 幾何原本》中就已出現(xiàn)。歐幾里得證明了素?cái)?shù)有無(wú)窮多

2、個(gè)，他還給出求兩個(gè)自然數(shù)的最大公約數(shù)的方法， 即所謂歐幾里得算法。我國(guó)古代在數(shù)論方面亦有杰出之貢獻(xiàn)，現(xiàn)在一般數(shù)論書(shū)中的“中國(guó)剩余定理”正是我國(guó)古代《孫子算經(jīng)》中的下卷第26題，我國(guó)稱(chēng)之為“孫子定理”。,近代初等數(shù)論的發(fā)展得益于費(fèi)馬、歐拉、拉格朗日、勒讓德和高斯等人的工作。1801年，高斯的《算術(shù)探究》是數(shù)論的劃時(shí)代杰作。 “數(shù)學(xué)是科學(xué)之王，數(shù)論是數(shù)學(xué)之王”。 -----高斯,,歐幾里德

3、 高斯,費(fèi)馬,歐拉,拉格朗日 畢達(dá)格拉斯,由于自20世紀(jì)以來(lái)引進(jìn)了抽象數(shù)學(xué)和高等分析的巧妙工具，數(shù)論得到進(jìn)一步的發(fā)展，從而開(kāi)闊了新的研究領(lǐng)域，出現(xiàn)了代數(shù)數(shù)論、解析數(shù)論、幾何數(shù)論等 新分支。而且近年來(lái)初等數(shù)論在計(jì)算器科學(xué)、組合數(shù)學(xué)、密碼學(xué)、代數(shù)編碼、計(jì)算方法等領(lǐng)域內(nèi)更得到了 廣泛的應(yīng)用，無(wú)疑同時(shí)間促進(jìn)著數(shù)論的發(fā)展。,數(shù)論是以嚴(yán)格和簡(jiǎn)潔著稱(chēng)，內(nèi)容既豐富又深刻。我將會(huì)介紹數(shù)論中最基本的概念和理論，希

4、望大家能對(duì)這門(mén)學(xué)問(wèn)產(chǎn)生興趣，并且對(duì)中小學(xué)時(shí)代學(xué)習(xí)過(guò)的一些基本概念，例如整除性、最大公因子、最小公倍數(shù)、輾轉(zhuǎn)相除法等，有較深入的了解。,第一章 整數(shù)的整除性§1.1整除的概念,一、基本概念 1、自然數(shù)、整數(shù) 2、正整數(shù)、負(fù)整數(shù) 3、奇數(shù)、偶數(shù)一個(gè)性質(zhì)： 整數(shù)+整數(shù)=整數(shù) 整數(shù)-整數(shù)=整數(shù) 整數(shù)*整數(shù)=整數(shù),二、整除,1、定義：設(shè)a，b是整數(shù)，b≠0。如果存在一個(gè)整數(shù)q使得等式：

5、 a=bq 成立，則稱(chēng)b能整除a或a能被b整除，記作 b∣a；如果這樣的q不存在，則稱(chēng)b不能整除a。,2、整除的性質(zhì),（1）如果b∣a， c∣b，則c∣a. （2）如果b∣a，則cb∣ca. （3）如果c∣a，則對(duì)任何整數(shù)d， c∣da. （4）如果c∣a， c∣b，則對(duì)任意整數(shù)m，n，有 c∣ma+nb. （5）如果a∣b， b∣a，則a=&#

6、177;b.,3、質(zhì)數(shù)、合數(shù),質(zhì)數(shù)（素?cái)?shù)）合數(shù)質(zhì)因數(shù)分解質(zhì)因數(shù)算術(shù)基本定理,4、帶余除法,定理： 設(shè)a，b是兩個(gè)整數(shù)，其中b＞0，則存在兩個(gè)唯一的整數(shù)q及r，使得 a=bq+r，0≤r＜b 成立.我們稱(chēng)r是b除a的余數(shù)。 可以看出：b整除a的充要條件是r=0。,§1.2最大公因數(shù)和輾轉(zhuǎn)相除法,一、最大公因數(shù) 1、定義 設(shè)a1，a2，…，an是n個(gè)不全為零的

7、整數(shù)，若整數(shù)d是它們之中每一個(gè)的因數(shù)，那么d就叫做a1，a2，…，an的一個(gè)公因數(shù)。整數(shù)的公因數(shù)中最大的一個(gè)叫做它們的最大公因數(shù)，記作 （a1，a2，…，an） 。,2、互質(zhì),設(shè)a1，a2，…，an是n個(gè)不全為零的整數(shù)，若 （a1，a2，…，an） =1， 則稱(chēng)a1，a2，…，an 是互質(zhì)的。注：三個(gè)互質(zhì)比一定兩兩互質(zhì)。比如（3，4，6）=1，但（3，6）=3，（4，6）=2.,3、最大公因數(shù)的性質(zhì),（1）當(dāng)

8、b∣a時(shí)，（a，b）=b.（2）a，b的一切公因數(shù)都是（a，b）的因數(shù).（3）若a，b是正整數(shù)，m是任一正整數(shù)，則有 （am，bm）=（a，b）m.（4）若（a，b）=1，c為任一正整數(shù)，則有 （ac，b）=（c，b）（5）若（a，b）=1， b∣ac，則有b∣c.（6）若a，b，c是任意三個(gè)正整數(shù)，則（a，b）=d的充分必要條件是：,4、輾轉(zhuǎn)相除法,一個(gè)推論,若a，b是正整

9、數(shù)，且（a，b）=d，則必存在整數(shù)m和n，使得 d=ma+nb注：證明可由帶余除法逆向代入證得。,例1：求（735000，238948）.,解：因?yàn)?35000=238948×3+18156， 238948=18156×13+2920 18156=2920×6+636 2920=636×

10、;4+376 636=376×1+260 376=260×1+116 260=116×2+28 116=28×4+4 28=4×7所以（735000，238948）=4.,例2：求（2605，-5125）.,解：因?yàn)?125=2605

11、15;1+2520， 2605=2520×1+85 2520=85×29+55 85=55×1+30 55=30×1+25 30=25×1+5 25=5×5所以（2605，-5125）=5.,例3：求（2605

12、，3245，7250）.,解：先求2065和3245的最大公因數(shù)。 因?yàn)?245=2605×1+1180， 2605=1180×1+885 1180=885×1+295 885=295×3 所以（2605，3245）=295. 再求295與7250的最大公因數(shù)。 725

13、0=295×24+170， 295=170×1+125 170=125×1+45 125=45×2+35 45=35×1+10 35=10×3+5 10=5×2所以（2605，3245，7250）

14、= （295，7250）=5.,練習(xí),求（125，610）.求（51306，1224）.求（538，244，555）.,§1.3最小公倍數(shù)一、定義,二、最小公倍數(shù)的性質(zhì),1、定理：,例1：求[3468,24871].,解：由輾轉(zhuǎn)相除法得： （3468，24871）=17.所以[3468,24871]= =5073684.,例2：求[128，234，524].,習(xí)題,1

15、、求[21，35].2、求[123，321].3、求[125，725，1125，2015].,§1.4整數(shù)可除性的檢驗(yàn),一、整數(shù)的表示1、十進(jìn)制的整數(shù)的意義：各位數(shù)字的加權(quán)和。2、一般表示：,進(jìn)位制,進(jìn)位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示不同的數(shù)值?？墒褂脭?shù)字符號(hào)的個(gè)數(shù)稱(chēng)為基數(shù)，基數(shù)為n，即可稱(chēng)n進(jìn)位制，簡(jiǎn)稱(chēng)n進(jìn)制。現(xiàn)在最常用的是十進(jìn)制，通常使用10個(gè)阿拉伯?dāng)?shù)字0-9進(jìn)行記數(shù)。,進(jìn)位制,常見(jiàn)的進(jìn)位制：

16、二進(jìn)制廣泛用于計(jì)算機(jī) 三進(jìn)制用于軍隊(duì)編制 十進(jìn)制最常用 十二進(jìn)制時(shí)辰、月份、一打物品 十六進(jìn)制廣泛用于計(jì)算機(jī) 六十進(jìn)制秒、分,角度,二、可除性判別方法,判別方法1：（整數(shù)被2整除） 如果一個(gè)整數(shù)的末尾數(shù)字能被2整除，則該數(shù)能被2整除。即：若2∣a0，，則2 ∣N.判別方法2：（整數(shù)被5整除） 如果一個(gè)整數(shù)的末尾數(shù)字能被5整除，則該數(shù)能被5整除。即：若5∣a0，，則5∣N.判別方法3：（整數(shù)被3

17、整除） 如果一個(gè)整數(shù)的各位數(shù)字之和能被3整除，則該數(shù)能被3整除。即：若3∣an+an-1+…a1+a0，，則3 ∣N.判別方法4：（整數(shù)被9整除）如果一個(gè)整數(shù)的各位數(shù)字之和能被9整除，則該數(shù)能被9整除。即：若9∣an+an-1+…a1+a0，，則9 ∣N.,二、可除性判別方法,判別方法5：（整數(shù)被11整除） 如果一個(gè)整數(shù)將其最后三位數(shù)字去掉后得到的位數(shù)少3位的新整數(shù)與該整數(shù)末三位數(shù)字組成的數(shù)之差能被11整除

18、，則該整數(shù)能11整除.即如果 ，則11︱N.判別方法6：（整數(shù)被13整除） 如果一個(gè)整數(shù)將其最后三位數(shù)字去掉后得到的位數(shù)少3位的新整數(shù)與該整數(shù)末三位數(shù)字組成的數(shù)之差能被11整除，則該整數(shù)能11整除.即如果 ，則13︱N.,第二章 不定方程,

19、67;2.1二元一次不定方程,一、齊次方程,二、非齊次方程,例1,三、有整數(shù)解的充要條件,兩個(gè)推論,推論1： 如果（a，b）=1，那么方程（1）有整數(shù)解.推論2： 如果（a，b）∣c，那么方程（1）沒(méi)有整數(shù)解.,例2：判斷下列不定方程有沒(méi)有整數(shù)解。,四、整數(shù)分離法解不定方程,步驟：1、把不定方程變形，用系數(shù)絕對(duì)值較大的未知數(shù)表示系數(shù)絕對(duì)值較小的未知數(shù)；2、把1中的代數(shù)式分離成一個(gè)整式和一個(gè)分式之和；3、通過(guò)觀察和其

20、它方法使分式值為整數(shù)從而篩選得到不定方程的整數(shù)解。,例3,例4:解下列不定方程,五、不定方程組,,例2：求解不定方程組,習(xí)題,§2.2多元一次不定方程,一、三元一次不定方程1、解的存在性 定理：三元一次不定方程 ax+by+cz=d有整數(shù)解的充分必要條件是（a，b，c) ∣d，其中a，b，c，d都是正整數(shù).,2、三元一次不定方程的通解,一般解法,第三章 同余§3.1

21、同余的概念和性質(zhì),二、同余的性質(zhì),,定理 同余關(guān)系是等價(jià)關(guān)系，即(1)自反性 a≡a(mod m)。(2)對(duì)稱(chēng)性 若a≡b(mod m)，則b≡a(mod m)。(3)傳遞性 若a≡b(mod m)，b≡c(mod m)，則a≡c(mod m)。,定理 設(shè)a、b、c、d為整數(shù)，m為正整數(shù)，若a≡b(mod m)，c≡d(mod m)，則： (1)ax＋cy≡bx＋dy(mod m)，x、y為任意整數(shù)，即同余式可以相加

22、；(2)ac≡bd(mod m)，即同余式可以相乘；(3)an≡bn(mod m)，n＞0；(4)f(a)≡f(b)(mod m)，f(x)為任一整系數(shù)多項(xiàng)式。證明 (1)因?yàn)閍≡b(mod m)，c≡d(mod m)，所以m|(a－b)，m|(c－d)，于是m|((a－b)x＋(c－d)y)，即m|((ax＋cy)－(bx＋dy))，故ax＋cy≡bx＋dy(mod m)。(2)因?yàn)閍≡b(mod m)，c≡d(mod m

23、)，所以m|(a－b)，m|(c－d)，于是m|((a－b)c＋(c－d)b)，即m|(ac－bd)，故ac≡bd(mod m)。,,(3)因?yàn)閍≡b(mod m)，則存在整數(shù)q使得a－b＝mq。于是：an－bn＝(b＋mq)n－bn＝(bn＋bn-1(mq)1＋…＋b1(mq)n-1＋(mq)n)－bn＝mp，其中p是一整數(shù)。所以an≡bn(mod m)。(4)由(1)和(3)可證。,,定理 若ac≡bc(mod m)，且(c，

24、m)＝d，則a≡b(mod m/d)證明 由(c，m)＝d得(c/d，m/d)＝1。由ac≡bc(mod m)得m|(ac－bc)，于是(m/d)|(a－b)(c/d)。又(c/d，m/d)＝1，從而(m/d)|(a－b)。故a≡b(mod m/d)。,,例1 求3406寫(xiě)成十進(jìn)制數(shù)時(shí)的個(gè)位數(shù)。解 因?yàn)?2≡－1(mod 10)，34≡1(mod 10)，所以3404≡1(mod 10)。因此，3406≡3404·32