初等數(shù)論NumberTheory初等數(shù)論NumberTheory1第一章整除理論整除性理論是初等數(shù)論的基礎(chǔ)。本章要介紹帶余數(shù)除法，輾轉(zhuǎn)相除法，最大公約數(shù)，最小公倍數(shù)，算術(shù)基本定理以及它們的一些應(yīng)用。第一章整除理論整除性理論是初等數(shù)論的基礎(chǔ)。本章要介紹帶余2第一節(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不被b整除，記為ba。第一節(jié)數(shù)的整除性定義1設(shè)a，b是整數(shù)，b0，如3第一節(jié)數(shù)的整除性顯然每個(gè)非零整數(shù)a都有約數(shù)

1，

a，稱這四個(gè)數(shù)為a的平凡約數(shù)，a的另外的約數(shù)稱為非平凡約數(shù)。被2整除的整數(shù)稱為偶數(shù)，不被2整除的整數(shù)稱為奇數(shù)。由定義可得下面定理，證明留作練習(xí)。第一節(jié)數(shù)的整除性顯然每個(gè)非零整數(shù)a都有4第一節(jié)數(shù)的整除性定理1

下面的結(jié)論成立：(ⅰ)a

b

a

b；(ⅱ)a

b，b

c

a

c；(ⅲ)b

ai，i=1,2,

,k

b

a1x1

a2x2

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ù)的整除性定理1下面的結(jié)論成立：5第一節(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

任何大于1的整數(shù)a都至少有一個(gè)素約數(shù)。證明若a是素?cái)?shù)，則定理是顯然的。若a不是素?cái)?shù)，那么它有兩個(gè)以上的正的非平凡約數(shù)，設(shè)它們是d1,d2,

,dk。

第一節(jié)數(shù)的整除性定義2若整數(shù)a0，1，并且只6第一節(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è)不超過的素約數(shù)。證明使用定理2中的記號(hào)，有a=d1d2，其中d1>1是最小的素約數(shù)，所以d12

a。證畢。第一節(jié)數(shù)的整除性不妨設(shè)d1是其中最小的。若d1不是素?cái)?shù)，7第一節(jié)數(shù)的整除性例1

設(shè)r是正奇數(shù),證明:對(duì)任意的正整數(shù)n,有n

21r

2

r

nr。解對(duì)于任意的正整數(shù)a，b以及正奇數(shù)k，有ak

bk=(a

b)(ak

1

ak

2b

ak

3b2

bk

1)=(a

b)q，其中q是整數(shù)。記s=1r

2

r

nr，則2s=2

(2

r

nr)

(3

r

(n

1)r)

(nr

2

r)=2

(n

2)Q，

第一節(jié)數(shù)的整除性例1設(shè)r是正奇數(shù),證明:對(duì)任意的8第一節(jié)數(shù)的整除性其中Q是整數(shù)。若n

2

s，由上式知n

2

2，因?yàn)閚

2>2，這是不可能的，所以n

2s。例2

設(shè)A={d1,d2,

,dk

}是n的所有約數(shù)的集合,則B=也是n的所有約數(shù)的集合。解由以下三點(diǎn)理由可以證得結(jié)論：(ⅰ)A和B的元素個(gè)數(shù)相同；(ⅱ)若di

A，即di

n，則，反之亦然；第一節(jié)數(shù)的整除性其中Q是整數(shù)。若n2s，由上式知9第一節(jié)數(shù)的整除性(ⅲ)若di

dj，則。例3以d(n)表示n的正約數(shù)的個(gè)數(shù)，例如：d(1)=1，d(2)=2，d(3)=2，d(4)=3，

。問：d(1)

d(2)

d(1997)是否為偶數(shù)？解對(duì)于n的每個(gè)約數(shù)d，都有n=d

，因此，n的正約數(shù)d與是成對(duì)地出現(xiàn)的。

第一節(jié)數(shù)的整除性(ⅲ)若didj，則10第一節(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(1)

d(2)

d(1997)是偶數(shù)。第一節(jié)數(shù)的整除性只有當(dāng)d=,即n=d2時(shí)11第一節(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ù)的整除性例4設(shè)凸2n邊形M的頂點(diǎn)是A1,A12第一節(jié)數(shù)的整除性解假設(shè)這些三角形的周長都相等，記為s。則2ns=3(1

2

2n)=3n(2n

1)，即2s=3(2n

1)，因此2

3(2n

1)，這是不可能的，這個(gè)矛盾,說明這些三角形的周長不可能全都相等。第一節(jié)數(shù)的整除性解假設(shè)這些三角形的周長都相等，記為s13第一節(jié)數(shù)的整除性例5

設(shè)整數(shù)k

1，證明：(ⅰ)若2k

n<2k

1，1

a

n，a

2k，則2ka；(ⅱ)若3k

2n

1<3k+1，1

b

n，2b

1

3k，則3k2b

1。第一節(jié)數(shù)的整除性例5設(shè)整數(shù)k1，證明：14第一節(jié)數(shù)的整除性解

(ⅰ)若2k|a，則存在整數(shù)q，使得a=

q2k。顯然q只可能是0或1。此時(shí)a=0或2k

，這都是不可能的，所以2ka；(ⅱ)若3k|2b-1，則存在整數(shù)q，使得2b-1=

q3k，顯然q只可能是0，1,或2。此時(shí)2b-1=0，3k，或，這都是不可能的，所以3k2b

1。第一節(jié)數(shù)的整除性解(ⅰ)若2k|a，則存在15第一節(jié)數(shù)的整除性例6寫出不超過100的所有的素?cái)?shù)。解將不超過100的正整數(shù)排列如下：

第一節(jié)數(shù)的整除性例6寫出不超過100的所有的素?cái)?shù)。16第一節(jié)數(shù)的整除性12

34567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465

676869707172737475767778798081828384858687888990919293949596979899100

———————————————————————————————————————————————————————————————————————————第一節(jié)數(shù)的整除性123417第一節(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ù)的整除性按以下步驟進(jìn)行：18第一節(jié)數(shù)的整除性照以上步驟可以到素?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ù)的整除性照以上步驟可以到素?cái)?shù)2,3,5,719第一節(jié)數(shù)的整除性例7

證明：存在無窮多個(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)閚2

2k2

2nk=(n

k)2

k2

k2，所以，對(duì)于任意的k=2,3,

以及任意的n

N，n4

a是合數(shù)。第一節(jié)數(shù)的整除性例7證明：存在無窮多個(gè)正整數(shù)a，使得20第一節(jié)數(shù)的整除性例8設(shè)a1,a2,

,an是整數(shù)，且a1

a2

an

=0，a1a2

an

=n，則4

n。解如果2n，則n,a1,a2,

,an都是奇數(shù)。于是a1

a2

an是奇數(shù)個(gè)奇數(shù)之和，不可能等于零，這與題設(shè)矛盾，所以2

n，即在a1,a2,

,an中至少有一個(gè)偶數(shù)。

第一節(jié)數(shù)的整除性例8設(shè)a1,a2,,an是21第一節(jié)數(shù)的整除性如果只有一個(gè)偶數(shù)，不妨設(shè)為a1，那么2ai（2

i

n）。此時(shí)有等式a2

an=

a1，在上式中，左端是(n

1)個(gè)奇數(shù)之和，右端是偶數(shù)，這是不可能的，因此，在a1,a2,

,an中至少有兩個(gè)偶數(shù)，即4

n。第一節(jié)數(shù)的整除性如果只有一個(gè)偶數(shù)，不妨設(shè)為a1，那么222第一節(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é)論雖然簡單，卻是很有用的。例如，使用例3中的記號(hào)，我們可以提出下面的問題：問題d(1)2

d(2)2

d(1997)2被4除的余數(shù)是多少？第一節(jié)數(shù)的整除性例9若n是奇數(shù)，則8n2123第一節(jié)數(shù)的整除性例10證明：方程a12

a22

a32=1999(1)無整數(shù)解。解若a1，a2，a3都是奇數(shù)，則存在整數(shù)A1，A2，A3，使得a12=8A1

1，a22=8A2

1，a32=8A3

1，于是a12

a22

a32=8(A1

A2

A3)

3。第一節(jié)數(shù)的整除性例10證明：方程解若a1，a24第一節(jié)數(shù)的整除性由于1999被8除的余數(shù)是7，所以a1，a2，a3不可能都是奇數(shù)。由式(1)，a1，a