蒲地蓝消炎片的功效与作用-疯狂猜成语答案

第一章 整数的可除性
第一章 整数的可除性
§1 整 除
整数 集对于加、减、乘三种运算都是封闭的，但是对于除法运算不封闭。
为此，我们引进整除的概念。
定义1 设a,b∈Z，b≠0，如果存在q∈Z，使得等式a=bq成立，那么称b
整除a或 a被b整除，记作：b|a，此时称b为a的因数（约数），a为b的倍数。
如果不存在满足等式a=bq的整数q，那么称b不能整除a或a不被b整除，
|
a。 记作b

定理1 设a,b,c∈Z，b≠0，c≠0，则
（1）如果c|b，b|a，那么c|a；
（2）如果b|a，那么bc|ac；反之亦真；
（3）如果c|a，c|b，那么，对于任意m,n∈Z，有c|(ma+nb)；
（4）如果b|a，a≠0，那么|b|≤|a|；
（5）如果b|a，a|b，那么|b|=|a|。
证明 可选证。
定理2（带余除法） 设a,b∈Z，b≠0，则存在q,r∈Z，使得a=bq+r，0≤
r <|b|，并且q及r是唯一的。
证明 当b|a时，取q=ab，r=0即可。
当b!|a时，考虑集合E={a-bk|k∈Z }，易知E中有正整数，因此E中有最
小正 整数，设为r=a-bk>0，下证：r<|b|。因为b!|a，所以r≠|b|，若r>|b|，则r’=r -|b|>0，
又r’∈E，故与r的最小性矛盾，从而存在q,r∈Z，使得a=bq+r，0≤r< |b|。
唯一性。设另有q’,r’∈Z，使得a=bq’+r’，0≤r’<|b|，则b(q-q ’)=r’-r，于
是b|(r’-r)，但由于0≤|r’-r|<|b|，故r’-r=0，即r= r’，从而q=q’。
- 1 -

第一章 整数的可除性
定义2 等式a=bq+r，0≤r<|b|中的整数q称为a被b除所得的（不完全）
商，整数r称为a被b除 所得的余数。
注 r=0的情形即为a被b整除。
例1 设b=15，则
当a=255时，a=17b+0，故q=17，r=0；
当a=417时，a=27b+12，故q=27，r=12；
当a=-81时，a=-6b+9，故q=-6，r=9。
例2 整数被2除的余数有两种可 能：0和1，一个整数被2整除称为偶数，
否则称为奇数，分别记作2k和2k+1，k∈Z。
类似地，任一整数可表示为3k，3k+1，3k+2三种形式之一。
例3 设a=2t-1，若a|2n，则a|n。
例4设a,b∈Z，a≠0，b≠0，有x,y∈Z，使a x+by=1，证明：若a|n，b|n，
则ab|n。

- 2 -

第一章 整数的可除性
§2 最大公因数与最小公倍数
定义1 设a
1
,a
2
,…,a
n
是n (n≥2)个整数，若整数 d满足d|a
i
，i=1,2,…,n，则
称d为a
1
,a
2
,…,a
n
的一个公因数；
整数a
1
,a
2< br>,…,a
n
的公因数中最大的一个称为最大公因数，记作：(a
1
,a
2
,…,a
n
)；
若(a
1
,a
2,…,a
n
)=1，则称a
1
,a
2
,…,a
n
互质（互素）；
若a
1
,a
2
,…,a
n中每两个整数互质，则称a
1
,a
2
,…,a
n
两两互 质。
注1 任意整数a
1
,a
2
,…,a
n
必有公因数（如±1）。
注2 若a
1
,a
2
,…,a
n
不全为0，则它们 的公因数只有有限多个，从而它们的
最大公因数必然存在而且唯一。（§1定理1之(4)）
注3 最大公因数一定是正整数。
注4 (a
1
,a
2
, …,a
n
)=1相当于a
1
,a
2
,…,a
n的公因数只有±1。
注5 两两互质必互质，反之未然。
定理1 若a
1
,a
2
,…,a
n
是任意n个不全为零的整数，则
(1) a
1
,a
2
,…,a
n
与|a
1
|,|a
2
|,…,|a
n
|的公因数相同；
(2) (a
1
,a
2
,…,a
n
)=( |a
1
|,|a
2
|,…,|a
n
|)。
定理2 若b是任一正整数，则
(1) 0与b的公因数就是b的因数，反之亦然；
(2) (0,b)=b。
推论 若b是任一非零整数，则(0,b)=|b|。
定理3 设a,b ,c是任意三个不全为零的整数，且a=bq+c，其中q∈Z，则
a,b与(b,c)有相同的公因数 ，从而(a,b)= (b,c)。
定理4 设a
1
,a
2
,…, a
n
是不全为零的整数，则a
1
,a
2
,…,a
n
的整线性组合的集
合S={a
1
x
1
+a
2
x
2
+…+a
n
x
n
| x
i
∈Z ， i=1,2,…,n}恰由(a
1
,a
2
,…,a
n
)的所 有倍数组成。
- 3 -

第一章 整数的可除性
证明 因为S中有正整数，所以S中有最小正整数，设为D= a
1
x
1
’+a2
x
2
’+…
+a
n
x
n
’，则对于 任意的a
1
x
1
+a
2
x
2
+…+an
x
n
∈S，有a
1
x
1
+a
2x
2
+…+a
n
x
n

=( a
1< br>x
1
’+a
2
x
2
’+…+a
n
x
n
’)q+r，其中0≤r< a
1
x
1
’+a
2
x
2
’+…+a
n
x
n
’，于是r=a
1
(x
1
-x
1
’q)+
a
2
(x
2
-x
2
’q)+…+ a
n< br>(x
n
-x
n
’q)∈S，若r>0，则与D是最小正整数矛盾，故r =0，即
S中任一整数都是D的倍数。反之，D的倍数也属于S，故S=DZ={Da|a∈Z}。 < br>设d=(a
1
,a
2
,…,a
n
)，下证：D=d。
由于D∈S，又d|a
i
，i=1,2,…,n，故d|D，即d≤D；另一方面，因 为a
1
,a
2
,…,a
n
∈S，所以D|a
i，i=1,2,…,n，从而D≤d。因此，D=d。
推论 设a
1
,a
2
,…,a
n
是不全为零的整数，则存在整数x
1
,x
2
,…,x
n
，使得
a
1
x
1
+a
2
x
2
+…+a
n
x
n
=(a
1
,a
2
,…,a
n
)，这一等式称为裴蜀（Bezout）等式。
特别地，(a
1
,a
2
,…,a
n
)=1的充分必要条件为 存在整数x
1
,x
2
,…,x
n
，使得
a
1
x
1
+a
2
x
2
+…+a
n
x
n
=1。
定理
5
(1)a
1
,a
2,

,a
n
的每一个公因数都是(a
1
,a
2
,

,a
n
)的因数；
(2)(a
1
,a
2
,

,a
n
)((a
1
,a
2
),

,a
n
)；
(3)设mZ

， 则(ma
1
,ma
2
,

,ma
n
)m (a
1
,a
2
,

,a
n
)；
a
a
1
a
2
,,

,
n
)1；< br>ddd
(5)设(a,m)(b,m)1，则(ab,m)1；（可推广）
(4) 设(a
1
,a
2
,

,a
n
)d，则(
(6)若c|ab且(c,b)1，则c|a。
证明(1)由裴蜀等式推出；
(3) 一方面由(1)，另一方面由裴蜀等式；
(2)由(1)；
(4)由(3)；
(5)将 裴蜀等式相乘；
(6)由裴蜀等式或由(1)，(3)可推出，c|ab，c|acc|(ab,ac )|a|(b,c)。


- 4 -

第一章 整数的可除性
最大公因数的求法：
1、由定理5(2)可知，求两个以上整数的最大公因数可 以转化为求两个整
数的最大公因数，对此，我们有下面算法：
辗转相除法（欧几里得(Eucl id)算法）设a,bZ，b0，按下述方式反
复做带余除法，有限步之后必然停止（即余数为零）
用b除a：abq
0
r
0
，0r
0
|b| ；
用r
0
除b：br
0
q
1
r
1，0r
1
r
0
；
用r
1
除r
0< br>：r
0
r
1
q
2
r
2
，0r
2
r
1
；

用r
n1
除r
n 2
：r
n2
r
n1
q
n
r
n< br>，0r
n
r
n1
；
用r
n
除r
n1
：r
n1
r
n
q
n1
。
则 (a,b)r
n
。
事实上，由于余数满足r
0
r
1

r
n1


0，故上述带余除法有限步后余数必为零，另一方面，由定理3，我们有
(a,b)(b,r
0
)(r< br>0
,r
1
)

(r
n1
,r
n
)r
n
。
2、上述算法不仅能算出(a,b)，而且可以求出方程ax by(a,b)的一组
整数解，具体做法就是将算式倒推。


例1设a1859，b1573，求(a,b)及x,y。

定义2设a
1
,a
2
,

,a
n
是n(n2)个非零整数 ，若整数D满足
a
i
|D，i1,2,

,n，则称D为a
1
,a
2
,

,a
n
的一个公倍数；
记 作：[a
1
,a
2
,

,a
n
]。

a
1
,a
2
,

,a
n
的一 切公倍数中的最小正数称为a
1
,a
2
,

,a
n
的最小公倍数，
定理6(1)[a
1
,a
2
,
< br>,a
n
][|a
1
|,|a
2
|,
,|a
n
|]；
(2)a
1
,a
2
,

,a
n
的每个公倍数都是[a
1
,a
2
,

,a
n
]的倍数；
(3)设mZ

，则[ma
1
,ma
2
,

,ma
n
]m[a
1
,a
2
,

,a
n
]；
(4)[a
1
,a
2
,

,a
n
][[a
1,a
2
],

,a
n
]；
(5)(a,b)[ a,b]|ab|；
(6)若a
1
,a
2
,

, a
n
两两互质，则[a
1
,a
2
,

,a
n
]|a
1
a
2

a
n
|。< br>- 5 -

第一章 整数的可除性
证明(1)由定义；< br>(2)设S{a
1
,a
2
,

,a
n的全体公倍数}，则S恰好是S中最小正整数D的所有
倍数构成的集合，故D[a
1,a
2
,

,a
n
]；
(3)(4)由定义；
(5)可设a,b均为正整数，当(a,b)1时，由定义：[a,b]axby，
a, b)1a,b]|ab
于是b|ax
(
b|xab|ax[a,b]
[
[a,b]ab，
ababab
一般情形，设(a,b)d，则 (,)1，于是[,]
2
，由(3)及定理5(3)可知
dddd
dababab
(a,b)[a,b]d(,)[,]dd
2

2ab；
dddd
d
(6)由(4)(5)及定理5(6)可推之。
< br>补充习题：
1、设nZ

，则
21n4
是既约分数。14n3
2、设nZ

，则(n!1,(n1)!1)1。
4、设m,n,aZ

，a1，证明：(a
m
1,a
n
1)a
(m,n)
1。
5、设a,b是不为0或1的整数，证明：存在x, yZ，满足axby(a,b)，
且0|x||b|，0|y||a|。
6、设 a,bZ，证明：存在x,y,u,vZ，使得axu，byv，(x,y)1
且[a,b] xy。
7、设m,nZ

，(m,n)1，证明：(1)(d,mn)(d, m)(d,n)；
(2)mn的任一正因数d，可唯一地表示为dd
1
d
2
，其中d
1
,d
2
分别是m,n的
正因数。
8、设 nZ

，证明：(1)(a
n
,b
n
)(a,b)n
；
(2)设(a,b)1，a,bZ

，abc
n，则a,b都是正整数的n次方幂，事实上，
a(a,c)
n
，b(b,c)
n
。一般地，若若干个两两互质的正整数之积是整数的n次
幂，则这些整数都是正整数 的n次方幂。
9、设nZ

，k为正奇数，证明：(12

 n)|(1
k
2
k


n
k
)。3、设m,nZ

，m是奇数，证明：(2
m
1,2
n1)1。

- 6 -

第一章 整数的可除性
§3 算术基本定理
定义 一个大于1的整数，如果它的正因数只有1及它本身，那么称之为质
数；否则称为合数。
注 正整数分为三类：1，质数类，合数类。
定理1设aZ，a1，则a的除1外最小正因数q是一质 数，并且当a是合
数时，qa。
证明假设q不是质数，则q除1及本身外还有一正因数q1
，因而1q
1
q，

但q|a，故q
1
|a，这与q是a的除1外的最小正因数矛盾，从而q是质数。
当a是合数时，aa
1
q，其中a
1
1，否则a是质数，由于q是a的除1外的最
小正因数，所以qa
1
，于是q
2
qa
1
a，也即qa。
定理2 若p是一质数，a是任一整数，则p|a或(a,p)1。
证明因为(p,a)|p，(p,a)0 ，由质数的定义，(p,a)1或(p,a)p，

即p|a或(a,p)1。
推论设a
1
,a
2
,

,a
n
是n个整数 ，p是质数，若p|a
1
a
2

a
n
，则a
1
,a
2
,

,a
n
中至少有一个被p整除。< br>证明假设a
1
,a
2
,

,a
n
都 不能被p整除，则(p,a
i
)1，i1,2,

,n，
从而( p,a
1
a
2

a
n
)1，这与p|a
1
a
2

a
n
矛盾，故结论成立。
定理3质数有无 穷多个。（公元前3世纪，Euclid）
证明
（反证法）假设质数只有有限多个，设p
1
,p
2
,

,p
r
是全部质数，
考虑 Np
1
p
2

p
r
1，由于N1，故由定理 1，N必有质因数p，由假设p必然
等于某个p
i
(1ir)，因而p整除Np
1
p
2

p
r
1，矛盾，故质数有无穷多个。< br>定理（算术基本定理）4任一大于1的整数能表示成质数的乘积，即任一大
于1的整数ap1
p
2

p
n
，p
1
p
2


p
n
，其中p
1
,p
2
,

,p
n
是质数，并且若
aq
1
q
2< br>
q
m
，q
1
q
2


q
m
，其中q
1
,q
2
,

,q
m
是质数，则mn，p
i
q
i
，
i1,2,

,n。
证明存在性（用数学归纳法）
当a2时，因为2是质数，所以结论成立。
- 7 -

第一章 整数的可除性
假设结论对小于a的 正整数都成立，下面考虑a，如果a是质数，则结论成
立；若a是合数，则有b,cZ
满足abc，1ba，1ca，由归纳假设，
b,c都可以写成若干个质数的乘积，于是 a也能写成有限个质数的乘积，适当调
动次序后便得结论。
唯一性因为ap
1
p
2

p
n
q
1
q
2
q
m
，p
1


p
n
，q
1
q
2


q
m
，
所以p
1
|q
1
q
2

q
m
，q
1
|p
1
p
2

p
n
，于是有p
k
,q
j
，使得p
1
|q
j
，q
1
|p< br>k
，又p
k
,q
j
均为质数，故p
1
q< br>j
，q
1
p
k
，又p
k
p
1< br>，q
j
q
1
，故q
j
p
1
p
k
q
1
，从而
p
1
q
1
，于 是有p
2

p
n
q
2

q
m< br>，同法可得p
2
q
2
，依此类推，最后可得
nm，pi
q
i
，i1,2,

,n。
推论1任一大于1的 整数a能够唯一地写成

k

1

2
ap
1
p
2

p
k
，

i
0，i 1,2,

,k，p
i
p
j
(ij)。
注1 上式叫做a的标准分解式；
注2为了讨论的方便，我们可以插进若干质数的零次幂而写成下面形式

k

1

2
ap
1
p
2< br>
p
k
，

i
0，i1,2,

,k，p
i
p
j
(ij)。


k

1

2
推论2设ap
1
p
2

p
k
是a的标准分解式，则正整数d是a的约数的充分

k
2
必要条件是其标准分解式为dp
1

1
p
2

p
k
，0

i


i
，i 1,2,

,k。
证明充分性是显然的。
必要性若d1，则结论已成立； 若d1，则由d|a可知，d的质因数必在

k

2
p
1
,p
2
,

,p
k
中，于是可设d的标准分解式为 dp
1

1
p
2

p
k
，
i
0，i1,2,

,k。下证：

i


i
，i1,2,

,k。（反证）
假设有一个

j


j
，则由p
j
j
|d及d|a 可知p
j
j
结论成立。
推论3设a,bZ

，且它们的标 准分解式为

k

k

1

2

2
ap
1
p
2

p
k
，bp
1

1
p
2

p
k
，

i
,

i
0，i1,2,

,k，

k

1

2
则(a,b)p
1
p
2

p
k
，其中

i
min(
i
,

i
)；

k

1
< br>2
[a,b]p
1
p
2

p
k
， 其中

i
max(

i
,

i
)。

k

1

2
证明令mp
1
p
2

p
k
，则m|a，m|b，又任一公因数必整除m，



j

k

1
j1j1|p
1

p
j1
p
j1

pk
，

即p
j
必与p
1
,

,p
j1
,p
j1
,

,p
k
之一 相同，矛盾，因此，

i


i
，i1,2,

,k，

- 8 -

第一章 整数的可除性
故m(a,b)。

同样可证另一结论。
幼拉脱斯展纳（Eratosth enes）筛法任给一个正整数N，把不超过N的一
切正整数按大小关系排成一串1,2,3,

,N，首先划去1，第一个留下来的是2，然
后从2起划去2的一切倍数，第一个留下来的是 3，然后从3起划去3的一切倍数，

，一直到划去不超过N的质数的一切倍数，最后留下来的 就是不超过N的
一切质数。
例造不超过30的质数表。


补充习题
1、设n2，证明：n和n!之间必有质数，由此说明质数有无穷多个。
2、设n2，证明 ：存在连续n个正整数，其中每一个都不是质数。这表明，
在正整数序列中，可以有任意长的一段区间中 不包含质数。
3、证明：(1)形如4m3的质数有无穷多个；
(2)形如6m5的质数有 无穷多个；
4、如果p，p2，p4都是质数，那么p3。
5、设整数10
n 1
10
n2


1(n1)是质数，则n必为质数，反之不 成立。
6、(1)设mZ

，证明：若2
m
1为质数，则m为2 的方幂；
(2)记F
n
2
2
1，n（费马数），证明：若0m n，则F
n
|(F
m
2)；
(3)证明：(F
m
,F
n
)1，mn。由此说明，质数有无穷多个。
(费马数中的质数称为费马质 数，如，F
0
3，F
1
5，F
2
17，F
3
257，
F
4
65537都是质数，费马猜测：F
n
都 是质数。但F
5
6416700417不是质数
（欧拉，1732），未知：费马 质数还有吗？费马质数是否有无穷多个？)
7、(1)设m,nZ，m,n1，证明：若m
n
1是质数，则m2并且n是质数；
(2)设p是质数，记M
p
2p
（梅森数），证明：若1pq，则(M
p
,M
q
)1。
(梅森数中的质数称为梅森质数（1644，法），它与偶完全数紧密相关，
到1996年底， 找到34个梅森质数，未知：是否有无穷多个梅森质数？)
8、设a,b,c,dZ

，满足abcd，证明：a
4
b
4
c
4
d
4
不是质数。
- 9 -
n

第一章 整数的可除性 9、证明：(1)(a,[b,c])[(a,b),(a,c)]；
(2)[a,(b,c)] ([a,b],[a,c])。
11

10、证明：(1)1

Z，(n1)；
2n
11
(2)1

Z，(n1 )。
32n1
- 10 -

第一章 整数的可除性
§4 函数[x]，{x}及其在数论中的一个应用
定义函数[x]与{x}是定义在实数集上的函数，函数 [x]的值等于不大于
x的最大整数，函数{x}的值是x[x]，[x]叫做x的整数部分(也称为 高斯函数)，
{x}叫做x的小数部分。
2332
例[

]3,[ e]2,[

]4,[]0,[]1,{3.14}0.14,{}。
3555
性质(1)x[x]{x}；
(2)[x]x[x]1，x1 [x]x，0{x}1；
(3)[nx]n[x]，nZ；
(4)[x][y ][xy]，{x}{y}{xy}；

[x]1，当xZ时
(5) [x]

；

[x]，当xZ时
aaa
(6)设a ,bZ，b>0，则ab[]b{}，0b{}b1；
bbb
a
(7)设 a,bZ
+
，则不大于a而为b的倍数的正整数的个数为[]。
b

证明当ab时，结论显然成立，下证ab的情形。
设m是任意不大于a而为b的倍数的正整数，则 0mbm
1
a，

aaa
于是0m
1
， 而满足这个条件的m
1
的个数为[]，故m的个数为[]。
bbb
定理在n! 的标准分解式中，质因数p(pn)的指数

nnn
h[][
2
]



[
r
]。
pp
r1
p
证明把2,3,

,n都写成标准分解式，则h是这n1个分解式中p的指数< br>之和，设2,3,

,n中p的指数为r的有n
r
个(r1)，则< br>hn
1
2n
2
3n
3


 (n
1
n
2
n
3


)(n
2
n
3


)(n
3


)

N
1
N
2
N
3


其中N
r
n
r
n
r1


恰好是2,3,

,n中能被p
r
整除的数的个数，

nn
于是N
r
[
r
]，因此h

[
r]。
p
r1
p

- 11 -

第一章 整数的可除性

[
p
r
]

推论1n!

p
r1
。
pn

n
n!
是整数(0kn)。
k!(nk)!
nnkk
证明由高斯函数之性质(4)可知[
r
][
r
][
r
]，
ppp
推论2贾宪数
< br>
[
nnkk
于是

[
r
]

[
r
]

[
r
]，从而

p< br>r1
p
r1
p
r1r1
p
pn




nk
p
r
]

[p
r
]
r1

k

[
p
r
]
|

p
r1
，
pn
n
故k !(nk)!|n!。
推论3若f(x)是一n次整系数多项式，f
(k)
(x)是 它的k阶导数(kn)，

f
(k)
(x)
则是一nk次整系数多项式。
k!


- 12 -