初等數(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ù)），并且使用記號b?a；如果不存在整數(shù)c使得a = bc成立，則稱a不

2、被b整除，記為b a。,第一節(jié) 數(shù)的整除性,顯然每個非零整數(shù)a都有約數(shù) ?1，?a，稱這四個數(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是素數(shù)(或質(zhì)數(shù))；否則稱a為合數(shù)。 以后無特別說明，素數(shù)總是指正素數(shù)。,定理2 任何

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

5、 數(shù)。,證明 使用定理2中的記號，有a = d1d2，其中d1 > 1是最小的素約數(shù)，所以d12 ? a。證畢。,第一節(jié) 數(shù)的整除性,例1 設(shè)r是正奇數(shù), 證明: 對任意的正整數(shù)n, 有n ? 2 1r ? 2 r ? ? ? n r。,解 對于任意的正整數(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，因為n ? 2 > 2，這是不可能的，所以n ? 2 s。,例2 設(shè)A= { d1, d2, ?, dk

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

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

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

10、相等，記為s。則2ns = 3(1 ? 2 ? ? ? 2n) = 3n(2n ? 1)，即2s = 3(2n ? 1)，因此2?3(2n ? 1)，這是不可能的，這個矛盾,說明這些三角形的周長不可能全都相等。,第一節(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。此時a= 0或2k ，這都是不可能的，所以2k a；,(ⅱ) 若 3k|2b-1，則存在整數(shù)q，使得2b-1= q3k，顯然q只可能是0，1, 或

12、2。此時2b-1= 0，3k，或，這都是不可能的，所以3k 2b ? 1。,第一節(jié) 數(shù)的整除性,例6 寫出不超過100的所有的素數(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ù)的整除性,按以下步驟進行：(ⅰ) 刪去1，剩下的后面的第一個數(shù)是2，2是素數(shù), 刪去2后面的被2整除的數(shù)；(ⅱ) 剩下的2后面的第一個數(shù)是3，3是素數(shù), 再刪去3后面的被3整除的數(shù)；(ⅲ) 剩下的3后面的第一個數(shù)是5，5是素數(shù), 再刪去5后面的被5整除的數(shù)；(ⅳ) 剩下的5后面的第一個數(shù)是7，7是素數(shù), 再刪去7后面的被7整除的數(shù).,第一節(jié) 數(shù)的整除性,

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

17、多個正整數(shù)a，使得n4 ? a（n = 1, 2, 3, ?）都是合數(shù)。,解 取a = 4k4，對于任意的n?N，有n4 ? 4k4 = (n2 ? 2k2)2 ? 4n2k2 = (n2 ? 2k2 ? 2nk)(n2 ? 2k2 ? 2nk)。因為 n2 ? 2k2 ? 2nk = (n ? k)2 ? k2 ? k2，所以，對于任意的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ù)個奇數(shù)之和，不可能等于零，這與題設(shè)矛盾，,所以2?n，即在a1, a2, ?, an中至少有一個偶數(shù)。,第一節(jié) 數(shù)的整除性,如果只有一個偶數(shù)，不妨設(shè)為a1，那么2 ai（2 ? i ? n）。此

19、時有等式a2 ? ? ? an = ?a1，在上式中，左端是(n ? 1)個奇數(shù)之和，右端是偶數(shù)，這是不可能的，因此，在a1, a2, ?, an中至少有兩個偶數(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中有一個是偶數(shù)，所以8?n2 ? 1。,例9的結(jié)論雖然簡單，卻是很有用的。

20、例如，使用例3中的記號，我們可以提出下面的問題：問題 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中只能有一個奇數(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個自然數(shù)，