初等數(shù)論第一章1

1、初等數(shù)論,Number Theory,第一章 整除理論,整除性理論是初等數(shù)論的基礎(chǔ)。本章要介紹帶余數(shù)除法，輾轉(zhuǎn)相除法，最大公約數(shù)，最小公倍數(shù)，算術(shù)基本定理以及它們的一些應(yīng)用。,第一節(jié) 數(shù)的整除性,定義1 設(shè)a，b是整數(shù)，b ? 0，如果存在整數(shù)c，使得 a = bc成立，則稱a被b整除，a是b的倍數(shù)，b是a的約數(shù)（因數(shù)或除數(shù)），并且使用記號(hào)b?a；如果不存在整數(shù)c使得a = bc成立，則稱a不

2、被b整除，記為b a。,第一節(jié) 數(shù)的整除性,顯然每個(gè)非零整數(shù)a都有約數(shù) ?1，?a，稱這四個(gè)數(shù)為a的平凡約數(shù)，a的另外的約數(shù)稱為非平凡約數(shù)。,被2整除的整數(shù)稱為偶數(shù)，不被2整除的整數(shù)稱為奇數(shù)。,由定義可得下面定理，證明留作練習(xí)。,第一節(jié) 數(shù)的整除性,定理1 下面的結(jié)論成立：(ⅰ) a?b ? ?a??b；(ⅱ) a?b，b?c ? a?c；(ⅲ) b?ai，i = 1, 2, ?, k ? b?a1x1 ? a2x2

3、 ? ? ? akxk，此處xi(i = 1, 2, ?, k)是任意的整數(shù)；(ⅳ) b?a ? bc?ac，此處c是任意的非零整數(shù)；(ⅴ) b?a, a?0 ?|b| ? |a|; b?a且|a| < |b| ? a = 0。,第一節(jié) 數(shù)的整除性,定義2 若整數(shù)a ? 0，?1，并且只有約數(shù) ?1和 ?a，則稱a是素?cái)?shù)(或質(zhì)數(shù))；否則稱a為合數(shù)。 以后無特別說明，素?cái)?shù)總是指正素?cái)?shù)。,定理2 任何

4、大于1的整數(shù)a都至少有一個(gè)素約數(shù)。,證明 若a是素?cái)?shù)，則定理是顯然的。,若a不是素?cái)?shù)，那么它有兩個(gè)以上的正的非平凡約數(shù)，設(shè)它們是d1, d2, ?, dk 。,第一節(jié) 數(shù)的整除性,不妨設(shè)d1是其中最小的。若d1不是素?cái)?shù)，則存在e1 > 1，e2 > 1，使得d1 = e1e2，,因此，e1和e2也是a的正的非平凡約數(shù)。這與d1的最小性矛盾。所以d1是素?cái)?shù)。證畢。,推論 任何大于1的合數(shù)a必有一個(gè)不超過的素約

5、 數(shù)。,證明 使用定理2中的記號(hào)，有a = d1d2，其中d1 > 1是最小的素約數(shù)，所以d12 ? a。證畢。,第一節(jié) 數(shù)的整除性,例1 設(shè)r是正奇數(shù), 證明: 對(duì)任意的正整數(shù)n, 有n ? 2 1r ? 2 r ? ? ? n r。,解 對(duì)于任意的正整數(shù)a，b以及正奇數(shù)k，有ak ? bk = (a ? b)(ak ? 1 ? ak ? 2b ? ak ? 3b2 ? ? ? bk ? 1) = (

6、a ? b)q，,其中q是整數(shù)。記s = 1r ? 2 r ? ? ? n r，則2s = 2 ? (2 r ? n r) ? (3 r ? (n ? 1)r) ? ? ? (n r ? 2 r) = 2 ? (n ? 2)Q，,第一節(jié) 數(shù)的整除性,其中Q是整數(shù)。若n ? 2?s，由上式知n ? 2?2，因?yàn)閚 ? 2 > 2，這是不可能的，所以n ? 2 s。,例2 設(shè)A= { d1, d2, ?, dk

7、}是n的所有約數(shù)的集合,則B= 也是n的所有約數(shù)的集合。,解 由以下三點(diǎn)理由可以證得結(jié)論：(ⅰ) A和B的元素個(gè)數(shù)相同；(ⅱ) 若di?A，即di?n，則 ，反之亦然；,第一節(jié) 數(shù)的整除性,(ⅲ) 若di ? dj，則 。,例3 以d(n)表示n的正約數(shù)的個(gè)數(shù)，例如：d(1) = 1，d(2) = 2，d(3) = 2，d(4) =

8、3，? 。問：d(1) ? d(2) ? ? ? d(1997)是否為偶數(shù)？,解對(duì)于n的每個(gè)約數(shù)d，都有n = d? ，因此，n的正約數(shù)d與 是成對(duì)地出現(xiàn)的。,第一節(jié) 數(shù)的整除性,只有當(dāng)d = , 即n = d2時(shí)，d 和 才是同一個(gè)數(shù)。故當(dāng)且僅當(dāng)n是完全平方數(shù)時(shí)，d(n)是奇數(shù)。,因?yàn)?42 < 1997 < 452，所以在d(1), d(2), ?, d(1997)中恰有44個(gè)奇數(shù)，故d

9、(1) ? d(2) ? ? ? d(1997)是偶數(shù)。,第一節(jié) 數(shù)的整除性,例4 設(shè)凸2n邊形M的頂點(diǎn)是A1, A2, ?, A2n，點(diǎn)O在M的內(nèi)部，用1, 2, ?, 2n將M的2n條邊分別編號(hào)，又將OA1, OA2, ?, OA2n也同樣進(jìn)行編號(hào)，若把這些編號(hào)作為相應(yīng)的線段的長度，證明：無論怎么編號(hào)，都不能使得三角形OA1A2, OA2A3, ?, OA2nA1的周長都相等。,第一節(jié) 數(shù)的整除性,解 假設(shè)這些三角形的周長都

10、相等，記為s。則2ns = 3(1 ? 2 ? ? ? 2n) = 3n(2n ? 1)，即2s = 3(2n ? 1)，因此2?3(2n ? 1)，這是不可能的，這個(gè)矛盾,說明這些三角形的周長不可能全都相等。,第一節(jié) 數(shù)的整除性,例5 設(shè)整數(shù)k ? 1，證明： (ⅰ) 若2k ? n < 2k ? 1，1 ? a ? n，a ? 2k， 則2k a； (ⅱ)

11、 若3k ? 2n ? 1 < 3k + 1，1 ? b ? n， 2b ? 1 ? 3k， 則3k 2b ? 1。,第一節(jié) 數(shù)的整除性,解 (ⅰ) 若2k|a，則存在整數(shù)q，使得a= q2k。顯然q只可能是0或1。此時(shí)a= 0或2k ，這都是不可能的，所以2k a；,(ⅱ) 若 3k|2b-1，則存在整數(shù)q，使得2b-1= q3k，顯然q只可能是0，1, 或

12、2。此時(shí)2b-1= 0，3k，或，這都是不可能的，所以3k 2b ? 1。,第一節(jié) 數(shù)的整除性,例6 寫出不超過100的所有的素?cái)?shù)。,解 將不超過100的正整數(shù)排列如下：,第一節(jié) 數(shù)的整除性,1 2 3 4 5 6 7 8 9 10 11 12 1314 15 16 17 18 19 20 21 22 23 24 25

13、 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 67 68 69 70 71 72 73 74 75 76 77 7

14、8 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100,,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,—,

15、—,—,—,—,—,—,—,—,—,—,—,—,—,第一節(jié) 數(shù)的整除性,按以下步驟進(jìn)行：(ⅰ) 刪去1，剩下的后面的第一個(gè)數(shù)是2，2是素?cái)?shù), 刪去2后面的被2整除的數(shù)；(ⅱ) 剩下的2后面的第一個(gè)數(shù)是3，3是素?cái)?shù), 再刪去3后面的被3整除的數(shù)；(ⅲ) 剩下的3后面的第一個(gè)數(shù)是5，5是素?cái)?shù), 再刪去5后面的被5整除的數(shù)；(ⅳ) 剩下的5后面的第一個(gè)數(shù)是7，7是素?cái)?shù), 再刪去7后面的被7整除的數(shù).,第一節(jié) 數(shù)的整除性,

16、照以上步驟可以到素?cái)?shù)2, 3, 5, 7, 11, ?等25個(gè)。由定理2推論可知，不超過100的合數(shù)必有一個(gè)不超過10的素約數(shù)，因此在刪去7后面被7整除的數(shù)以后，就得到了不超過100的全部素?cái)?shù)。,在例6中所使用的尋找素?cái)?shù)的方法，稱為Eratosthenes篩法。它可以用來求出不超過任何固定整數(shù)的所有素?cái)?shù)。在理論上這是可行的；但在實(shí)際應(yīng)用中，這種列出素?cái)?shù)的方法需要大量的計(jì)算時(shí)間，是不可取的。,第一節(jié) 數(shù)的整除性,例7 證明：存在無窮

17、多個(gè)正整數(shù)a，使得n4 ? a（n = 1, 2, 3, ?）都是合數(shù)。,解 取a = 4k4，對(duì)于任意的n?N，有n4 ? 4k4 = (n2 ? 2k2)2 ? 4n2k2 = (n2 ? 2k2 ? 2nk)(n2 ? 2k2 ? 2nk)。因?yàn)?n2 ? 2k2 ? 2nk = (n ? k)2 ? k2 ? k2，所以，對(duì)于任意的k = 2, 3, ? 以及任意的n?N，n4 ? a是合數(shù)。,第一節(jié) 數(shù)的整除

18、性,例8 設(shè)a1, a2, ?, an是整數(shù)，且a1 ? a2 ? ? ? an = 0，a1a2?an = n，則4?n。,解 如果2 n，則n, a1, a2, ?, an都是奇數(shù)。于是a1 ? a2 ? ? ? an是奇數(shù)個(gè)奇數(shù)之和，不可能等于零，這與題設(shè)矛盾，,所以2?n，即在a1, a2, ?, an中至少有一個(gè)偶數(shù)。,第一節(jié) 數(shù)的整除性,如果只有一個(gè)偶數(shù)，不妨設(shè)為a1，那么2 ai（2 ? i ? n）。此

19、時(shí)有等式a2 ? ? ? an = ?a1，在上式中，左端是(n ? 1)個(gè)奇數(shù)之和，右端是偶數(shù)，這是不可能的，因此，在a1, a2, ?, an中至少有兩個(gè)偶數(shù)，即4?n。,第一節(jié) 數(shù)的整除性,例9 若n是奇數(shù)，則8?n2 ? 1。,解 設(shè)n = 2k ? 1，則n2 ? 1= (2k ? 1)2 ? 1 = 4k(k ? 1)。在k和k ? 1中有一個(gè)是偶數(shù)，所以8?n2 ? 1。,例9的結(jié)論雖然簡單，卻是很有用的。

20、例如，使用例3中的記號(hào)，我們可以提出下面的問題：問題 d(1)2 ? d(2)2 ? ? ? d(1997)2被4除的余數(shù)是多少？,第一節(jié) 數(shù)的整除性,例10 證明：方程 a12 ? a22 ? a32 = 1999 (1)無整數(shù)解。,解 若a1，a2，a3都是奇數(shù)，則存在整數(shù)A1，A2，A3，使得a12 = 8A1 ? 1，a22 = 8A2 ? 1

21、，a32 = 8A3 ? 1，于是a12 ? a22 ? a32 = 8(A1 ? A2 ? A3) ? 3。,第一節(jié) 數(shù)的整除性,由于1999被8除的余數(shù)是7，所以a1，a2，a3不可能都是奇數(shù)。由式(1)，a1，a2，a3中只能有一個(gè)奇數(shù)，設(shè)a1為奇數(shù)，a2，a3為偶數(shù)，則存在整數(shù)A1，A2，A3，使得a12 = 8A1 ? 1，a22 = 8A2 ? r，a32 = 8A3 ? s，于是a12 ? a22 ? a32

22、 = 8(A1 ? A2 ? A3) ? 1 ? r ? s，,第一節(jié) 數(shù)的整除性,其中r和s是整數(shù)，而且只能取值0或4。這樣a12 ? a22 ? a32被8除的余數(shù)只可能是1或5，但1999被8除的余數(shù)是7，所以這樣的a1，a2，a3也不能使式(2)成立。綜上證得所需要的結(jié)論。,習(xí) 題 一,1. 證明定理1。2. 證明：若m ? p?mn ? pq, 則m ? p?mq ? np。3. 證明：任意給定的連續(xù)39個(gè)自然數(shù)，