初等數論第一章1

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

2、被b整除，記為b a。,第一節(jié) 數的整除性,顯然每個非零整數a都有約數 ?1，?a，稱這四個數為a的平凡約數，a的另外的約數稱為非平凡約數。,被2整除的整數稱為偶數，不被2整除的整數稱為奇數。,由定義可得下面定理，證明留作練習。,第一節(jié) 數的整除性,定理1 下面的結論成立：(ⅰ) 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)是任意的整數；(ⅳ) b?a ? bc?ac，此處c是任意的非零整數；(ⅴ) b?a, a?0 ?|b| ? |a|; b?a且|a| < |b| ? a = 0。,第一節(jié) 數的整除性,定義2 若整數a ? 0，?1，并且只有約數 ?1和 ?a，則稱a是素數(或質數)；否則稱a為合數。 以后無特別說明，素數總是指正素數。,定理2 任何

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

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

6、a ? b)q，,其中q是整數。記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é) 數的整除性,其中Q是整數。若n ? 2?s，由上式知n ? 2?2，因為n ? 2 > 2，這是不可能的，所以n ? 2 s。,例2 設A= { d1, d2, ?, dk

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

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

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

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

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

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

17、多個正整數a，使得n4 ? a（n = 1, 2, 3, ?）都是合數。,解 取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是合數。,第一節(jié) 數的整除

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

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

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

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

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