此中三昧-木棉树

题 目:


学院

学 术 论 文





学号：
学校：
专业：
班级：
姓名：
指导老师：
时间：

【摘 要】
文中给出了整除的相关定理及其证明，以及一个整数可以被零一个整数整
除的判别法。
【关键字】
整除

素数 带余除法
Abstract:
the paper gives division, and related theorem and an integer can be
divided exactly by an integer zero method.

Key words:
division division transformation primes
一 整除的证明

定义
设a ﹑b是任意两个整数，其中
b0
，如果存在一个整数q使得等式

abq
（1）
成立，我们就说b整除a或a被b整除，记作ba
，此时我们把b叫做a的因数，把a叫作
b的倍数。

由整除的定义，不难得出整数的如下性质：

（1） 若
ab
，
bc
,则
ac
。
（2） 若
ab
i
，则
a

cb
，其中
cZ
，i
=1，2，… ,n。
ii
n
i
i1
（3） 若
ac
，则
abcb
。反之，亦成立。
（4） 若
ab< br>，则
ab
。因此，若
ab
，又
ba
，则
a b
。
（5） a ﹑b互质，若
ac
，
bc
，则
abc
。
（6）< br>p
为质数，若
pa
1
a
2
……
a
n
，则
p
必能整除
a
1
，
a
2
，… ，
a
n
中的某一个。特别
n
地，若
p
为质数，p
|
a
，则
p
|
a
.
(7) 如在 等式

a

b
i
i1k1
nm
k< br>中除开某一项外，其余各项都是c的倍数，则这一项也是c
的倍数。
（8） n个连续整数中有且只有一个是n的倍数。

（9）任何n个连续整数之积一定是n的倍数。
777
例1
：求一对整数
a,b
，满足：（1）
ab(a b)
不能被7整除：（2）
(ab)ab
能

被
7
整除。 （第25届IMO试题）
7
解
(ab)
7
a
7< br>b
7
=
7ab[(a
5
b
5
)3ab (a
3
b
3
)5a
2
b
2
(ab) ]

=
7ab(ab)(a
2
b
2
ab)
2
。
6222322
根据题设要求（1）（2）知，
7(abab)
，即7(abab)
。
2232
令
abab7
，即(ab)
2
ab343
，即
ab19
。则
a b19343
。故
可令
a18,b1
即合要求。
定理1 （带余数除法）
[1] 若a,b是两个整数，其中b>0，则存在着两个整数
q及r，使得

abqr
，
0rb
（1）
成立，而且q及r是唯一的。
证
作整数序列
… , -3b , -2b , -b , 0 ,b , 2b , 3b , …
则a必在上述序列的某两项之间，即存在一个整数q使得

qba(q1)b

成立。令
aqbr
，则
a bqr
，而
0rb
。
下面我们证明
q,r
的唯一性：设
q
1
，
r
1
是满足（2）的两个整数，则

abq
1
r
1，
0r
1
b
，
因而
bq
1
r
1
bqr
，
于是
b(qq
1
)r
r
r
，
故
bqq
1
r
1
r
。
由于
r
及
r
1
都是小于
b
的正数，所以上式右边是小于
b
的。如果
qq
1
，则上式左边≥
b
。
这是不可能的。因 此
qq
1
而
rr
1
。
证完

例2
： 设
p
和
q
均为自然数，使得

11
p11

。
1
…

13181319
q23
证明：
p
可被1979整除。 （第21届IMO试题）
证
1111
p11
)
-2
(
…
)
< br>(1
…

1319241318
q23
11111< br>
…
)
-
(1
…
)

2 313192659
111111
)
+
()
+…+
( )
=
(
66989990
111

…
)
=
1979
(
66013196611318989990
=
(1
两端同乘以
1319!
得
1319!
< br>p
=
1979

m
(mN
*
)
。 此式说明
1979|1319!p
。由
q
于
1979
为质 数，且
1979
不整除
1319!
，故
1979
p
。
证完

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

证 当
n2m时，
F(2m,1)
m

rm(2m1)
。
r1
2k1
2m

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

=
< br>r
r1
m
2k1


(2m1r)
2k1

r1
=

[r
r1
2k1
(2m1r)
2k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
整除，所以< br>F(2m,k)
也能被m整除，因
m
与
2m1
互质，所以< br>F(2m,k)
能被
m(2m1)
(即F(m,1))
整除。 类似可证当
n2m1
时，
F(2m1,k)
能被
F(2m 1,1)
整除，故
F(n,k)
能被
F(n,1)
整除。

二 整除的判别法
定理3
[2]


设
A
、
B
、
C
、
K
（素数）为正 整数，若
（1）
0B9

（2）
(10
•
C1)
可以被
K
整除：
则10
•
AB
可以被
K
整除的充要条件是：
AB•
C
可以被
K
整除。
证
若
AB
•
C
可以被
K
整除，记
AB
•
C
=< br>K
•
n
(nZ)
，则
AB
•
C
+
K
•
n

代人
10
•
AB
得：
10
•
AB
=
10(B
•
C
+K
•
n
)
B
=
(10
•
C1)< br>•
B10
•
K
•
n

由条件（2）可知：
10
•
AB
可以被
K
整除。
若
10
•
AB
可以被
K
整除， 记
10
•
AB
=
K
•
m
(mZ)，则
BK
•
m10
•
A
，
代入
AB
•
C
得
AB
•
C
=
A(K•
m10
•
A
)
•
C
=
(10< br>•
C1)
A
-
K
•
m
,由条件
（ 2）易知
AB
•
C
可以被
K
整除。
证完

要判断一个正整数
M
可以被素数
K
(
K2
、
3
、
5
)
整除，由上述令
M
=
10
•
AB
（
A
、
B满足条件（1）与（2））；再由条件（2）有
(10C1)Km
，
(mZ )
，
则只要取最小的
mZ
，使
C
Km1
Z

。重复运用上命题即可。因此，判断一个整
10
数
M
是否 能被素数
K
(
K2
、
3
、
5
)整除，可用如下差别法：
1. 先取最小的
mZ
，使它与
K
的个位数之积的个位为1，再求出
C
等于
Km
去掉个位1的数。
2. 将数
M
的个位数
(B)
和十位数以上的数
(A)分开成两部分；从十位数以上的数
(A)
中减去个位数
(B)
乘以
C
的积。
3. 重复上述运算，直至出现结果是0或一个易判别是否可以被
K
整除的数为止。
Km1
或取
C

10

4. 若最后得出结果是0或是可以被
K
整除的数，则
M
也可以被
K
整除；否则
M
不
能被
K
整除。

例4
： 判别16508388能否被13整除。
解
因为3×7=21，且13×7=91，故取C=9。
1650838
8
 72
1648
4
36
161
165076
2

6

18



54
14
3
16502
2
 27
18
13
最后得一个数是-13，易知-13可以被13整除，所以1650 8388能被13整除。


三 小结
整除是数论中的基本概念， 其在中，小学的学科中占据着重要地位，尤其是
往年的数学竞赛中，难度很大，但相关的知识点却是易被 接受！在这方面，需要
多拓展相关的知识面！

例如，我们在证明整除时也可以借助带余数除法来进行，即求得其余数为0，
类似的问题还有很多，但有一点就是学会灵活运用！

参考文献
[1]
闵嗣鹤,严士健·初等数论(第三版) [M]1 北京:高等教育出版社,20031.

[2] 刘长安•离散数学教程
[M] 西北：西北工业大学出版社，2007 .

[3] 段瑞卿•整除的一个简单判别法
[J] 成都教育学报，2003，(06).



References
[1] YanShiJian elementary theory, MinSiHe (third edition) [M]. Beijing: higher
education from January
Version of the club, 20031.
[2] LiuChangAn, discrete mathematics course northwest: [M]. Cambridge
university press, 2007 in northwest industry.
[3]
A simple DuanRuiQing, division method [J], journal of chengdu education, 2003 (6).