初等数论期末复习资料

§1

是整数,且

b≠0,如果有整数

q,使得

a=bq,则称

a,记为

b|a,也称

的因数,a

的倍数.

q,使得

a=bq,则称

a,记为

a.例如

3，

在中小学数学里,整除概念中的整数是正整数,今天讲的整除中的整数可正可负.

b|a？当

的数值较大时,可借助计算器判别.

的商数是整数,说明

b|a;如果

的商不是整数,说明

b|a？(1)

(1)如果

(2)如果

d|a,d|b,那么对任意整数

m,n,都有

(3)如果

,,

L

,

n

的倍数,

q

,q,

L

,q

n

是任意整数,那么q

q

L

q

n

n

的倍数.(4)如果

cd|ab。

2×3|4×(-6).

个连续整数的乘积,一定可被

整除.

个连续整数的乘积,一定可被

整除.2.带余除法

是整数,且

b>0,那么有唯一一对整数

a=bq+r,0≤r＜

b

的商,r

的余数.例如-5=3×(-2)+1 5=3×1+2 -5=(-3)×2+15=(-3)×(-1)+2 15=(-5)×(-3), -24=(-2)×12.事实上,以

的余数也可以是负的.例如-5=3×(-1)-2=3×(-2)+1.

的余数,也称为模运算(取余):mod.可用计算器进行.具体操作:输入

a-按

mod(取余)键-输入

b-按=键得出余数.如果

的余数=0,则

b|a;如果

的余数≠0,则

利用计算器求余数:

整除的整数称为偶数.如,0,4,10,-6,-8

都是偶数.

整除的整数称为奇数.如,-5,-3,1,7,11

都是奇数.

是整数);奇数的形式为

是整数).奇数、偶数的性质:

偶数±偶数=偶数,奇数±奇数=偶数,奇数±偶数=奇数,偶数×偶数=偶数,偶数×奇数=偶数,奇数×奇数=奇数.

是任意两个整数,则

同奇同偶.

个整数,而且

b

,证明

是偶数.

是任一奇数,试证明

是正整数,证明形如

整数不是完全平方数.

a,设

a=3q±1,于是

q

q

±6q+1=3(3

q

±2q)+1.

≠3n-1,故

不是完全平方数.

是正整数,证明形如

4n-1、4n+2

的整数都不是完全平方数.§2

1.最大公因数、辗转相除法几个数的公有因数叫做这几个数的公因数.公因数中最大的整数称为这几个数的最大公因数.(1)几个数:不能确定;(2)因数、公因数:都是正整数;

最大公因数:没有专门的符号.,

,L

,

都是整数,d≠0,如果

d

i

…,n,称

,

,

L

,

,

,L

,

的公因数,

.记为,

,L

,

,

,L

,

n

.如果

,

,L

,

在中小学数学里,求正整数

(1)观察法；(2)将

的所有公因数都求出来,再从中挑最大的；(3)用短除法.辗转相除法:

是正整数,而且有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

用辗转相除法求(123,78),练习:用辗转相除法求(66,54).下面说明辗转相除法的正确性.先证明

0,而且有整数

、(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.最大公因数的性质

短除法的根据)

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

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

是任意整数,证明

5n

是既约分数.

互质.

r

b

§3

1.整除的进一步性质

不全为零,那么有

s,t∈Z

将(*)中每式中的余数解出得r

r r

q r

r

r

q

r

bq

r

,r

,L

,r

,r r

r

r

q

用辗转相除法求(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.

用辗转相除法求(84,45),并求整数

都是正整数,问

①求(12,18)及

r

通过这个例子,请同学们观察最大公因数与公因数有何关系？能否提出自己的猜想？能否证明自己的猜想？

的最大公因数,那么,a,b

的因数.

d=(a,b),由性质

u,v∈Z

的任一公因数,则

b,

d=(a,b),则(

d d

(a,c)=1,且

c|ab,则

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

(a,b)=1,且

,

,L

,

中每一个数的倍数,则称

的公倍中最小正整数称为

,

,L

的公倍中最小正整数称为

,

,L

,

的一个公倍数.

,

,L

,

的最小公倍数.用

,

,L

,

]来表示.

|,…,|

,

,L

,

是两个正整数,则

的任一公倍数是[a,b]的倍数；

(

,b

)

.而且若(a,b)=1,则[a,b]=ab.证明(i)设

的任一公倍数,而且

,因

m,[a,b]都是

的公倍数,由

的公倍数,若

则这与[a,b]的最小性矛盾.故

,b(ii)记

,

b

,则

是整数,由

d b b

,bd

d|a,d|b,即

的公因数. b d

b

的任一公因数,由

,即,

b

,所以

从而(a,b)=

,b

,

,L

,

都是正整数,令,

m

m,

m ,…,

m

,

m

,

,L

,

m

n

n

,

,L

,

n(≥2)个正整数,且两两互素,则[,

,L

,

]

L

n

求[123,456,-789]

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

是正整数,则[a,b,c]=

(

,

,

)作业:P14:1.2.求(84,45),

§4

1.质数

a>1,如果

外再无其它正因数,则称

为质数,也称为素数.否则,称

为合数.

都是质数，4,6,8,9,10

都是合数.

个,1-1000

个,100

个.

a>1,则

是素数,而且当

是合数时,q≤

是合数,设

b|q,q|a,得

b|a,但

1<b<q,这与

的最小正因数矛盾.故

是素数.

是合数,设

a=qm,由

a=qm≥qq,即

q≤

a>1,不超过

p,p

,L

,p

,如果

p

i

a,i=1,…,k,则

为素数.

素数判别威尔逊定理:

p>1,那么

都是素数.

较大时,(p-1)!+1

的数值非常大,在实际运用时不可行。

是素数,a

为任一整数,则或

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

因(P,a)|P,P

为素数,所以(P,a)=P,或(P,a)=1.即

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

的整数都有标准分解式:a=

p

p

L

p

p,p

,L

,p

为不同素数,整数

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

个.

的标准分解式,并求它们的最大公因数和最小公倍数.

×5×11×41,

×3×

所以(725760,154200)=

×5,

×3×

×11×41×257.

求下列各组数的最大公因数及其公因数的个数:练习:求下列各组数的最大公因数及其公因数的个数:

的素数,证明

qpq

,令

M

,令

M

p

p

L

p

反证法,设质数只有

个:

p,p

,L

,p

M>1,于是

p.因

pi

…,k,p|M,所以

p≠

pi

1,2,…,k.这就是说,

p,p

,L

,p

个不同素数.这与假设矛盾.

(1)删去

1，剩下的后面的第一个数是

2，2

(2)删去

整除的数(从

开始),2

(3)删去

整除的数(从

开始),3

(4)删去

整除的数(从

开始),5

现在表中剩下的就全为素数了:对较小范围内的素数以上求法方便,对较大范围内的素数,需要编程求素数了.现在运行程序,求较大范围内的素数.找两个同学来求.作业:1.判别

是否为素数;2.P19:5t3.求

的标准分解式,并求它们的最大公因数和最小公倍数,并求它们的所有公因数的个数。§5

函数[x],{x}

函数[x],{x}

是实数,以[x]表示不超过

的整数部分，又称{x}

[x]为

是实数,则[y]；(2)若

是整数,[x]；(3)若

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

]

{

}(4)(带余除法)设

是整数,且

b>0,则

b

b

r r

q

[

] {

}

[

]

{

}

b b

,故

b

b b,所以

b

b

[

](5)设

是正整数,则

b

[

]

,因此,若数

个,则

b

b

例2

的倍数的正整数有[

的倍数的正整数有[

函数[x]的应用

p

是素数,n

是整数,如果

p

│n,

p

p

例3设

p

是素数,那么在

的整数中,恰好被

p

n!的标准分解式中,质因数

p

p

p

]+…

整除的整数有[

p

p

]个;

整除的整数有[

p

p

]个;

pp

整除的整数有[ ppprpr

整除的整数有[

p

r

]个,…,于是

p

p

p

pp

p

p

])+…+r([

pr

p

r

])+…=[

p

p

p

]+….

p

r

pr

50!的标准分解式中,素数

的指数,并确定

50!的十进制数的末尾

的个数.

的整数中,求

的倍数的整数的个数.

2:60!的十进制数的末尾

的个数.

2t,求

100!的十进制数的末尾

的个数.

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

百鸡问题:“鸡翁一,值钱五,鸡母一,值钱

3,鸡雏三,值钱一.百钱买百鸡,问鸡翁、鸡母、鸡雏各几何？”

只、y

只.依题意得

都是非负整数.14x+8y=200

称为二元一次不定方程.

∈Z).如果整数

的一组整数解,ax+by=c

的一组已知整数解,也称为特解.2.二元一次不定方程解法

有整数解的充分必要条件是,(a,b)|c.

m,n,则

am+bn=c,因为(a,b)|a,(a,b)|b,

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

由第一章§3

m,n,则方程的一切整数解为

∈Z,或

∈Z.

t∈Z,由(2)得到的整数

都是方程(1)的解.

是(1)的任一整数解,于是

因为(a,b)=1,

b|(x-m),设

3.例子与应用

的一切整数解和所有非负整数解.

的一切整数解.

L

N

n

n

,

,L

,n,N

.n≥2

是整数.

不定方程(1)有整数解充分必要条件是,(

,

,L

,

n

的一切整数解.

所以不定方程有整数解,因(9,24)=3,可设

∈Z,②的通解为

写成分母两两互质的三个既约分数之和.

60=3×4×5,

因(20,15,12=1,

.当

作业:1

的一切整数解.§3

1.不定方程

1.不定方程

的一组整数解(x,y,z)称为一组勾股数.

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

一切正整数解可由下式表出：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.其它不定方程作业:1.写出不定方程

作业:1.写出不定方程

x=±1

y=±6,或

x=±6,且

y=±1,或

x=±2,且

y=±3,或

x=±3,且

y=±2。②原方程可变为(x+1)(y-1)-3=0,

x+1=±1

y-1=±3,或

x+1=±3,且

y-1=±1.故得不定方程的全部整数解为 2.求不定方程

的全部整数解.

§1

1.同余及性质

是正整数,称

为模.a,b∈Z,如果

除所得的余数相同,则称

同余,记为

a≡b(modm).如果

得的余数不同,则称

不同余,记为

4≡7(mod3),6

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

∈Z.

必要性,若

a≡b(modm).

∈Z,则

T=s-u∈Z.所以

m|a-b,且

充分性,设

r充分性,设

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.同余的应用

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,所以

作业：1.p53:2.§2

1.模

是正整数,Z

是整数集,令K

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

的剩余类.易知,

a,b∈K

,则

a≡b(modm).称

K

中其它数的剩余.

K…,m-1,称,…,m

的完全剩余系.

是正整数,0,1,…,m-1

的非负最小完全剩余系.

m,

m,

L

,L

,

L

,L

,

m

m

m

m

称为模

的绝对最小完全剩余系；m

为奇数

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

的非负最小完全剩余系和绝对最小完全剩余系.2.完全剩余系的判定

,…, m

m

两两不同余.

,…,

,…,

m

的一个完全剩余系,则

b

b

b

bm

的一个完全剩余系.

j≠i,m

(

)j

i

,因为

j

b(i

b)

(

j

i)

,且(a,m)=1,

b

b

b

bj i

b

bj i,所以

j

b(i

b

bj i

,…,

bm

全剩余系.

的一组完全剩余系,它的每一个数都是偶数;

的一组完全剩余系,它的每一个数都是奇数.作业：1.分别写出模

的非负最小完全剩余系、绝对最小完全剩余系.

1.简化剩余系、欧拉函数K

互质,则称这个剩余类为与模

互质的.

互质的全部剩余类,从每一类里任取一数组成的集合,叫做模

的简化剩余系.

时,KK

互质的剩余类,1,5

的简化剩余系.m=8

KKK

的简化剩余系.

是正整数,欧拉函数

互质的整数的个数.

m2.简化剩余系的判定

K

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

m.模

的每一个简化剩余系,是

m个整数组成.

,…,

(m)

,…,

(m)

的一个简化剩余系,则

,…,

(m)

的一个简化剩余系.

m

m是互质的两个正整数,分别通过模的简化剩余系,则

m

m

m

m

的简化剩余系.

是互质的两个正整数,则

是互质的两个正整数,则

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).证毕。推论(费尔玛定理)设

是素数,则

P),而且

a∈Z,

P)

|a,则

，若(m)=1，则

P)

P)

是不同的素数,证明q

p

q

是不同的素数,所以(p,q)=1,由费尔玛定理知,q

p

q

q

p

q

由同余的性质得,q

p

q

p≠2,5

为素数,整数

位,而且每一位上的数字都是

9,证明

p≠2,5

为素数,所以(10,p)=1,由费尔玛定理得,a=99…9=

≡0(modp),即

取整数时,多项式

b

b

L

b

的值总为整数,则称

为整值多项式.证明,

是整值多项式.

2730=2×3×5×7×13,当

取整数值时,由费尔玛定理,

(

)(

(

)(

(

)(

(

)(

L

两两互质,由整除的性质知,2×3×5×7×13|

.故

是整值多项式.

g

(mod6)。

，k

为正整数,于是

作业:P64:1.

2.分数与循环小数

L

nL

n

{0,1，…,9}）从任何一位数后不全为

s≥0,t＞0,使得

i

i

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

L

L

对满足(*)的最小正整数

对满足(*)的最小正整数

L

为循环节的长度.若最小的

s=0,那小数就叫做纯循环小数，否则叫做混循环

b

能表成纯循环小数的充分必要条件是,(b,10)=1.

b

是纯有限小数的充分必要条件是(b,10)≠1.

b

b

b

L

L

L

L

gL

L

L

.于是

b

.所以

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

,设

=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

是正整数,则称

L

为同余式,或模

的同余方程.

称为同余方程(1)的次数.若

a∈Z

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