弟子规读后感600字-大学生社会实践报告格式

第十七章 整数问题

第十七章 整数问题
一、常用定义定理
1．整除：设a,b∈Z,a≠0，如果存在q∈Z使得b=aq，那么称b可被a整除，记作a|b， 且
称b是a的倍数,a是b的约数。b不能被a整除，记作a b.
2 带余数除法： 设a,b是两个给定的整数，a≠0，那么，一定存在唯一一对整数q与r，
满足b=aq+r,0≤r <|a|，当r=0时a|b。

3．辗转相除法：设u
0
,u
1< br>是给定的两个整数，u
1
≠0，
u
1
u
0
,由2可得下面k+1个等式：u
0
=q
0
u
1
+u2
,02
<|u
1
|；
u
1
= q
1
u
2
+u
3
,03
2
；
u
2
=q
2
u
3
+u
4< br>,04
3
；
…
u
k-2
=q
k-2
u
1
+u
k-1
+u
k
,0 k
k-1
；
u
k-1
=q
k- 1
u
k+1
,0k+1
k
；
u
k
=q
k
u
k+1
.
4．由3可得： （1）u
k+1
=(u
0
,u
1
)；（2）d|u
0
且d|u
1
的充要条件是d|u
k+1
；（3）存在整数x 0
,x
1
，使u
k+1
=x
0
u
0< br>+x
1
u
1
.
5．算术基本定理：若n>1且n为整数，则
np
1
1
p
2
2
p
k
k，其中p
j
(j=1,2,…,k)是质数
（或称素数），且在不计次序的意义下 ，表示是唯一的。
6．同余：设m≠0,若m|(a-b)，即a-b=km，则称a与b模同m同余 ，记为a≡b(modm)，也
称b是a对模m的剩余。
7．完全剩余系：一组数y
1
,y
2
,…,y
s
满足：对任意整数a有且仅有一个y
j
是a对模m的剩余，
即a≡y
j
(modm)，则y
1
,y
2
,…,y
s
称为模m的完全剩余系。
p-1p
8．Fe rmat小定理：若p为素数，p>a,(a,p)=1，则a≡1(modp)，且对任意整数a,有a≡a(modp).
9．若(a,m)=1，则
a

(m)
aa
a
≡1(modm),

(m)称欧拉函数。
a
1
1
10．（欧拉函数值的计算公式）若
mppp
，则

(m) =
m

(1
a
2
2
a
k
kk
i1
1
).

p
i
11．（孙子定理）设 m
1
,m
2
,…,m
k
是k个两两互质的正整数，则同余组 ：
x≡b
1
(modm
1
),x≡b
2
(mod m
2
),…,x≡b
k
(modm
k
)有唯一解，
'
x≡
M
1
M
1
b
1
+
M2
M
2
b
2
+…+
M
k
M
k
b
k
(modM)，
''
其中M=m
1
m
2
m
k
；
M
i
=
M
，i=1,2,…, k；
M
i
'
M
i
≡1(modm
i
),i =1,2,…,k.
m
i
二、方法与例题
1．奇偶分析法。
例1 有n个整数，它们的和为0，乘积为n，（n>1），求证：4|n。



2．不等分析法。

1

第十七章 整数问题

例2 试求所有的正整数n，使方程x+y+z=nxyz有正整数解。






3．无穷递降法。
22222
例3 确定并证明方程a+b+c=ab的所有整数解。





4．特殊模法。
例4 证明：存在无穷多个正整数，它们不能表示成少于10个奇数的平方和。




5．最小数原理。
442
例5 证明：方程x+y=z没有正整数解。








6．整除的应用。
333222
n
3
1
例6 求出所有的有序正整数数对(m,n)，使得是整数。
mn1









7．进位制的作用

2

第十七章 整数问题

例7 能否选择1983个不 同的正整数都不大于10，且其中没有3个正整数是等差数列中的
连续项？证明你的结论。







三、习题精选
2
1．试求所有正整数对(a,b)，使得(ab-a+b+1)|(ab+1).
2222
2．设a,b,c∈N
+
，且a+b-abc是不超过c+1的一个正整数， 求证：a+b-abc是一个完全平
方数。
22
3．确定所有的正整数数对(x,y )，使得x≤y，且x+1是y的倍数，y+1是x的倍数。
n2
4．求所有的正整数n，使得存在正整数m,(2-1)|(m+9).
5．求 证：存在一个具有如下性质的正整数的集合A，对于任何由无限多个素数组成的集合，
存在k≥2及正整 数m∈A和n

A，使得m和n均为S中k个不同元素的乘积。
6．求最小的正整数 n(≥4)，满足从任意n个不同的整数中能选出四个不同的数a,b,c,d使
20|(a+b-c- d).
7.对于正整数a,n,定义F
n
(a)=q+r，其中q,r为非负整数， a=qn+r且0≤r≤n，求最大正整
数A，使得存在正整数n
1
,n
2< br>,…,n
6
，对任意正整数a≤A，都有
5
F
n
(< br>F
n
(
F
n
(
F
n
(
F< br>n
(
F
n
(
a
)

)
=1 ，并证明你的结论。
6
5
4321
8．设x是一个n位数，问：是否总存在 非负整数y≤9和z使得10z+10x+y是一个完全平
方数？证明你的结论。
9．设a, b,c,d∈N
+
,且a>b>c>d,ac+bd=(b+d+a-c)(b+d-a+c) 。证明：ab+cd不是素数。
w.w.w.k.s.5.u.c.o.m
n+1

第十八章 组合
一、方法与例题
1．抽屉原理。
例1 设整数n≥4,a
1
,a
2
,…,a
n
是 区间(0,2n)内n个不同的整数，证明：存在集合{a
1
,a
2
,…,a
n
}
的一个子集，它的所有元素之和能被2n整除。
w.w.w.k.s.5.u.c.o.m
[证明] （1）若n

{a
1
,a
2
,…,a
n
},则n个不同的数属于n-1个集合{1,2 n-1}，
{2,2n-2},…,{n-1,n+1}。由抽屉原理知其中必存在两个数a
i
,a
j
(i≠j)属于同一集合，从而
a
i
+a
j
=2n被2n整除；
（2）若n∈{a
1
,a
2
,…,a
n
}，不妨设a
n
=n，从a
1
,a
2
, …,a
n
-1
(n-1≥3)中任意取3个数a
i
, a
j
, a
k
(a
i
,j
<
a
k
)，则a
j
-a
i
与a
k
-ai
中至少有一个不被n整除，否则a
k
-a
i
=(a
k
-a
j
)+(a
j
-a
i
)≥2n，这与a
k
∈(0,2n)
矛盾，故a
1
,a
2
,…,a
n-1
中必有两个数之差不被n整除；不妨设a
1
与a
2
之差(a< br>2
-a
1
>0)不被n
整除，考虑n个数a
1
,a< br>2
,a
1
+a
2
,a
1
+a
2+a
3
,…,a
1
+a
2
+…+a
n-1。
ⅰ）若这n个数中有一个被n整除，设此数等于k
n
，若k为偶数，则结论成 立；若k为奇数，
则加上a
n
=n知结论成立。
ⅱ）若这n个数中没有一个 被n整除，则它们除以n的余数只能取1,2,…,n-1这n-1个值，

3

第十七章 整数问题

由抽屉原理知其中必有两个数除以n的余数相 同，它们之差被n整除，而a
2
-a
1
不被n整除，
故这个差必为a
i
, a
j
, a
k-1
中若干个数之和，同ⅰ）可知结论成立。
2 极端原理。
例2 在n×n的方格表的每个小方格内写有一个非负整数，并且在某一行和某一列的交叉
点处如果写有0，那 么该行与该列所填的所有数之和不小于n。证明：表中所有数之和不小
于
1
2
n
。
2
[证明] 计算各行的和、各列的和，这2n个和中必有最小的，不妨设第 m行的和最小，记
和为k，则该行中至少有n-k个0，这n- k个0所在的各列的和都不小于n-k，从而这n-k列
的数的总和不小于(n-k)
2
，其余各列的数的总和不小于k
2
，从而表中所有数的总和不小于
(nkk)< br>2
1
2
n.
(n-k)+k≥
22
22
3.不变量原理。
俗话说，变化的是现象，不变的是本质，某一事情反复地进行，寻找不变量是一种策略。
例3 设正整数n是奇数，在黑板上写下数1，2，…，2n，然后取其中任意两个数a,b,擦
去这两个数， 并写上|a-b|。证明：最后留下的是一个奇数。
[证明] 设S是黑板上所有数的和，开始时和 数是S=1+2+…+2n=n(2n+1)，这是一个奇数，因
为|a-b|与a+b有相同的奇偶性 ，故整个变化过程中S的奇偶性不变，故最后结果为奇数。
例4 数a
1
, a< br>2
,…,a
n
中每一个是1或-1，并且有S=a
1
a
2
a
3
a
4
+ a
2
a
3
a< br>4
a
5
+…+a
n
a
1
a
2
a
3
=0. 证明：4|n.
[证明] 如果把a
1
, a< br>2
,…,a
n
中任意一个a
i
换成-a
i
， 因为有4个循环相邻的项都改变符号，S
模4并不改变，开始时S=0，即S≡0，即S≡0(mod4 )。经有限次变号可将每个a
i
都变成1，
而始终有S≡0(mod4)，从而有n≡ 0(mod4)，所以4|n。
4．构造法。
例5 是否存在一个无穷正整数数列a1
,2
3
<…，使得对任意整数A，数列
{a
n
A}

n1
中
仅有有限个素数。
3
[证明] 存在。取a
n
=(n!)即可。当A=0时，{a
n
}中没有素数；当|A|≥2时，若n≥|A|，
2
则a
n
+A均为 |A|的倍数且大于|A|，不可能为素数；当A=±1时，a
n
±1=(n!±1)•[(n !)±
3
n!+1]，当≥3时均为合数。从而当A为整数时，{(n!)+A}中只有有限个 素数。
例6 一个多面体共有偶数条棱，试证：可以在它的每条棱上标上一个箭头，使得对每个顶< br>点，指向它的箭头数目是偶数。
[证明] 首先任意给每条棱一个箭头，如果此时对每个顶点 ，指向它的箭头数均为偶数，则
命题成立。若有某个顶点A，指向它的箭头数为奇数，则必存在另一个顶 点B，指向它的箭
头数也为奇数（因为棱总数为偶数），对于顶点A与B，总有一条由棱组成的“路径” 连结
它们，对该路径上的每条棱，改变它们箭头的方向，于是对于该路径上除A，B外的每个顶
点，指向它的箭头数的奇偶性不变，而对顶点A，B，指向它的箭头数变成了偶数。如果这
时仍有顶点， 指向它的箭头数为奇数，那么重复上述做法，又可以减少两个这样的顶点，由
于多面体顶点数有限，经过 有限次调整，总能使和是对每个顶点，指向它的箭头数为偶数。
命题成立。
5．染色法。
例7 能否在5×5方格表内找到一条线路，它由某格中心出发，经过每个方格恰好一次，
再 回到出发点，并且途中不经过任何方格的顶点？
[解] 不可能。将方格表黑白相间染色，不妨设黑格为13个，白格为12个，如果能实现，

4

第十七章 整数问题

因黑白格交替出现，黑白格数目应相等，得出矛盾，故不可能。
6．凸包的使用。
给定平面点集A，能盖住A的最小的凸图形，称为A的凸包。
例8 试证：任何不自交的五边形都位于它的某条边的同一侧。
[证明] 五边形的凸五包是凸五边形、凸 四边形或者是三角形，凸包的顶点中至少有3点是
原五边形的顶点。五边形共有5个顶点，故3个顶点中 必有两点是相邻顶点。连结这两点的
边即为所求。
7．赋值方法。
例9 由2× 2的方格纸去掉一个方格余下的图形称为拐形，用这种拐形去覆盖5×7的方格
板，每个拐形恰覆盖3个 方格，可以重叠但不能超出方格板的边界，问：能否使方格板上每
个方格被覆盖的层数都相同？说明理由 。
[解] 将5×7方格板的每一个小方格内填写数-2和1。如图18-1所示，每个拐形覆盖的 三
个数之和为非负。因而无论用多少个拐形覆盖多少次，盖住的所有数字之和都是非负的。另
一 方面，方格板上数字的总和为12×(-2)+23×1=-1，当被覆盖K层时，盖住的数字之和等
于 -K，这表明不存在满足题中要求的覆盖。
-2
1
-2
1
-2
1
1
1
1
1
-2
1
-2
1
-2
1
1
1
1
1
-2
1
-2
1
-2
1
1
1
1
1
-2
1
-2
1
-2

8．图论方法。
例10 生产由六种颜色的纱线织成的双色布，在所生产的双色布中，每种 颜色的纱线至少
与其他三种颜色的纱线搭配过。证明：可以挑出三种不同的双色布，它们包含所有的颜色 。
[证明] 用点A
1
，A
2
，A
3
，A4
，A
5
，A
6
表示六种颜色，若两种颜色的线搭配过，则在相 应的
两点之间连一条边。由已知，每个顶点至少连出三条边。命题等价于由这些边和点构成的图
中有三条边两两不相邻（即无公共顶点）。因为每个顶点的次数≥3，所以可以找到两条边不
相邻，设为 A
1
A
2
，A
3
A
4
。
（1） 若A
5
与A
6
连有一条边，则A
1
A
2
， A
3
A
4
，A
5
A
6
对应的三种双色布满 足要求。
（2）若A
5
与A
6
之间没有边相连，不妨设A
5
和A
1
相连，A
2
与A
3
相连，若A
4
和A
6
相连，则
A
1
A
2
，A
3
A
4
，A
5
A
6
对应的双色布满足要求；若A4
与A
6
不相连，则A
6
与A
1
相连，A2
与A
3
相
连，A
1
A
5
，A
2
A
6
，A
3
A
4
对应的双色布满足要求。
综上，命题得证。
二、习题精选
1．药房里有若干种药，其中一部分药是烈性的。 药剂师用这些药配成68副药方，每副药方
中恰有5种药，其中至少有一种是烈性的，并且使得任选3种 药恰有一副药方包含它们。试
问：全部药方中是否一定有一副药方至少含有4种烈性药？（证明或否定）
2．21个女孩和21个男孩参加一次数学竞赛，（1）每一个参赛者最多解出6道题；（2）对
每一个女孩和每一个男孩至少有一道题被这一对孩子都解出。求证：有一道题至少有3个女
孩和至少有 3个男孩都解出。
3．求证：存在无穷多个正整数n，使得可将3n个数1, 2,…, 3n排成数表
a
1
, a
2
…a
n

b
1
, b
2
…b
n

c
1
, c
2
…c
n


5

第十七章 整数问题

满足：（1）a
1
+b
1
+c
1
= a
2
+b
2
+c
2
=…= a
n
+b
n
+c
n
=，且为6的倍数。
（2）a
1
+a
2
+…+a
n
= b
1
+b
2
+…+b
n
= c
1
+c
2
+…+c
n
=，且为6的倍数。
4． 给定正整数n，已知克数都是正整数的k块砝码和一台天平可以称出质量为1，2，…，n
克的所有物品 ，求k的最小值f(n)。
5．空间中有1989个点，其中任何3点都不共线，把它们分成点数各不 相同的30组，在任
何3个不同的组中各取一点为顶点作三角形。试问：为使这种三角形的总数最大，各 组的点
数应分别为多少？
6．在平面给定点A
0
和n个向量a
1< br>，a
2
，…，a
n
，且使a
1
+a
2
+…+a
n
=0。这组向量的每一个排
列
a
i
,ai
,

,a
i
12
n
都定义一个点集：A1
，A
2
，…，A
n
=A
0
，使得
a
i
A
0
A
1
,a
i
A
1A
2
,,a
i
A
n1
A
n
< br>12
n
求证：存在一个排列，使由它定义的所有点A
1
，A
2
，…，A
n-1
都在以A
0
为角顶的某个60
0
角 的内部和边上。
7．设m, n, k∈N，有4个酒杯，容量分别为m,n,k和m+n+k升，允 许进行如下操作：将一个
杯中的酒倒入另一杯中或者将另一杯倒满为止。开始时，大杯中装满酒而另3个 杯子却空着，
问：为使对任何S∈N，Sm,n,k的充分必要条件是什么？
8．设有30个人坐在一张圆桌的周围，其中的 每个人都或者是白痴，或者是聪明人。对在座
的每个人都提问：“你右边的邻座是聪明人还是白痴？”聪 明人总是给出正确的答案，而白
痴既可能回答正确，也可能回答不正确。已知白痴的个数不超过F，求总 可以指出一位聪明
人的最大的F。
9．某班共有30名学生，每名学生在班内都有同样多的朋 友，期末时任何两人的成绩都可分
出优劣，没有相同的。问：比自己的多半朋友的成绩都要好的学生最多 能有多少人？
w.w.w.k.s.5.u.c.o.m



6