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

1、初等數(shù)論,Number Theory,,第一章 整除理論,整除性理論是初等數(shù)論的基礎(chǔ)。本章要介紹帶余數(shù)除法，輾轉(zhuǎn)相除法，最大公約數(shù)，最小公倍數(shù)，算術(shù)基本定理以及它們的一些應(yīng)用。,第三節(jié) 最大公約數(shù),定義1 整數(shù)a1, a2, …, ak的公共約數(shù)稱為a1, a2, …, ak的公約數(shù)。不全為零的整數(shù)a1, a2, …, ak的公約數(shù)中最大的一個叫做a1, a2, …, ak的最大公約數(shù)（或最大公因數(shù)），記為(a1, a2, …,

2、ak)。,由于每個非零整數(shù)的約數(shù)的個數(shù)是有限的, 所以最大公約數(shù)是存在的, 并且是正整數(shù).,第三節(jié) 最大公約數(shù),如果(a1, a2, …, ak) = 1，則稱 a1, a2, …, ak是互素的（或互質(zhì)的）；如果(ai, a j) = 1，1 ? i, j ? k，i ? j，則稱a1, a2, …, ak是兩兩互素的(或兩兩互質(zhì)的).,顯然，a1, a2, …, ak兩兩互素可以推出(a1, a2, …, ak) = 1，反

3、之則不然，例如(2, 6, 15) = 1，但(2, 6) = 2。,第三節(jié) 最大公約數(shù),定理1 下面的等式成立：(ⅰ) (a1, a2, …, ak) = (|a1|, |a2|, …, |ak|)；(ⅱ) (a, 1) = 1，(a, 0) = |a|，(a, a) = |a|；(ⅲ) (a, b) = (b, a)；(ⅳ) 若p是素數(shù), a是整數(shù), 則(p, a) = 1或p?a;(ⅴ) 若a = b

4、q ? r，則(a, b) = (b, r)。,第三節(jié) 最大公約數(shù),證明 (ⅰ)??(ⅳ)留作習(xí)題。(ⅴ) 由第一節(jié)定理1可知, 如果d?a，d?b，則有d?r = a ? bq，反之, 若d?b，d?r，則d?a = bq ? r. 因此a與b的全體公約數(shù)的集合就是b與r的全體公約數(shù)的集合，這兩個集合中的最大正數(shù)當(dāng)然相等，即(a, b) = (b, r)。證畢。,由定理1可知,在討論(a1, a2, …, an)時,不妨假設(shè)a

5、1, a2, …, an是正整數(shù),以后我們就維持這一假設(shè).,第三節(jié) 最大公約數(shù),定理2 設(shè)a1, a2, …, ak?Z，記A = { y:y = x1a1+x2a2+ …+xkak ,xi?Z,? ? i ? k }.如果y0是集合A中最小的正數(shù), 則y0=(a1,a2, …,ak).,證明 設(shè)d是a1, a2, …, ak的一個公約數(shù), 則d?y0,所以d ? y0. 另一方面, 由第二節(jié)例2知, y0也是a1, a2

6、, …, ak的公約數(shù). 因此y0是a1, a2, …, ak的公約數(shù)中的最大者, 即y0 = ( a1, a2, …, ak). 證畢.,第三節(jié) 最大公約數(shù),推論1 設(shè)d是a1, a2, …, ak的一個公約數(shù)，則d?(a1, a2, …, ak)。,這個推論對最大公約數(shù)的性質(zhì)做了更深的刻劃：最大公約數(shù)不但是公約數(shù)中的最大的，而且是所有公約數(shù)的倍數(shù)。,推論2 (ma1, ma2, …, mak) = |m|(a1, a2, …,

7、 ak)。,第三節(jié) 最大公約數(shù),推論3 記? = (a1, a2, …, ak)，則,特別地,,第三節(jié) 最大公約數(shù),定理3 (a1, a2, …, ak) = 1的充要條件是存在整數(shù)x1, x2, …, xk，使得a1x1 ? a2x2 ? … ? akxk = 1。 (1),證明 必要性 由定理2得到。充分性 若式(1)成立，如果 (a1, a2, …, ak) = d >

8、1，那么由d?ai（1 ? i ? k）推出d?a1x1 ? a2x2 ? … ? akxk = 1，這是不可能的。所以有(a1, a2, …, ak) = 1。證畢。,第三節(jié) 最大公約數(shù),定理4 對于任意的整數(shù)a，b，c，下面的結(jié)論成立：(ⅰ) 由b?ac及(a, b) = 1可以推出b?c；(ⅱ) 由b?c，a?c及(a, b) = 1可以推出ab?c。,證明 (ⅰ) 若(a, b) = 1，由定理2，存在整數(shù)x與

9、y，使得ax ? by = 1。,第三節(jié) 最大公約數(shù),因此 acx ? bcy = c (2)由上式及b?ac得到b?c。結(jié)論(ⅰ)得證；(ⅱ) 若(a, b) = 1，則存在整數(shù)x，y使得式(2)成立。由b?c與a?c得到ab?ac，ab?bc，再由式(2)得到ab?c。結(jié)論(ⅱ)得證。證畢。,第三節(jié) 最大公約數(shù),

10、推論1 若p是素數(shù)，則下述結(jié)論成立：(ⅰ) p?ab ? p?a或p?b；(ⅱ) p?a2 ? p?a。,證明 留作習(xí)題。,第三節(jié) 最大公約數(shù),推論2 若 (a, b) = 1，則(a, bc) = (a, c)。,證明 設(shè)d是a與bc的一個公約數(shù)，則d?a，d?bc，由式（2）得到，d|c, 即d是a與c的公約數(shù)。另一方面，若d是a與c的公約數(shù)，則它也是a與bc的公約數(shù)。因此，a與c的公約數(shù)的集合，就是a與bc

11、的公約數(shù)的集合，所以(a, bc) = (a, c)。證畢。,第三節(jié) 最大公約數(shù),推論3 若 (a, bi) = 1，1 ? i ? n，則 (a, b1b2…bn) = 1。,證明 留作習(xí)題。,定理5 對于任意的n個整數(shù)a1, a2, …, an，記(a1, a2) = d2, (d2, a3) = d3, …, (dn ? 2, an ? 1) = dn ? 1,

12、 (dn ? 1, an) = dn，則 dn = (a1, a2, …, an).,第三節(jié) 最大公約數(shù),證明 由定理2的推論，我們有 dn = (dn ? 1, an) ? dn?an，dn?dn ? 1，dn ? 1 = (dn ? 2, an ? 1) ? dn ? 1?an ? 1，dn ? 1?dn ? 2， ? dn?an，dn?an ?

13、1，dn?dn ? 2，dn ? 2 = (dn ? 3, an ? 2) ? dn ? 2?an ? 2，dn ? 2?dn ? 3 ? dn?an，dn?an ? 1，dn?an ? 2，dn?dn ? 3， ……,第三節(jié) 最大公約數(shù),d2 = (a1, a2) ? dn?an，dn?an ? 1，…，dn?a2，dn?a1，即dn是a1, a2, …, an的一個公約數(shù)。,另一方面，對于a

14、1, a2, …, an的任何公約數(shù)d，由定理2的推論及d2, …, dn的定義，依次得出 d?a1，d?a2 ? d?d2， d?d2，d?a3 ? d?d3， ……,第三節(jié) 最大公約數(shù),d?dn ? 1，d?an ? d?dn，因此dn是a1, a2, …, an的公約數(shù)中的最大者，即dn = (a1, a2, …, an)。證畢。,第三節(jié) 最大公約數(shù),證明 由定理1得到 (21n ? 4, 14n ? 3)

15、 = (7n ? 1, 14n ? 3) = (7n ? 1, 1) = 1。,,,,,例1 證明: 若n是正整數(shù),則 是既約分數(shù).,注：一般地，若(x, y) = 1，那么，對于任意的整數(shù)a，b，有 (x, y) = (x ?ay, y) = (x ?ay, y ? b(x ?ay)) = (x ?ay, (ab ? 1)y ? bx)， 因此，是

16、 既約分數(shù)。,第三節(jié) 最大公約數(shù),證明 由于121 = 112，n2 ? 2n ? 12 = (n ? 1)2 ? 11，所以，若112?(n ? 1)2 ? 11， (3)則11?(n ? 1)2，因此，由定理4的推論1得到11?n ? 1，112?(n ? 1)2。再由式(3)得到 112?11，這是不可能的。所以式(3)不能成立。,,,,,例2 證明：,第三節(jié)

17、 最大公約數(shù),,,,,,注：這個例題的一般形式是：設(shè)p是素數(shù)，a，b是整數(shù)，則Pk (an ? b)k ? pk ? 1c，其中c是不被p整除的任意整數(shù)，k是任意的大于1的整數(shù)。,第三節(jié) 最大公約數(shù),證明 由式(4)得到9?(a ? b)2 ? 3ab ? 3?(a ? b)2 ? 3ab? 3?(a ? b)2 ? 3?a ? b (5)? 9?(a ? b)2。,,,,,例3

18、設(shè)a，b是整數(shù)，且9?a2 ? ab ? b2， (4)則3?(a, b)。,第三節(jié) 最大公約數(shù),再由式(4)得到 9?3ab ? 3?ab。因此，由定理4的推論1，得到3?a或3?b。若3?a，由式(5)得到3?b；若3?b，由(5)式也 得到3?a。因此，總有3?a且3?b。由定理2的推論推出3?(a, b)。再由式(3)得到 112?11，這是不可能的。所以式(3

19、)不能成立。,,,,,第三節(jié) 最大公約數(shù),證明 (ⅰ) 若a < b，且2b ? 1?2a ? 1。 (6)成立，則2b ? 1 ? 2a ? 1 ? 2b ? 2a ? 2 ? 2a(2b ? a ? 1) ? 2，于是a = 1，b ? a = 1，即b = 2，這是不可能的，所以式(6)不成立。,,,,,,例4 設(shè)a和b是正整數(shù), b > 2, 則2b ?

20、 1 2a ? 1.,第三節(jié) 最大公約數(shù),(ⅱ) 若a = b，且式(6)成立，則由式(6)得到2a ? 1?(2a ? 1) ? 2 ? 2a ? 1?2 ? 2a ? 1 ? 2 ? 2a ? 3，于是b = a = 1，這是不可能的，所以式(6)不成立。,,,,,,第三節(jié) 最大公約數(shù),(ⅲ) 若a > b，記a = kb ? r，0 ? r < b，此時2kb?1=(2b?1)(2(k ? 1)b?2

21、(k ? 2)b???1)=(2b? 1)Q,其中Q是整數(shù)。所以2a ? 1 = 2kb + r ? 1 = 2r(2kb ? 1 ? 1) ? 1 = 2r((2b ? 1)Q ? 1) ? 1 = (2b ? 1)Q ? ? (2r ? 1),其中Q?是整數(shù)。因此2b ? 1?2a ? 1 ? 2b ? 1?2r ? 1，在(ⅰ)中已經(jīng)證明這是不可能的,所以式(6)不能成立.,,,,,,第三節(jié) 最大公約數(shù),,,,,,,