初等數(shù)論期末復(fù)習(xí)資料

§1

是整數(shù),且

b≠0,如果有整數(shù)

q,使得

a=bq,則稱

a,記為

b|a,也稱

的因數(shù),a

的倍數(shù).

q,使得

a=bq,則稱

a,記為

a.例如

3，

在中小學(xué)數(shù)學(xué)里,整除概念中的整數(shù)是正整數(shù),今天講的整除中的整數(shù)可正可負(fù).

b|a？當(dāng)

的數(shù)值較大時,可借助計算器判別.

的商數(shù)是整數(shù),說明

b|a;如果

的商不是整數(shù),說明

b|a？(1)

(1)如果

(2)如果

d|a,d|b,那么對任意整數(shù)

m,n,都有

(3)如果

,,

L

,

n

的倍數(shù),

q

,q,

L

,q

n

是任意整數(shù),那么q

q

L

q

n

n

的倍數(shù).(4)如果

cd|ab。

2×3|4×(-6).

個連續(xù)整數(shù)的乘積,一定可被

整除.

個連續(xù)整數(shù)的乘積,一定可被

整除.2.帶余除法

是整數(shù),且

b>0,那么有唯一一對整數(shù)

a=bq+r,0≤r＜

b

的商,r

的余數(shù).例如-5=3×(-2)+1 5=3×1+2 -5=(-3)×2+15=(-3)×(-1)+2 15=(-5)×(-3), -24=(-2)×12.事實(shí)上,以

的余數(shù)也可以是負(fù)的.例如-5=3×(-1)-2=3×(-2)+1.

的余數(shù),也稱為模運(yùn)算(取余):mod.可用計算器進(jìn)行.具體操作:輸入

a-按

mod(取余)鍵-輸入

b-按=鍵得出余數(shù).如果

的余數(shù)=0,則

b|a;如果

的余數(shù)≠0,則

利用計算器求余數(shù):

整除的整數(shù)稱為偶數(shù).如,0,4,10,-6,-8

都是偶數(shù).

整除的整數(shù)稱為奇數(shù).如,-5,-3,1,7,11

都是奇數(shù).

是整數(shù));奇數(shù)的形式為

是整數(shù)).奇數(shù)、偶數(shù)的性質(zhì):

偶數(shù)±偶數(shù)=偶數(shù),奇數(shù)±奇數(shù)=偶數(shù),奇數(shù)±偶數(shù)=奇數(shù),偶數(shù)×偶數(shù)=偶數(shù),偶數(shù)×奇數(shù)=偶數(shù),奇數(shù)×奇數(shù)=奇數(shù).

是任意兩個整數(shù),則

同奇同偶.

個整數(shù),而且

b

,證明

是偶數(shù).

是任一奇數(shù),試證明

是正整數(shù),證明形如

整數(shù)不是完全平方數(shù).

a,設(shè)

a=3q±1,于是

q

q

±6q+1=3(3

q

±2q)+1.

≠3n-1,故

不是完全平方數(shù).

是正整數(shù),證明形如

4n-1、4n+2

的整數(shù)都不是完全平方數(shù).§2

1.最大公因數(shù)、輾轉(zhuǎn)相除法幾個數(shù)的公有因數(shù)叫做這幾個數(shù)的公因數(shù).公因數(shù)中最大的整數(shù)稱為這幾個數(shù)的最大公因數(shù).(1)幾個數(shù):不能確定;(2)因數(shù)、公因數(shù):都是正整數(shù);

最大公因數(shù):沒有專門的符號.,

,L

,

都是整數(shù),d≠0,如果

d

i

…,n,稱

,

,

L

,

,

,L

,

的公因數(shù),

.記為,

,L

,

,

,L

,

n

.如果

,

,L

,

在中小學(xué)數(shù)學(xué)里,求正整數(shù)

(1)觀察法；(2)將

的所有公因數(shù)都求出來,再從中挑最大的；(3)用短除法.輾轉(zhuǎn)相除法:

是正整數(shù),而且有a

bq r

,0

r b

rq

r

,0

r

r;

r

rq r,0

r

r

;1 2

3 3 3 2 （*）r r

q

r,0

r

r

;n2 n1

n n n n1n

1

n

n

1

用輾轉(zhuǎn)相除法求(123,78),練習(xí):用輾轉(zhuǎn)相除法求(66,54).下面說明輾轉(zhuǎn)相除法的正確性.先證明

0,而且有整數(shù)

、(b,c)都存在.因(a,b)|a,(a,b)|b,c=a-bq,

得(a,b)|c,又得(a,b)≤(b,c);反之,由(b,c)|b,(b,c)|c,a=bq+c,

得(b,c)|a,(b,c)≤(a,b).所以(a,b)=(b,c).

b

r

r

L

r

r

0,

(b,r)

)1 1 2

…=

n1

n1

2.最大公因數(shù)的性質(zhì)

短除法的根據(jù))

求(84,90),(120,36).

求(-84,120),(-120,-72),(24,-60,-96).3n

是任意整數(shù),證明

5n

是既約分?jǐn)?shù).

互質(zhì).

r

b

§3

1.整除的進(jìn)一步性質(zhì)

不全為零,那么有

s,t∈Z

將(*)中每式中的余數(shù)解出得r

r r

q r

r

r

q

r

bq

r

,r

,L

,r

,r r

r

r

q

用輾轉(zhuǎn)相除法求(120,54),

解∵120=2×54+12,54=12×4+6,12=6×2,∴(120,54)=6.12=120-2×54,6=54-12×4=54-(120-2×54)×4=120×(-4)+54×9.

用輾轉(zhuǎn)相除法求(84,45),并求整數(shù)

都是正整數(shù),問

①求(12,18)及

r

通過這個例子,請同學(xué)們觀察最大公因數(shù)與公因數(shù)有何關(guān)系？能否提出自己的猜想？能否證明自己的猜想？

的最大公因數(shù),那么,a,b

的因數(shù).

d=(a,b),由性質(zhì)

u,v∈Z

的任一公因數(shù),則

b,

d=(a,b),則(

d d

(a,c)=1,且

c|ab,則

(a,c)=1,則(ab,c)=(b,c).

(a,b)=1,且

,

,L

,

中每一個數(shù)的倍數(shù),則稱

的公倍中最小正整數(shù)稱為

,

,L

的公倍中最小正整數(shù)稱為

,

,L

,

的一個公倍數(shù).

,

,L

,

的最小公倍數(shù).用

,

,L

,

]來表示.

|,…,|

,

,L

,

是兩個正整數(shù),則

的任一公倍數(shù)是[a,b]的倍數(shù)；

(

,b

)

.而且若(a,b)=1,則[a,b]=ab.證明(i)設(shè)

的任一公倍數(shù),而且

,因

m,[a,b]都是

的公倍數(shù),由

的公倍數(shù),若

則這與[a,b]的最小性矛盾.故

,b(ii)記

,

b

,則

是整數(shù),由

d b b

,bd

d|a,d|b,即

的公因數(shù). b d

b

的任一公因數(shù),由

,即,

b

,所以

從而(a,b)=

,b

,

,L

,

都是正整數(shù),令,

m

m,

m ,…,

m

,

m

,

,L

,

m

n

n

,

,L

,

n(≥2)個正整數(shù),且兩兩互素,則[,

,L

,

]

L

n

求[123,456,-789]

a,b,滿足:a+b=120,(a,b)=24,[a,b]=144.

是正整數(shù),則[a,b,c]=

(

,

,

)作業(yè):P14:1.2.求(84,45),

§4

1.質(zhì)數(shù)

a>1,如果

外再無其它正因數(shù),則稱

為質(zhì)數(shù),也稱為素數(shù).否則,稱

為合數(shù).

都是質(zhì)數(shù)，4,6,8,9,10

都是合數(shù).

個,1-1000

個,100

個.

a>1,則

是素數(shù),而且當(dāng)

是合數(shù)時,q≤

是合數(shù),設(shè)

b|q,q|a,得

b|a,但

1<b<q,這與

的最小正因數(shù)矛盾.故

是素數(shù).

是合數(shù),設(shè)

a=qm,由

a=qm≥qq,即

q≤

a>1,不超過

p,p

,L

,p

,如果

p

i

a,i=1,…,k,則

為素數(shù).

素數(shù)判別威爾遜定理:

p>1,那么

都是素數(shù).

較大時,(p-1)!+1

的數(shù)值非常大,在實(shí)際運(yùn)用時不可行。

是素數(shù),a

為任一整數(shù),則或

P|a,或(P,a)=1.

因(P,a)|P,P

為素數(shù),所以(P,a)=P,或(P,a)=1.即

P|a,或(P,a)=1.2.整數(shù)的唯一分解定理

的整數(shù)都有標(biāo)準(zhǔn)分解式:a=

p

p

L

p

p,p

,L

,p

為不同素數(shù),整數(shù)

i

,i=1,…,k.

p

p

L

p

p

p

p

L

p

i

i

…,k.而且

L

個.

ppL

p

p

p

L

p

i

i

,i=1,…,k.

ppL

p

ppL

p

,

,

i i i i i i

L

個;

L

個.

的標(biāo)準(zhǔn)分解式,并求它們的最大公因數(shù)和最小公倍數(shù).

×5×11×41,

×3×

所以(725760,154200)=

×5,

×3×

×11×41×257.

求下列各組數(shù)的最大公因數(shù)及其公因數(shù)的個數(shù):練習(xí):求下列各組數(shù)的最大公因數(shù)及其公因數(shù)的個數(shù):

的素數(shù),證明

qpq

,令

M

,令

M

p

p

L

p

反證法,設(shè)質(zhì)數(shù)只有

個:

p,p

,L

,p

M>1,于是

p.因

pi

…,k,p|M,所以

p≠

pi

1,2,…,k.這就是說,

p,p

,L

,p

個不同素數(shù).這與假設(shè)矛盾.

(1)刪去

1，剩下的后面的第一個數(shù)是

2，2

(2)刪去

整除的數(shù)(從

開始),2

(3)刪去

整除的數(shù)(從

開始),3

(4)刪去

整除的數(shù)(從

開始),5

現(xiàn)在表中剩下的就全為素數(shù)了:對較小范圍內(nèi)的素數(shù)以上求法方便,對較大范圍內(nèi)的素數(shù),需要編程求素數(shù)了.現(xiàn)在運(yùn)行程序,求較大范圍內(nèi)的素數(shù).找兩個同學(xué)來求.作業(yè):1.判別

是否為素數(shù);2.P19:5t3.求

的標(biāo)準(zhǔn)分解式,并求它們的最大公因數(shù)和最小公倍數(shù),并求它們的所有公因數(shù)的個數(shù)?！?

函數(shù)[x],{x}

函數(shù)[x],{x}

是實(shí)數(shù),以[x]表示不超過

的整數(shù)部分，又稱{x}

[x]為

是實(shí)數(shù),則[y]；(2)若

是整數(shù),[x]；(3)若

x<1,則[x]=0； [

]

{

}(4)(帶余除法)設(shè)

是整數(shù),且

b>0,則

b

b

r r

q

[

] {

}

[

]

{

}

b b

,故

b

b b,所以

b

b

[

](5)設(shè)

是正整數(shù),則

b

[

]

,因此,若數(shù)

個,則

b

b

例2

的倍數(shù)的正整數(shù)有[

的倍數(shù)的正整數(shù)有[

函數(shù)[x]的應(yīng)用

p

是素數(shù),n

是整數(shù),如果

p

│n,

p

p

例3設(shè)

p

是素數(shù),那么在

的整數(shù)中,恰好被

p

n!的標(biāo)準(zhǔn)分解式中,質(zhì)因數(shù)

p

p

p

]+…

整除的整數(shù)有[

p

p

]個;

整除的整數(shù)有[

p

p

]個;

pp

整除的整數(shù)有[ ppprpr

整除的整數(shù)有[

p

r

]個,…,于是

p

p

p

pp

p

p

])+…+r([

pr

p

r

])+…=[

p

p

p

]+….

p

r

pr

50!的標(biāo)準(zhǔn)分解式中,素數(shù)

的指數(shù),并確定

50!的十進(jìn)制數(shù)的末尾

的個數(shù).

的整數(shù)中,求

的倍數(shù)的整數(shù)的個數(shù).

2:60!的十進(jìn)制數(shù)的末尾

的個數(shù).

2t,求

100!的十進(jìn)制數(shù)的末尾

的個數(shù).

1.二元一次不定方程概念

百雞問題:“雞翁一,值錢五,雞母一,值錢

3,雞雛三,值錢一.百錢買百雞,問雞翁、雞母、雞雛各幾何？”

只、y

只.依題意得

都是非負(fù)整數(shù).14x+8y=200

稱為二元一次不定方程.

∈Z).如果整數(shù)

的一組整數(shù)解,ax+by=c

的一組已知整數(shù)解,也稱為特解.2.二元一次不定方程解法

有整數(shù)解的充分必要條件是,(a,b)|c.

m,n,則

am+bn=c,因?yàn)?a,b)|a,(a,b)|b,

即(a,b)|c.反之,若(a,b)|c,

由第一章§3

m,n,則方程的一切整數(shù)解為

∈Z,或

∈Z.

t∈Z,由(2)得到的整數(shù)

都是方程(1)的解.

是(1)的任一整數(shù)解,于是

因?yàn)?a,b)=1,

b|(x-m),設(shè)

3.例子與應(yīng)用

的一切整數(shù)解和所有非負(fù)整數(shù)解.

的一切整數(shù)解.

L

N

n

n

,

,L

,n,N

.n≥2

是整數(shù).

不定方程(1)有整數(shù)解充分必要條件是,(

,

,L

,

n

的一切整數(shù)解.

所以不定方程有整數(shù)解,因(9,24)=3,可設(shè)

∈Z,②的通解為

寫成分母兩兩互質(zhì)的三個既約分?jǐn)?shù)之和.

60=3×4×5,

因(20,15,12=1,

.當(dāng)

作業(yè):1

的一切整數(shù)解.§3

1.不定方程

1.不定方程

的一組整數(shù)解(x,y,z)稱為一組勾股數(shù).

例如,(3,4,5),(6,8,10),(9,12,15),(8,15,17)等都是勾股數(shù).

一切正整數(shù)解可由下式表出：x=2ab,y=

b

b

一奇一偶.

②a=3,b=2,x=12,y=5,z=13;

⑥a=5,b=4,x=40,y=9,z=41.2.其它不定方程作業(yè):1.寫出不定方程

作業(yè):1.寫出不定方程

x=±1

y=±6,或

x=±6,且

y=±1,或

x=±2,且

y=±3,或

x=±3,且

y=±2。②原方程可變?yōu)?x+1)(y-1)-3=0,

x+1=±1

y-1=±3,或

x+1=±3,且

y-1=±1.故得不定方程的全部整數(shù)解為 2.求不定方程

的全部整數(shù)解.

§1

1.同余及性質(zhì)

是正整數(shù),稱

為模.a,b∈Z,如果

除所得的余數(shù)相同,則稱

同余,記為

a≡b(modm).如果

得的余數(shù)不同,則稱

不同余,記為

4≡7(mod3),6

同余的充分必要條件是,m|a-b,即

∈Z.

必要性,若

a≡b(modm).

∈Z,則

T=s-u∈Z.所以

m|a-b,且

充分性,設(shè)

r充分性,設(shè)

r

r

m|a-b,所以

r

,但|r

<m.從而

<m.從而

,即

甲:a≡b(modm).乙:若

a≡b(modm),b丙:若

a≡b(modm),b

a≡c(modm).丁、戊:

b

m),

bm),

b

b

m),

bb

m)

由此可得,若

b

m),

bm),L

,

bm)

L

b

b

L

b

m),

L

bb

L

b

m)

2.同余的應(yīng)用

i

L

i

L

,,

i ni

n

n

L

n

L

i

L

i

L

,,

i ni

L

(

L

(

L

n

L

n

L

(

56,所以

作業(yè)：1.p53:2.§2

1.模

是正整數(shù),Z

是整數(shù)集,令K

∈Z},r=0,1,…,m-1,則KK,…,Km

的剩余類.易知,

a,b∈K

,則

a≡b(modm).稱

K

中其它數(shù)的剩余.

K…,m-1,稱,…,m

的完全剩余系.

是正整數(shù),0,1,…,m-1

的非負(fù)最小完全剩余系.

m,

m,

L

,L

,

L

,L

,

m

m

m

m

稱為模

的絕對最小完全剩余系；m

為奇數(shù)

m

m

,L

,L

,

的絕對最小完全剩余系.

m=6,模

KKK

KK

K

的一個完全剩余系,1,2,3,4,5,6

系.-3,-2,-1,0,1,2;-2,-1,0,1,2,3

的完全剩余系,稱為模

的絕對最小完全剩余系.例2

的非負(fù)最小完全剩余系和絕對最小完全剩余系.2.完全剩余系的判定

,…, m

m

兩兩不同余.

,…,

,…,

m

的一個完全剩余系,則

b

b

b

bm

的一個完全剩余系.

j≠i,m

(

)j

i

,因?yàn)?/p>

j

b(i

b)

(

j

i)

,且(a,m)=1,

b

b

b

bj i

b

bj i,所以

j

b(i

b

bj i

,…,

bm

全剩余系.

的一組完全剩余系,它的每一個數(shù)都是偶數(shù);

的一組完全剩余系,它的每一個數(shù)都是奇數(shù).作業(yè)：1.分別寫出模

的非負(fù)最小完全剩余系、絕對最小完全剩余系.

1.簡化剩余系、歐拉函數(shù)K

互質(zhì),則稱這個剩余類為與模

互質(zhì)的.

互質(zhì)的全部剩余類,從每一類里任取一數(shù)組成的集合,叫做模

的簡化剩余系.

時,KK

互質(zhì)的剩余類,1,5

的簡化剩余系.m=8

KKK

的簡化剩余系.

是正整數(shù),歐拉函數(shù)

互質(zhì)的整數(shù)的個數(shù).

m2.簡化剩余系的判定

K

a∈Z,使得(a,m)=1.

m.模

的每一個簡化剩余系,是

m個整數(shù)組成.

,…,

(m)

,…,

(m)

的一個簡化剩余系,則

,…,

(m)

的一個簡化剩余系.

m

m是互質(zhì)的兩個正整數(shù),分別通過模的簡化剩余系,則

m

m

m

m

的簡化剩余系.

是互質(zhì)的兩個正整數(shù),則

是互質(zhì)的兩個正整數(shù),則

m

(m

m

)

(m

)

(m

)

p

p

L

p

,則 (p

p

(p

L

p (p

p

(p

L

p

)

L

)p

p

p

1,2,…,p-1,p,p+1,……,p

p

p

-1)+1,…,

p

p

p

p

p

1.歐拉定理

a,m∈Z,m>1,(a,m)=1,

m

m)m

b

,

b

,

,

b

,(

(m))

,由于(m)=1,由§3

知,

,,

,

m

()(

)L

()bb

L

b

m)

,即

(m)bb

L

b

bb

L

b

m)

,因(m,bi

(m))=1,從而1,2,…,

(m))=1,從而

b

,

b

,L

,

b

m

m).證畢。推論(費(fèi)爾瑪定理)設(shè)

是素數(shù),則

P),而且

a∈Z,

P)

|a,則

，若(m)=1，則

P)

P)

是不同的素數(shù),證明q

p

q

是不同的素數(shù),所以(p,q)=1,由費(fèi)爾瑪定理知,q

p

q

q

p

q

由同余的性質(zhì)得,q

p

q

p≠2,5

為素數(shù),整數(shù)

位,而且每一位上的數(shù)字都是

9,證明

p≠2,5

為素數(shù),所以(10,p)=1,由費(fèi)爾瑪定理得,a=99…9=

≡0(modp),即

取整數(shù)時,多項式

b

b

L

b

的值總為整數(shù),則稱

為整值多項式.證明,

是整值多項式.

2730=2×3×5×7×13,當(dāng)

取整數(shù)值時,由費(fèi)爾瑪定理,

(

)(

(

)(

(

)(

(

)(

L

兩兩互質(zhì),由整除的性質(zhì)知,2×3×5×7×13|

.故

是整值多項式.

g

(mod6)。

，k

為正整數(shù),于是

作業(yè):P64:1.

2.分?jǐn)?shù)與循環(huán)小數(shù)

L

nL

n

{0,1，…,9}）從任何一位數(shù)后不全為

s≥0,t＞0,使得

i

i

,i=1,2,…,t,k=0,1,2,

L

L

對滿足(*)的最小正整數(shù)

對滿足(*)的最小正整數(shù)

L

為循環(huán)節(jié)的長度.若最小的

s=0,那小數(shù)就叫做純循環(huán)小數(shù)，否則叫做混循環(huán)

b

能表成純循環(huán)小數(shù)的充分必要條件是,(b,10)=1.

b

是純有限小數(shù)的充分必要條件是(b,10)≠1.

b

b

b

L

L

L

L

gL

L

L

.于是

b

.所以

bq,因(a,b)=1,所以

,設(shè)

=qb,則

qb=1,故(b,10)=1.b

L

L

L

L

b

qb

qb

q

b

L

,顯然

,

,L

,

9,也不全為

L

qb

L

qb

b

b

b

b

b

b

L

L

L

L

b

b

L

L

g g b

gb

,

, (b

b

,

§1基本的概念及一次同余方程1.同余方程的概念

L

,這里i

,i=0,1,…,n.m

是正整數(shù),則稱

L

為同余式,或模

的同余方程.

稱為同余方程(1)的次數(shù).若

a∈Z

f(a)≡0(modm),x≡a(m