初等數論一演示文稿課件

初等數論NumberTheory初等數論NumberTheory1第一章整除理論整除性理論是初等數論的基礎。本章要介紹帶余數除法，輾轉相除法，最大公約數，最小公倍數，算術基本定理以及它們的一些應用。第一章整除理論整除性理論是初等數論的基礎。本章要介紹帶余2第一節(jié)數的整除性定義1

設a，b是整數，b

0，如果存在整數c，使得

a=bc成立，則稱a被b整除，a是b的倍數，b是a的約數（因數或除數），并且使用記號b

a；如果不存在整數c使得a=bc成立，則稱a不被b整除，記為ba。第一節(jié)數的整除性定義1設a，b是整數，b0，如3第一節(jié)數的整除性顯然每個非零整數a都有約數

1，

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

下面的結論成立：(ⅰ)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)是任意的整數；(ⅳ)b

a

bc

ac，此處c是任意的非零整數；(ⅴ)b

a,a

0

|b|

|a|;b

a且|a|<|b|

a=0。第一節(jié)數的整除性定理1下面的結論成立：5第一節(jié)數的整除性定義2

若整數a

0，

1，并且只有約數

1和

a，則稱a是素數(或質數)；否則稱a為合數。以后無特別說明，素數總是指正素數。定理2

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

,dk。

第一節(jié)數的整除性定義2若整數a0，1，并且只6第一節(jié)數的整除性不妨設d1是其中最小的。若d1不是素數，則存在e1>1，e2>1，使得d1=e1e2，

因此，e1和e2也是a的正的非平凡約數。這與d1的最小性矛盾。所以d1是素數。證畢。

推論任何大于1的合數a必有一個不超過的素約數。證明使用定理2中的記號，有a=d1d2，其中d1>1是最小的素約數，所以d12

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

設r是正奇數,證明:對任意的正整數n,有n

21r

2

r

nr。解對于任意的正整數a，b以及正奇數k，有ak

bk=(a

b)(ak

1

ak

2b

ak

3b2

bk

1)=(a

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

2

r

nr，則2s=2

(2

r

nr)

(3

r

(n

1)r)

(nr

2

r)=2

(n

2)Q，

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

2

s，由上式知n

2

2，因為n

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

2s。例2

設A={d1,d2,

,dk

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

A，即di

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

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

。問：d(1)

d(2)

d(1997)是否為偶數？解對于n的每個約數d，都有n=d

，因此，n的正約數d與是成對地出現的。

第一節(jié)數的整除性(ⅲ)若didj，則10第一節(jié)數的整除性只有當d=,即n=d2時，d和才是同一個數。故當且僅當n是完全平方數時，d(n)是奇數。因為442<1997<452，所以在d(1),d(2),

,d(1997)中恰有44個奇數，故d(1)

d(2)

d(1997)是偶數。第一節(jié)數的整除性只有當d=,即n=d2時11第一節(jié)數的整除性例4

設凸2n邊形M的頂點是A1,A2,

,A2n，點O在M的內部，用1,2,

,2n將M的2n條邊分別編號，又將OA1,OA2,

,OA2n也同樣進行編號，若把這些編號作為相應的線段的長度，證明：無論怎么編號，都不能使得三角形OA1A2,OA2A3,

,OA2nA1的周長都相等。第一節(jié)數的整除性例4設凸2n邊形M的頂點是A1,A12第一節(jié)數的整除性解假設這些三角形的周長都相等，記為s。則2ns=3(1

2

2n)=3n(2n

1)，即2s=3(2n

1)，因此2

3(2n

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

設整數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é)數的整除性例5設整數k1，證明：14第一節(jié)數的整除性解

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

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

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

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

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

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

34567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465

676869707172737475767778798081828384858687888990919293949596979899100

———————————————————————————————————————————————————————————————————————————第一節(jié)數的整除性123417第一節(jié)數的整除性按以下步驟進行：(ⅰ)刪去1，剩下的后面的第一個數是2，2是素數,刪去2后面的被2整除的數；(ⅱ)剩下的2后面的第一個數是3，3是素數,再刪去3后面的被3整除的數；(ⅲ)剩下的3后面的第一個數是5，5是素數,再刪去5后面的被5整除的數；(ⅳ)剩下的5后面的第一個數是7，7是素數,再刪去7后面的被7整除的數.第一節(jié)數的整除性按以下步驟進行：18第一節(jié)數的整除性照以上步驟可以到素數2,3,5,7,11,

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

證明：存在無窮多個正整數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é)數的整除性例7證明：存在無窮多個正整數a，使得20第一節(jié)數的整除性例8設a1,a2,

,an是整數，且a1

a2

an

=0，a1a2

an

=n，則4

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

,an都是奇數。于是a1

a2

an是奇數個奇數之和，不可能等于零，這與題設矛盾，所以2

n，即在a1,a2,

,an中至少有一個偶數。

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

i

n）。此時有等式a2

an=

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

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

,an中至少有兩個偶數，即4

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

d(2)2

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

a22

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

1，a22=8A2

1，a32=8A3

1，于是a12

a22

a32=8(A1

A2

A3)

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