定风波苏轼-有余数的除法课件

数学奥赛辅导讲义------数论(1) 整除


知识、方法、技能
整除是整数的一个重要内容，这里仅介绍其中的几个方面：整数的整除性、 最大公约
数、最小公倍数、方幂问题.
Ⅰ. 整数的整除性
初等数论的基本研究对象是自然数集合及整数集合. 我们知道，整数集合中可以作加、
减、乘 法运算，并且这些运算满足一些规律（即加法和乘法的结合律和交换律，加法与乘法
的分配律），但一般 不能做除法，即，如
a,b
是整除，
b0
，则
出初等数论中第一个 基本概念：整数的整除性.
定义一：（带余除法）对于任一整数
a
和任一整数
b
，必有惟一的一对整数
q
，
r
使得
并且整数
q
和
r
由上述条件惟一确定，则
q
称为
b
除
a
的不完全商，
abqr
，
0rb
，
a
不 一定是整数. 由此引
b
r
称为
b
除
a
的余数.
若
r0
，则称
b
整除
a
，或
a
被
b
整除，或称
a是b
的倍数，或称
b是a
的约数（又叫< br>因子），记为
b|a
.否则，
b
|
a
.
任何
a
的非
a,1
的约数，叫做
a
的真约数.
0是任何整数的倍数，1是任何整数的约数.
任一非零的整数是其本身的约数，也是其本身的倍数.
由整除的定义，不难得出整除的如下性质：
（1）若
a|b,b|c,则a|c.

（2）若
a|b
i
,则a|

cb,其中c
ii
i1
n
i

Z,i

1,2,

,n.

（3）若
a|c
，则
ab|cb.
反之，亦成立.
（4） 若
a|b,则|a||b|
.因此，若
a|b,又b|a,则ab
.
（5）
a
、
b
互质，若
a|c,b|c,则ab|c.
（6）
p
为质数，若
p|a
1
a
2
a
n
,
则
p
必能整除
a
1
,a< br>2
,

,a
n
中的某一个.
特别地，若
p
为质数，
p|a,则p|a.

n
（ 7）如在等式

a

b
i
i1k1
nmk
中除开某一项外，其余各项都是
c
的倍数，则这一项也是

c
的倍数.
（8）n个连续整数中有且只有一个是n的倍数.
（9）任何n个连续整数之积一定是n的倍数.
本讲开始在整除的定义同时给出了约数的概念 ，又由上一讲的算术基本定理，我们就
可以讨论整数的约数的个数了.
定理一：设大于1的整 数
a
的标准分解式为
ap
1
1
p
为质数，
i
均为非负整数），则a的约数的个数为
d(a)

2
p
n
n
(p
1
p
2
p< br>n
i

（


i1
n
1).
p
i

i
1
1
所有的约数和为：
(a)

.
p
i
1
i1
n
事实上，由算术基本定理的推论知
d(a)

(

i1
n
i
1)
，而各约数的和就是

(1p
i1
n
i
pa
i
i
)
展开后的各项之和，所以
nn

i
p
1
1


(a)

(1p
i
p
i
)

p1< br>i1i1
i

i
例如，25200=2
4
·3< br>2
·5
2
·7，所以
d(25200)(41)(21)(21)(11)90
，
2
5
13
3
15
3
17
2
1
< br>(25200)99944
.
21315171
Ⅱ. 最大公约数和最小公倍数
定义二：设
a
、
b
是两个不全为0的整数 .若整数c满足：
c|a,c|b
，则称
c为a,b
的
a与b
的所有公约数中的最大者称为
a与b
的最大公约数，公约数，记为
(a,b)
.如果
(a,b)
=1，
则称
a与b
互质或互素.
定义 三：如果
d是a
、
b
的倍数，则称
d是a
、
b的公倍数.
a与b
的公倍数中最小的正
数称为
a与b
的最小公 倍数，记为
[a,b]
.
最大公约数和最小公倍数的概念可以推广到有限多个整数的 情形，并用
(a
1
,a
2
,,a
n
)
表 示
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< br>,a
3
,

,a
n
互质，若
a
1< br>,a
2
,

,a
n
中任何两个都互质，

则称它们是两两互质的.注意，n个整数互质与n个整数两两互质是不同的概念，前者成立时
后者不一定成立（例如，3，15，8互质，但不两两互质）；显然后者成立时，前者必成立.
因为任 何正数都不是0的倍数，所以在讨论最小公倍数时，一般都假定这些整数不为
0.同时，由于
a ,b与|a|,|b|
有相同的公约数，且
(a,b)(|a|,|b|)
（有限多 个亦成立），
因此，我们总限于在自然数集合内来讨论数的最大公约数和最小公倍数.
显然，若
a,b
的标准分解式为
a
则

ip,bp

i

i
(p
i
为质数，
a
i
,

i
为非负整数），

i
i1i 1
nn
(a,b)

p
i
min(

i
,

i
)
①
i1
n
n
[a,b]

p
i
man(

i
,

i
)
②
i1
例如 3960=2
3
·3
2
·5·11，
756=2
2
·3
3
·7，
则 （3960，756）=2
2
·3
2
=36，
[3960，756]=2
3
·3
3
·5·7·11=83160.
求最大公约数也可以用辗转相除法，其理论依据是：
定理二：设a、b、c是三个不全为0的 整数，且有整数t使得
abtc
，则a、b与b、
c有相同的公约数，因而
(a,b)(b,c)
，即
(a,b)(b,abt).

因为，若
d是a
、b的任一公约数，则由
d|a,d|b和abtc知d|c,即d是b< br>、c的
公约数；反之，若
d是b
、c的任一公约数，
d也是a
、b的公约数.
辗转相除法：设
a
、
bN,且ab
，
由带余除法有



br
1
q
2r
2
,0r
2
r
1
,



③
r
n2
r
n1
q
n
r
n
,0r
n
r
n1
,

r
n1
r
n
q
n1
r< br>n1
,r
n1
0.


因为每进行一次带余除 法，余数至少减1，即
br
1
r
n
r
n1，而b为有限数，
因此，必有一个最多不超过b的正整数n存在，使得
r
n
0
，而
r
n1
0
，故由定理二得：
abq1
r
1
,0r
1
b,
r
n
( r
n1
,r
n
)(r
n
,r
n1
) (r
2
,r
1
）（r
1
,b)(a,b).
例如，（3960，756）=（756，180）=（180，36）=36.

具体算式如下：
5（q
1
） 3960（a） 756（b） 4（q
2
）
3780 720
180（r
1
） 36（r
2
）
5（q
3
） 180

0（r
3
）

由定义和上述求法不难得出最大公约数和最小公倍数的如下性质：
（1）
mN,则(am,bm)m(a,b)
.
（2）设
c为 a,b
的公约数，则
(,)
ab
cc
(a,b)ab
.< br>特别地，若
c(a,b),则(,)1
.
ccc
（3）设
a
1
,a
2
,

,a
n
是任意n个正整 数，如果
(a
1
,a
2
)c
2
,(c
2
,a
3
)c
3
,

,(c
n1
,a
n
)c
n
，
则
(a
1
,a2
,

,a
n
)c
n
.
因
c
n
|a
n
,c
n
|c
n1
,而c< br>n1
|a
n1
,c
n1
|c
n2
, 故c
n1
|a
n1
,c
n
|c
n2
，如此类推得出
c
n
能
整除
a
n
,a
n 1
,

,a
1
,于是c
n
是它们的一个公约数.又 设
c
为
a
1
,a
2
,

,an
的任一公约数，则
c|a
1
,c|a
2
，因而
c|c
2
，同理可推出
c|c
3
，如此类推最后可得
c| c
n
. 于是
c|c|c
n
，
故
c
n
是最大公约数.
（4）若
(a,b)c
，则一定有整数
x和y
，使得
ax byc
.
特别地，
(a,b)1
存在
x,y使得axby1
.
这可由辗转相除法的③式逆推而得
cr
n
axby
.
（5）若
(a,b)1,则(ac,b)(c,b)
.
（6）
a,bN

①
[ak,bk]k[a,b]
< br>(kN

)
；
②
m为a,b
的任一公倍数，则
[a,b]|m
；
③(a,b)[a,b]ab
，特别地，若
(a,b)1,则[a,b]ab
.
①可由③直接得到，②可由最小公倍数定义得，③根据①、②式知，
(a,b)[a,b ]

p
i
min(

i
,

i
)

p
i

i


i
ab
.
i1i1
nn

（7）设
a
1
,a
2
,

,a
n
是任意
n
个正 整数.若
[a
1
,a
2
]

m
2
,[m
2
,a
3
]

m
3
,,[mn1
,a
n
]

m
n
，
则
[a
1
,a
2
,

,a
n
]m
n
.
这是一个求多个整数的最小公倍数的方法.它可用证明③类似的方法来证明.
Ⅲ.方幂问题
一个正整数
n
能否表成
m
个整数的
k
次方和的问题称为方幂和问题.特别地，当
m1
时称为
k
次方 问题，当
k2
时，称为平方和问题.
能表为某整数的平方的数称为完全平方数. 简称平方数，关于平方数，明显有如下一些
简单的性质和结论：
（1）平方数的个位数字只可能是0，1，4，5，6，9.
（2）偶数的平方数是4的倍数，奇数的平方数被8除余1，即任何平方数被4除的余
数只能是0或1.
（3）奇数平方的十位数字是偶数.
（4）十位数字是奇数的平方数的个位数一定是6.
（5）不能被3整除的数的平方被3除余1，能被3整除的数的平方能被3整除.因而，
平方 数被9除的余数为0，1，4，7，且此平方数的各位数字的和被9除的余数也只能为0，
1，4，7.
（6）平方数的约数的个数为奇数.
（7）任何四个连续整数的乘积加1，必定是一个平方数.
进一步研究可得到有关平方和的几个结论:


定理三：奇素数
p
能表示成两个正整数的平方和的充要条件是
p4m1.

定理四：设正整数
nmp
，其中
p
不再含平方因数，
n
能表示成两个整数的平方的
2
充要条件是
p
没有形如
4q3
的质因数.
定理五：每个正整数都能表示成四个整数的平方和.
这几个定理的证明略.这里重点是介绍有关k
方幂的解法技巧.
k
方幂中许多问题实质上
是不定方程的整数解问题， 比如著名的勾股数问题.

赛题精讲
例1：证明：对于任何自然数
n和
k
，数
f(n,k)2n
续的正整数之积.
（1981年全国高中联赛试题）


【证明】由性质9知，只需证明数< br>f(n,k)
不能被一个很小的自然数
n
整除.因
3k
4 n
k
10
都不能分解成若干个连
f(n,k)3n
3k
3n
k
n
3k
n
k
103(n
3kn
k
3)n
k
(n
k
1)(n
k1)1,

3|3(n
3k
n
k
3),3|n
k
(n
k
1)(n
k
1),
3 1，故3
f(n,k)
，因而
f(n,k)
不能分解成
三个或三个以上的连续 自然数的积.
再证
f(n,k)
不能分解成两个连续正整数的积.

由上知，
f(n,k)3q1(qN)
，因而只需证方程：< br>3q1x(x1)
无正整数解.而
这一点可分别具体验算
x3r,34 1,342
时，
x(x1)
均不是
3q1
形的数来说明.
故
f(n,k)
对任何正整数
n
、
k
都不能分解 成若干个连续正整数之积.
例2： 设
p
和
q
均为自然数,使得< br>p1111
1.

q2313181319
证明：
p
可被1979整除. (第21届IMO试题)
【证明】
p111111
(1)2()

q231319241318
11111
)(1)

2313192659
111111
=
()()()

66989990
111
=1979×
(

)

66013196611318989990
=
(1
两端同乘以1319！得1319！

p
1979m(mN*).
此式说明1979|1319！×
p.
由
q
于1979为质数，且1979 1319！，故1979|
p.



【评述】把1979换成形如
3k2
的质数，1319换成
2k1(kN*)
，命题仍成立.
牛顿二项式定理和
(ab)|ab,(ab)|ab(n
为偶数),
(ab)|ab(n
nnnnnn
为奇数)在整除问题中经常用到.
例3 ：对于整数
n
与
k
，定义
F(n,k)

r
r1
2m
n
2k1
,
求证：
F(n ,1)
可整除
F(n,k).

（1996加拿大数学竞赛试题）
【证明】当
n2m
时，
F(2m,1)
m2m

rm (2m1),

r1

F(2m,k)

r
r1
2k1

rm1

r
m
2k1


r
r1
m
m
2k1

(2m1r)
2k1
r1



[ r
2k1
(2m1r)
2k1
],
r1
由于 […]能被
r(2m1r)2m1
整除，所以
F(2m,k)
能被
2m1
整除，另一方

面，

F(2m,k)< br>
[r
r1
m1
2k1
(2mr)
2k 1
]m
2k1
(2m)
2k1
,

上式 中[…]能被
r(2mr)2m
整除，所以
F(2m,k)
也能被m
整除.因
m
与2
m
+1
互质，所以
F(2m ,k)
能被
m
（2
m
+1）（即
F(m,1)
）整 除.
类似可证当
n2m1
时，F（2
m
+1，
k< br>）能被F（2
m
+1,1）整除. 故
F(n,k)
能被
F(n,1)
整除.
例4 ：求一对整数a,b
，满足：(1)
ab(ab)
不能被7整除；（2）
(ab) ab
能被
7
7
整除. (第25届IMO试题)

777
【解】
(ab)ab
=< br>7ab[(ab)3ab(ab)5ab(ab)]

553322
777
=
7ab(ab)(abab).



根据题设要求(1) (2)知，
7|(abab)|,
即
7|abab.

2< br>令
abab7,
即
(ab)ab343,
即
a b19
，则
ab19343.
故可
2232
6222322< br>222
令
a18,b1
即合要求.
【评述】数学归纳法在整除问题中也有广泛应用.
例5：是否存在1000000个连续整数，使得每 一个都含有重复的素因子，即都能被某个素数
的平方所整除？(第15届美国普特南数学竞赛试题) < br>【解】存在.用数学归纳法证明它的加强命题：对任何正整数
m,
存在
m
个连续的整
数，使得每一个都含有重复的素因子.
当
m
=1时，显然成立.这只需取一个素数的平方.
假设当
m
=
k
时命题成立,即有
k
个连续整数
n1,n2,,nk,它们分别含有重复的
素因子
p
1
,p
2
,

,p
k
,任取一个与
p
1
,p
2
,

,p
k
都不同的素数
p
k1
(显然存在),当
22222
t1,2,p
k1
时,
tp
1
p
2

p
k
n(k1)
这
p
k1
个数中任两个数的差是形如
222
222
ap
1
2
p
2
p
k
(1ap
k1
1)
的数,不能被
p
k1
整除,故这
p
k1
个数除以
p
k1
后,余数两两
222
不同.但除以
p
k1
后的余数只有0 ，1，…，
p
k1
－1这
p
k1
个，从而恰有一个数< br>222
22
tpp

pn(k1)
t
0
(1t
0
p
k
)p
，使
能被
（
k 1)
个连续整数：
012k
1k1
整除.这时，
22
2222
t
0
p
1
2
p
2

p< br>k
n1,
t
0
p
1
2
p
2p
k
n
2，…，
t
0
p
1
2< br>p
2
p
k
n
k
，

< br>22
t
0
p
1
2
p
2

p
k
n
（
k
+1）
2222
分别能被
p
1
,p
2
p
k
,p
k1
整除，即< br>mk1
时命题成立.故题对一切正整数
m
均成立.
[a,b,c]
2
(a,b,c)
2
.
例6：求证：< br>[a,b][b,c][c,a](a,b)(b,c)(c,a)
（第1届美国数学奥林匹克竞 赛试题）
【证明】设
a
n

p
i1
i
i,b

p
i
i,c

p
i< br>
i,
其中

i1i1
nn
p
i
为质数，

i
,

i
,

i
为 非负整数，则

[a,b,c]
n

p
i1
n
max(

i
,

i
,

i
)
i
,


[a,b]
< br>p
i
max(

i
,

i
)
,

i1

(a,b,c)
n
p
i1
n
mi

n
i
(,

i
,

i
)
i
,


(a,b)



因此只需证明
min(

i
,

i
)
p,


i
i1
2
max(

i
,< br>
i
,

i
)max(

i
,< br>
i
)max(

i
,

i
) max(

i
,

i
)

=2
min(

i
,

i
,

i
) min(

i
,

i
)min(

i
,

i
)min(

i
,

i
)

上式关于

i
,

i
,
i
对称，则不妨设

i


i
< br>
i
，于是上式变为：
2

i


i


i


i
2

i

i


i


i
.此式显然成立，故得证.
a
p
b
p
例7：设
a和
b
是两个正整数，
(a,b)1,p
为大于或等于3的质数，
c(ab,
），
ab
试证：（1）
(c,a)1
；（2）
c1
或
cp.
（1985新加坡数学竞赛试题）
a
p
b
p
cs(t,sN)
，两式相乘得

【证明】由已知得
abct,
ab
c
2
stap
b
p
a
p
(cta)
p
c
p
t
p
pac
p1
t
p1
pap1
ct,
于是
csc
p1
t
p1
pac
p2
t
p2
pa
p1
,
故< br>c|pa
p1
.

（1）现用反证法来证明
(c,a)1
.若
(c,a)k1,
令
q
是
k
的一个质因子 ，则有

q|c,q|a.
因
c|ab
，则
q|a b
，从而
q|b.
于是
q
是
a
、
b
的一个公约数，这与
(a,b)
=1
矛盾，故
(c,a)1
.
（2）因为
c|pa
例8：设
S
n

p1
,(c,a)1,
所以
c|p.
而
p
为质数且
p3< br>，故
c1
或
cp.


(k
k1n
5
k
7
)
，求最大公约数
d(S
n,S
3n
).
（第26届IMO预选题）
【解】能过具体计算可猜想
S
n
2(12

n)
4
2(
n (n1)
4
).
此式不难用数学归纳法获证.
2
为求< br>d(S
n
,S
3n
)
，对
n
分奇偶来讨论 .
（1）当
n2k
时，
d(2[


2 k(2k1)
4
6k(6k1)
4
],2[])(2k
4(2k1)
4
,281k
4
(6k1)
4
).< br>
22
和
6k1
互质，所以
d2k((2k1),81 ).
而当
k3t1
时
44
44
由于
2k1

4

(2k 1)81(2t1),k3t1
时，
(2k1)
与81互质.故此时有


n
4
81
44
281k281
4
n,当n6t2时;


8
2

d



2k
4

1
n
4
,当n6t6或6t4时(t0).

8

（2）当当
n2k1
时
d(2[(2k1)(k1)],2[3(2k1)(3k 2)).

444
因3k2与2k1,k1
与质，所以
k2 (2k1)((k1),3).
而当
k3t2
时，
44
< br>k13(t1),k3k2
时，
k1
与3
4
互质 .故此时有
4444


2(2k1)32n3162n,当n 6t5时;
d


44


2(2k1) 2n当n6t1或6t3时).
例9：
m
盒子中各若干个球，每一次在其中< br>n(nm)
个盒中加一球.求证：不论开始的分布
情况如何，总可按上述方法进行有限 次加球后使各盒中球数相等的充要条件是
(m,n)1.

（第26届IMO预选题）
【证明】设
(m,n)1
，则有
u ,vZ
使得
unvm1v(m1)(v1)
，此式说明：
对盒 子连续加球
u
次，可使
m1
个盒子各增加了
v
个，一个增 加
(v1)
个.这样可将多增加

了一个球的盒子选择为原来球数最少 的那个，于是经过
u
次加球之后，原来球数最多的盒子
中的球与球数最少的盒子中的球 数之差减少1，因此，经过有限次加球后，各盒球数差为0，
达到各盒中的球数相等.
用反 证法证明必要性.若
(m,n)d1
，则只要在
m
个盒中放
m 1
个球，则不管加球
多少次，例如，加球
k
次，则这时
m
个 盒中共有球
m1kn
（个），因为
d|m,d|n,d1,
所以
m1kn
不可能是
d
的倍数，更不是
m
的倍数，各盒中的球决 不能一样多，因此，
必须
(m,n)1
.
例10：求所有这样的自然数< br>n
，使得
2
8
2
11
2
n
是一 个自然数的平方.
（1980年第6届全俄数学竞赛试题）
【证明】（1）当
n 8
时，
N222(2
811n8n
2
11n
1)
，因（…）为奇数，
所以要使N为平方数，
n
必为偶数.逐一验证< br>n2,4,6,8
知，N都不是平方数.


（2）当
n9
时，
N222211
不是平方数. （3）当
n10
时，
N2(92
n8
8n8
81198
)
，要N为平方数，
92
n8
应为奇数的平方，不< br>妨假设
92
=
(2k1)
,则
2
2n10(k1)(k2).
由于
k1
和
k2
是一奇一偶， 左边
n10
为2的幂，因而只能
k1
=1，于是得
k2
，由
2




2
2
知
n12
为所求.