大學數學---初等數論

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

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

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

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

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

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

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

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

9、數，且（a，b）=d，則必存在整數m和n，使得 d=ma+nb注：證明可由帶余除法逆向代入證得。,例1：求（735000，238948）.,解：因為735000=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）.,解：因為5125=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的最大公因數。 因為3245=2605×1+1180， 2605=1180×1+885 1180=885×1+295 885=295×3 所以（2605，3245）=295. 再求295與7250的最大公因數。 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.,練習,求（125，610）.求（51306，1224）.求（538，244，555）.,§1.3最小公倍數一、定義,二、最小公倍數的性質,1、定理：,例1：求[3468,24871].,解：由輾轉相除法得： （3468，24871）=17.所以[3468,24871]= =5073684.,例2：求[128，234，524].,習題,1

15、、求[21，35].2、求[123，321].3、求[125，725，1125，2015].,§1.4整數可除性的檢驗,一、整數的表示1、十進制的整數的意義：各位數字的加權和。2、一般表示：,進位制,進位制是一種記數方式，用有限的數字在不同的位置表示不同的數值?？墒褂脭底址柕膫€數稱為基數，基數為n，即可稱n進位制，簡稱n進制?，F在最常用的是十進制，通常使用10個阿拉伯數字0-9進行記數。,進位制,常見的進位制：

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

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

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

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

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

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

22、；(2)ac≡bd(mod m)，即同余式可以相乘；(3)an≡bn(mod m)，n＞0；(4)f(a)≡f(b)(mod m)，f(x)為任一整系數多項式。證明 (1)因為a≡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)因為a≡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)因為a≡b(mod m)，則存在整數q使得a－b＝mq。于是：an－bn＝(b＋mq)n－bn＝(bn＋bn-1(mq)1＋…＋b1(mq)n-1＋(mq)n)－bn＝mp，其中p是一整數。所以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寫成十進制數時的個位數。解 因為32≡－1(mod 10)，34≡1(mod 10)，所以3404≡1(mod 10)。因此，3406≡3404·32