第一章 整數(shù)的可除性

第一章整數(shù)的可除性

《初等數(shù)論》美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

§1.1整數(shù)的除法

帶余除法定理

初等數(shù)論美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

定義1.1.1設(shè)a，b是整數(shù)，b

0，如果存在整數(shù)c，使得a=bc成立，則稱a被b整除，a是b的倍數(shù)，b是a的約數(shù)（因數(shù)或除數(shù)），并且使用記號ba；如果不存在整數(shù)c使得a=bc成立，則稱a不被b整除，記為ba。顯然每個非零整數(shù)a都有約數(shù)1，a，稱這四個數(shù)為a的平凡約數(shù)，a的另外的約數(shù)稱為非平凡約數(shù)。被2整除的整數(shù)稱為偶數(shù)，不被2整除的整數(shù)稱為奇數(shù)。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容定理1.1.1下面的結(jié)論成立：(ⅰ)ab

ab；(ⅱ)ab，bc

ac；(ⅲ)bai，i=1,2,,k

ba1x1

a2x2

akxk，此處xi（i=1,2,,k）是任意的整數(shù)；(ⅳ)ba

bcac，此處c是任意的非零整數(shù)；(ⅴ)ba，a

0|b||a|；ba且|a|<|b|

a=0。證明留作習(xí)題。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

定義1.1.2若整數(shù)a

0，1，并且只有約數(shù)1和a，則稱a是素數(shù)（或質(zhì)數(shù)）；否則稱a為合數(shù)。以后在本書中若無特別說明，素數(shù)總是指正素數(shù)。定理1.1.2任何大于1的整數(shù)a都至少有一個素約數(shù)。證明若a是素數(shù)，則定理是顯然的。若a不是素數(shù)，那么它有兩個以上的正的非平凡約數(shù)，設(shè)它們是d1,d2,,dk。不妨設(shè)d1是其中最小的。若d1不是素數(shù)，則存在e1>1，e2>1，使得d1=e1e2，因此，e1和e2也是a的正的非平凡約數(shù)。這與d1的最小性矛盾。所以d1是素數(shù)。證畢。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

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

a。證畢。例1.1.1設(shè)r是正奇數(shù)，證明：對任意的正整數(shù)n，有n

21r

2r

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

bk=(a

b)(ak

1

ak

2b

ak

3b2

bk

1)=(a

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

2r

nr，則2s=2(2r

nr)(3r

(n

1)r)

(nr

2r)=2(n

2)Q，其中Q是整數(shù)。若n

2s，由上式知n

22，因為n

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

2s。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

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

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

d(1997)是偶數(shù)。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

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

1，證明：(ⅰ)若2k

n<2k1，1

a

n，a2k，則2ka；(ⅱ)若3k2n

1<3k+1，1

b

n，2b

1

3k，則3k2b

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

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

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

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

1。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

例1.1.7證明：存在無窮多個正整數(shù)a，使得n4

a（n=1,2,3,）都是合數(shù)。解取a=4k4，對于任意的nN，有

n44k4=(n22k2)24n2k2=(n22k22nk)(n22k22nk)。因為n22k22nk=(n

k)2

k2

k2，所以，對于任意的k=2,3,

以及任意的nN，n4

a是合數(shù)。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

例1.1.8設(shè)a1,a2,,an是整數(shù)，且a1a2

an=0，a1a2an=n，則4n。解如果2n，則n,a1,a2,,an都是奇數(shù)。于是a1a2

an是奇數(shù)個奇數(shù)之和，不可能等于零，這與題設(shè)矛盾，所以2n，即在a1,a2,,an中至少有一個偶數(shù)。如果只有一個偶數(shù)，不妨設(shè)為a1，那么2ai（2in）。此時有等式a2

an=a1，在上式中，左端是(n1)個奇數(shù)之和，右端是偶數(shù)，這是不可能的，因此，在a1,a2,,an中至少有兩個偶數(shù)，即4n。

《初等數(shù)論》————————————————————————————————————————

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

例1.1.9若n是奇數(shù)，則8n21。解設(shè)n=2k

1，則

n21=(2k

1)21=4k(k

1)。在k和k

1中有一個是偶數(shù)，所以8n21。例9的結(jié)論雖然簡單，卻是很有用的。例如，使用例3中的記號，我們可以提出下面的問題：問題d(1)2

d(2)2

d(1997)2被4除的余數(shù)是多少？

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

下面，我們要介紹帶余數(shù)除法及其簡單應(yīng)用。定理1.1.3(帶余數(shù)除法)設(shè)a與b是兩個整數(shù)，b

0，則存在唯一的兩個整數(shù)q和r，使得

a=bq

r，0

r<|b|。(1)

證明存在性若ba，a=bq，qZ，可取r=0。若ba，考慮集合A={a

kb；kZ},其中Z表示所有整數(shù)的集合，以后，仍使用此記號，并以N表示所有正整數(shù)的集合。在集合A中有無限多個正整數(shù)，設(shè)最小的正整數(shù)是r=a

k0b，則必有

0<r<|b|，(2)否則就有r|b|。因為ba，所以r

|b|。于是r>|b|，即a

k0b>|b|，a

k0b

|b|>0，這樣，在集合A中，又有正整數(shù)a

k0b

|b|<r，這與r的最小性矛盾。所以式(2)必定成立。取q=k0知式(1)成立。存在性得證。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

唯一性假設(shè)有兩對整數(shù)q

，r

與q

，r

都使得式(1)成立，即a=q

b

r

=q

b

r

，0

r

,r

<|b|，則(q

q)b=r

r，|r

r|<|b|，(3)因此r

r=0，r=r，再由式(3)得出q

=q

，唯一性得證。證畢。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

定義1.1.3稱式(1)中的q是a被b除的商，r是a被b除的余數(shù)。由定理1可知，對于給定的整數(shù)b，可以按照被b除的余數(shù)將所有的整數(shù)分成b類。在同一類中的數(shù)被b除的余數(shù)相同。這就使得許多關(guān)于全體整數(shù)的問題可以歸化為對有限個整數(shù)類的研究。以后在本書中，除特別聲明外，在談到帶余數(shù)除法時總是假定b是正整數(shù)。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

例1.1.14設(shè)a0,a1,,anZ，f(x)=anxn

a1x

a0，已知f(0)與f(1)都不是3的倍數(shù)，證明：若方程f(x)=0有整數(shù)解，則3f(1)=a0

a1

a2

(1)nan

。解對任何整數(shù)x，都有x=3q

r，r=0，1或2，qZ。(ⅰ)若r=0，即x=3q，qZ，則f(x)=f(3q)=an(3q)n

a1(3q)

a0=3Q1

a0=3Q1

f(0)，其中Q1Z，由于f(0)不是3的倍數(shù)，所以f(x)0；(ⅱ)若r=1，即x=3q1，qZ，則f(x)=f(3q1)=an(3q1)n

a1(3q1)

a0=3Q2

an

a1

a0=3Q2

f(1)，其中Q2Z。由于f(1)不是3的倍數(shù)，所以f(x)0。因此若f(x)=0有整數(shù)解x，則必是x=3q2=3q

1，q

Z，于是0=f(x)=f(3q

1)=an(3q

1)n

a1(3q

1)

a0=3Q3

a0

a1

a2

(1)nan=3Q3

f(1)，其中Q3Z。所以3f(1)=a0

a1

a2

(1)nan。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

例1.1.15證明：對于任意的整數(shù)n，f(n)=3n5

5n3

7n被15整除。解對于任意的正整數(shù)n，記n=15q

r，0

r<15。由例1，n2=15Q1

r1，n4=15Q2

r2，其中r1與r2分別是r2與r4被15除的余數(shù)。以R表示3n4

5n2

7被15除的余數(shù)，則R就是3r2

5r1

7被15除的余數(shù)，而且f(n)被15除的余數(shù)就是rR被15除的余數(shù)，記為R。當r=0時，顯然R

=0，即153n5

5n3

7n。對于r=1,2,3,,14的情形，通過計算列出下表：

r=1,142,133,124,115,106,97,8r1=14911064r2=11611061R=0010012100R=0000000

這證明了結(jié)論。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

例1.1.16設(shè)n是奇數(shù)，則16n4

4n2

11。

解我們有

n4

4n2

11=(n21)(n2

5)

16。由第一節(jié)例題9，有8n21，由此及2n2

5得到16(n21)(n2

5)。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

習(xí)題1.11.證明：若m

pmn

pq，則m

pmq

np。

2.證明：任意給定的連續(xù)39個自然數(shù)，其中至少存在一個自然數(shù)，使得這個自然數(shù)的數(shù)字和能被11整除。

3.證明：存在無窮多個自然數(shù)n，使得n不能表示為a2

p（a>0是整數(shù)，p為素數(shù)）的形式。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容6.證明：12n4

2n3

11n2

10n，nZ。

7.設(shè)3a2

b2，證明：3a且3b。

8.設(shè)n，k是正整數(shù)，證明：nk與nk+4的個位數(shù)字相同。

9.證明：對于任何整數(shù)n，m，等式n2

(n1)2=m2

2不可能成立。

10.設(shè)a是自然數(shù)，問a43a29是素數(shù)還是合數(shù)？

§1.2最大公約數(shù)與

輾轉(zhuǎn)相除法

初等數(shù)論美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

定義1.2.1整數(shù)a1,a2,,ak的公共約數(shù)稱為a1,a2,,ak的公約數(shù)。不全為零的整數(shù)a1,a2,,ak的公約數(shù)中最大的一個叫做a1,a2,,ak的最大公約數(shù)（或最大公因數(shù)），記為(a1,a2,,ak)。由于每個非零整數(shù)的約數(shù)的個數(shù)是有限的，所以最大公約數(shù)是存在的，并且是正整數(shù)。如果(a1,a2,,ak)

=

1，則稱a1,a2,,ak是互素的（或互質(zhì)的）；如果(ai,aj)

=

1，1

i,j

k，i

j，則稱a1,a2,,ak是兩兩互素的（或兩兩互質(zhì)的）。顯然，a1,a2,,ak兩兩互素可以推出(a1,a2,,ak)=

1，反之則不然，例如(2,6,15)

=

1，但(2,6)=2。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

定理1.2.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或pa；(ⅴ)若a=bqr，則(a,b)

=

(b,r)。證明(ⅰ)(ⅳ)留作習(xí)題。

(ⅴ)由第一節(jié)定理1可知，如果da，db，則有dr=a

bq，反之，若db，dr，則da=bqr。因此a與b的全體公約數(shù)的集合就是b與r的全體公約數(shù)的集合，這兩個集合中的最大正數(shù)當然相等，即(a,b)

=

(b,r)。證畢。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

定理1.2.2設(shè)a1,a2,,akZ，記

A=

{y；y=，xiZ，

i

k}。如果y0是集合A中最小的正數(shù)，則y0

=

(a1,a2,,ak)。證明設(shè)d是a1,a2,,ak的一個公約數(shù)，則dy0，所以d

y0。另一方面，由第二節(jié)例2知，y0也是a1,a2,,ak的公約數(shù)。因此y0是a1,a2,,ak的公約數(shù)中的最大者，即y0

=

(a1,a2,,ak)。證畢。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

定理1.2.3(a1,a2,,ak)=1的充要條件是存在整數(shù)x1,x2,,xk，使得

a1x1a2x2

akxk=1。(1)

證明必要性由定理2得到。充分性若式(1)成立，如果(a1,a2,,ak)=d>1，那么由dai（1ik）推出da1x1a2x2

akxk=1，這是不可能的。所以有(a1,a2,,ak)=1。證畢。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

定理1.2.4對于任意的整數(shù)a，b，c，下面的結(jié)論成立：(ⅰ)由bac及(a,b)

=

1可以推出bc；(ⅱ)由bc，ac及(a,b)

=

1可以推出abc。證明(ⅰ)若(a,b)

=

1，由定理2，存在整數(shù)x與y，使得axby=

1。因此acxbcy=c。(2)由上式及bac得到bc。結(jié)論(ⅰ)得證；(ⅱ)若(a,b)

=

1，則存在整數(shù)x，y使得式(2)成立。由bc與ac得到abac，abbc，再由式(2)得到abc。結(jié)論(ⅱ)得證。證畢。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

推論1.2.4若p是素數(shù)，則下述結(jié)論成立：(ⅰ)pab

pa或pb；(ⅱ)pa2

pa。證明留作習(xí)題。推論1.2.5若(a,b)

=

1，則(a,bc)

=

(a,c)。證明設(shè)d是a與bc的一個公約數(shù)，則da，dbc，由式（2）得到，d|c,即d是a與c的公約數(shù)。另一方面，若d是a與c的公約數(shù)，則它也是a與bc的公約數(shù)。因此，a與c的公約數(shù)的集合，就是a與bc的公約數(shù)的集合，所以(a,bc)

=

(a,c)。證畢。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

定理1.2.5對于任意的n個整數(shù)a1,a2,,an，記(a1,a2)

=d2，(d2,a3)

=d3，，(dn2,an1)

=dn1，(dn1,an)

=dn，則

dn=

(a1,a2,,an)。證明由定理2的推論，我們有

dn=

(dn1,an)

dnan，dndn1，dn1

=

(dn2,an1)

dn1an1，dn1dn2，

dnan，dnan1，dndn2，dn2

=

(dn3,an2)

dn2an2，dn2dn3

dnan，dnan1，dnan2，dndn3，

d2

=

(a1,a2)dnan，dnan1，，dna2，dna1，即dn是a1,a2,,an的一個公約數(shù)。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

另一方面，對于a1,a2,,an的任何公約數(shù)d，由定理2的推論及d2,,dn的定義，依次得出

da1，da2

dd2，

dd2，da3

dd3，

ddn1，dan

ddn，因此dn是a1,a2,,an的公約數(shù)中的最大者，即dn=

(a1,a2,,an)。證畢。

美麗有兩種一是深刻又動人的方程

一是你泛著倦意淡淡的笑容

例1.2.1證明：若n是正整數(shù)，則是既約分數(shù)。解由定理1得到(21n4,14n3)=(7n1,14n3)=(7n1,1)=1。注：一般地，若(x,y)=1，那么，對于任意的整數(shù)a，b，有(x,y)=(xay,y)=(xay,yb(xay))=(xay,(ab1)ybx)，因此，是既約分數(shù)。例1.2.2證明：121n22n12，nZ。解由于121=112，n22n12=(n1)211，所以，若112(n1)211，(3)則11(n1)2，因此，由定理4的推論1得到11n1，1