第二讲整除与同余教师版.docx
《第二讲整除与同余教师版.docx》由会员分享，可在线阅读，更多相关《第二讲整除与同余教师版.docx（20页珍藏版）》请在冰点文库上搜索。
第二讲整除与同余教师版
、整数的进位制
1、【十进制数】给定一个
m位的正整数
10
的m1次多项式，即A
m1
am110
i01,2,L,m1且am1
2、【p进制数】若十进制正整数A
第二讲整除与同余
A，其各位上的数字分别记为am1,am2,,a。
A可以表示成
m2
am210
Aam1am
可以表示为:
a{0,1,2,L,p1},i0,,,2,L,m1且am10,
ai10a°，其中
ai{0,1,2,L,9},
2a0.
m1
Aam1pam2
m仍然为十进制数，则称
a1pa，其中
p进制数，记为
A（am1am2a0）p.
【例题分析】
位数•
解:
由于
100
abc
999，则100
（a
b
3
c）999，从而5ab
c!
9；
当a
b
c
5时，
53
125
（1
2
5）3;
3
当abc6时，6
216
（21
6）3;
当a
b
c
7时，
73
343
（3
4
3）3;
3
当abc8时，8
512
（51
2）3;
当a
b
c
9时，
93
729
（7
2
9）3;
bc）3的所有三位数
于是所求的三位数只有512.
3.一个四位数，它的个位数字与百位数字相同。
如果将这个四位数的数字顺序颠倒过来（即个位数字与
千位数字互换，十位数字与百位数字互换），所得的新数减去原数，所得的差为7812，求原来的四位数。
解：
设该数的千位数字、百位数字、十位数字分别为x,y,z，则
32
原数10x10y10zy①;
QO
颠倒后的新数103y102z10yx②
由②—①得7812=999（yx）90（zy）
2
即868111（yx）10（zy）10（yx）10（zx）（yx）③
比较③式两端百位、十位、个位数字得yx8,zx6.
由于原四位数的千位数字x不能为0,所以x1，从而yx89，又显然百位数字y9,
所以y9,x1,zx67，所以所求的原四位数为1979.
二、整除的概念及其性质
（1）、基本概念
1、定义：
设a,b是给定的整数，b0，若存在整数c，使得abe,则称b整除a，记作b|a，并称b是a的一个约数（或因数），称a是b的一个倍数，如果不存在上述e，则称b不能整除a，记作a.
2、整除的性质
（1）若b|e且e|a，则b|a（传递性）；
⑵若b|a且b|e，则b|（ae）；
若反复运用这一性质，易知b|a及b|e，则对于任意的整数u,v有b|（auev）;
n
更一般，若a|bi，则a|Cib其中eZ,i1,2,L,n；
i1
⑶若b|a，则或者a0，或者|a||b|;特别地，若b|a且a|b，则ab；
（4）（带余除法定理）
设a,b为整数，b0，则存在一对整数q和r，使得abqr，其中0rb，满足以上条件的整数q和r是唯一确定•整数q称为a被b除得的商，数r称为a被b除得的余数。
注意：
r共有b种可能的取值：
0,1,……,b1；若r0，即为a被b整除的情形；
（5）若n是正整数，则xnyn（xy）（xn1xn2yxyn2yn1）；
nm
（6）如果在等式abk中去掉某一项外，其余项均为e的倍数，则去掉项也是e的倍数；
i1k1
（7）m（m>2且mZ）个连续整数中，有且只有一个是m的倍数；
（8）任何n（n>2且nZ）个连续的整数之积一定是n!
的倍数，特别地，三个连续正整数之积能被6整除;
（9）若一个整数的未位数字能被2（或5）整除，则这个数能被2（或5）整除，否则不能；
（10）一个整数的数码之和能被3（或9）整除，则这个数能被3（或9）整除，否则不能；
（11）若一个整数的未两位数字能被4（或25）整除，则这个数能被4（或25）整除，否则不能；
（12）若一个整数的未三位数字能被8（或125）整除，则这个数能被8（或125）整除，否则不能；
（13）若一个整数的奇位上的数码之和与偶位上的数码之和的差是11的倍数，则这个数能被11整除，
否则不能。
（14［①质数：
一个大于1的正整数，如果它的因数只有1和它本身，则称为质数或素数；
②合数：
如果一个正整数包含有大于1且小于其本身的因子，则称这个正整数为合数。
（2）、奇数、偶数的性质
（1）奇数奇数=偶数，偶数偶数=偶数，奇数偶数=奇数，偶数偶数=偶数，奇数偶数=偶数，奇数奇数=奇数；任意多个偶数的和、差、积仍为偶数，奇数个奇数的和、差仍为奇数，偶数个奇数的
和、差为偶数•
（2）奇数的平方都可以表示成8m1的形式，偶数的平方可以表示为8m或8m4的形式，其中mZ；
（3）任何一个正整数n，都可以写成n2ml的形式，其中m为负整数，|为偶数。
（4）若有限个整数之积为奇数，则其中每个整数都是奇数；若有限个整数之积为偶数，则这些整数中至少有一个是偶数；两个整数的和与差具有相同的奇偶性；偶数的平方根若是整数，它必为偶数。
（3）、完全平方数及其性质
能表示为某整数的平方的数称为完全平方数，简称为平方数，平方数有以下性质：
（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，必定是一个平方数。
（4）、格点：
数学上把在平面直角坐标系中横纵坐标均为整数的点称为格点或整点
【例题分析】
3、（2007）设数列an满足：
a1=1,%1=5anJ24%21,nN，求证：
a的各项都是正整数
4、（2009）证明：
平面直角坐标系xoy内存在不在一条直线上的2009个整点，使得每条直线上至少有
3个整点，且任意两点的距离都是整数
5、（2008）
对每一实数对Ly,函数f（i）wJEr（x+y）-f（x）+f（y>+xy+lf若1（-2〉--2,试求满足f（a）=a的所有整数雲
显然ab，令（a,b）d，则aaid,bbid，（a^bj1
22
从而ab=（a1b1）d，将其代入①得2a1da1b13b1d②
2
因为d|2a1d，所以d|（印bj，从而d印d；
2
而②式又可写成Gb1）（2a12b11）b1d；
因为（a,b）d且（a1,b1）1，所以（a1b1,b1）1（a1b1）
所以佝bi）|d，从而a1b1d。
所以da1b1，所以ab=⑻bjdd2，从而ab为完全平方数。
三、同余的定义及其性质
【定义1】.设m是正整数，若用m去除整数a,b，所得的余数相同，则称a与b关于模m同余，记作
ab（modm），否则称a与b关于模m不同余，记作a*b（modm）.
例如：
344（mod15）,10001（mod7）,9^8（mod2）等等。
当0bm时，ab（modm），则称b是a对模m的最小非负剩余。
对于固定的模m，通常有下面的性质：
性质1.ab（modm）的充要条件是amtb,tZ也即m|（ab）。
性质2.同余关系满足以下规律：
（1）（反身性）aa（modm）;
（2）（对称性）若ab（modm），则ba（modm）；
（3）（传递性）若ab（modm）,bc（modm），贝Uac（modm）;
（4）（同余式相加）若ab（modm）,cd（modm），贝Uacbd（modm）；
（5）（同余式相乘）若ab（modm）,cd（modm），则acbd（modm）；
注意：
①反复利用（4）（5）,可以对多于两个的（模相同的）同余式建立加、减和乘法的运算公式；
....kk
2特别地，由（5）易推出：
若ab（modm），k,c为整数且k0,则acbc（modm）；
3同余式的消去律一般并不成立，即从acbc（modm）未必能推出ab（modm），可是我们却有
以下结果：
若acbc（modm），贝Uabmod―m.
（m,c）
由此可以推出：
（6）若（c,m）1,acbc（modm），则有ab（modm），即在c与m互素时，可以在原同余式两边约
去c而不改变模.
（7）若ab（modm）,dIm，则ab（modd）;
（8）若ab（modm）,d0，贝Udadb（moddm）；
（9）若ab（modm）（i1,2L,k），则ab（mod[m^m?
Lm]），特别地，若
m「m2丄，mk两两互素时，则有ab（modm!
m?
LmQ；
kkkk
性质3.若aibi（modm）,i1,2,,k，贝Ua,b,（modm）；a,b,（modm）；
i1i1i1i1
性质4.设f（x）是系数全为整数的多项式，若ab（modm），贝Uf（a）f（b）（modm）。
这一性质在计算时特别有用：
在计算大数字的式子时，可以改变成与它同余的小数字，使计算大大地简化。
整数集合可以按模m来分类，确切地说，若a和b模m同余，则a和b属同一类，否则不属于同一类，每一个这样的类为模m的一个同余类。
由带余除法，任一整数必恰与0,1,……,m1中的一个模m同余,
而0,1,,m1这m个数彼此模m不同余，因此模m共有m个不同的同余类，例如，模2的同余类
共有两个，即通常说的偶数类与奇数类，这两类中的数分别具有形式2k和2k1（k为任意整数）•
【例题分析】
1、（2006年3）在集合1,2,3,L,50的子集S中任意两个元素和都不能被7整除，这样的子集S中元素
C23
个数最多的是（）A22
2、（2005年15）试求最小的正整数n，使得对于任何n个连续正整数中，必有一数，其各位数字之和是
【练习题】
P
1、已知p,q为质数，且p3q17,则—
5q1
2、由7个数字0,1,2,3,4,5,6组成且能被55整除的最小七位数是
3、a为正整数，记2a1,2a2,2a3表示2a1,2a2,2a3的最小公倍数，以A表示它若2a4
整除A，贝Ha=
4、设p是给定的奇质数，正整数k使得：
—pk也是一个正整数，则k=
5、对于正整数n，如果能找到正整数a,b，使nabab，则称n为“好数”，则在前100个正整数
中，共有“好数”的个数为
6、设n是整数，且4n217n15表示两个相邻正整数的积，则n二
7、设1m99,1n99，则使得（mn）23mn是完全平方数的有序整数对（m,n）的个数为
8•设k1是一个奇数，证明：
对于任意正整数n，数1k2knk不能被n2整除。
10.1987可以在b进制中写成三位数xyz，如果xyz1987，试确定所有可能的x,,y,z和
b。
11.证明不存在正整数n，使2n2+1，3n2+1
6n2+1都是完全平方数。
12.证明：
对于任意正整数n，数1200522005
n2005不能被n2整除。
13.已知n为正奇数，求证：
60|6n3n2n1.
14.设a、b、c为满足不等式1vavbvc的整数，且
ab-1）（bc-1）（ca-1）能被abc整除，求所
有可能数组（a,b,c）
【试题参考答案】
」、填空题
1、当p
2时，q5；当p11时，q2；综上：
一^1或1.
5q113
2、性质：
若一个整数的奇位上的数码之和与偶位上的数码之和的差是11的倍数，则这个数能被11整除,
否则不能•设该七位数为10abcd5，于是abcd=15,116acbd,6acbd21
七位数为：
1042635.
3、任意连续三个正整数互质，则A2a12a22a3，由a2
A,得a=1.
4、设k2pk
n乙则
即2kp
2kp
2n
2n
5、由nab
ab知，a
1,即n
1是合数，前
101
个正整数中共有26个，好数个数:
101-26=74
6、设4n2
17n
152n
2n
14n2
kk1，故n
2
kk15
15
4k
当k0时,
n1;当k
2时,
当k3时,
7•解：
由于
1m99，
2
99可得：
（mn）
2
3mnv（mn）4（m
n）
2
4（mn2）
2
又（mn）
（mn）2
3mn，于是（m
22
n）（mn）
3mn（mn
2）2
若（mn）2
3mn是完全平方数，则必有
2
（mn）3m
n=（mn1）2。
2
然而（mn）3m
n=（mn1）2n
m1，于是必有
此时n1,2丄,98，
m2,3丄,99。
所以所求的有序整数对
m,n）共有98对:
（m,n）
（2,1）,（3,2）,（4,3）,L,（99,98）。
、简答题
8.证明：
n1时,
结论显然成立。
设n2，记所说的和为A，则：
2A2（2k
kk、
（3（n1））
/k、
（n2）
k
由k是正奇数，从而结于每一个i2，数i（n
i）被i（n2i）n2整除,
故2A被n2除
得余数为2，从而A不可能被n2整除（注意n
2）。
9•证明：
首先，当nm时，易知结论成立。
事实上,
mn时，结论平凡；当
m时，结果可由
2n12m112m1推出来（注意m2）。
最后，nm的情形可化为上述特殊情形：
由带余除法n
mp
r,0r
而q0，由于
2n1（2mq1）2r2r1,从而由若n是正整数
（xy）（xn1
n2n1.
xyy）知
（2m1）|（2mq1）；而0rm，故由上面证明了的结论知
（2m
1）
r
（21）
（注意r
0时结论平
凡）,从而当nm时，也有（2m1）（2n1）。
22
10.解：
易知xb1987,xyz25，从而x（b1）y（b1）162,
2
即（b1）[（b1）xy]1962232109,
由b10知b19。
由1962b21知b196345故9
b145;
又因为1962232109有12个正约数，分别为1,2,3,6,
9,18,109,218,327,654,981,1962，所以
b118，从而b19。
又由1987519291911知x
5,y9,z11.
11.证明不存在正整数n，使2n2+1,3n2+1,6n2+1都是完全平方数。
证明：
假设存在这样的正整数n，使2n2+1,3n2+1,6n2+1都是完全平方数，那么（
2n2+1）（3n2+1）
（6n2+1）也必定是完全平方数。
而（2n2+1）（3n2+1）（6n2+1）=36n6+36n4+11
n2+1；
3232
（6n3n）36n6+36n4+9n2；（6n3n1）
36n6+36n4+12n3+9n2+6n+1
所以（6n33n）2（2n2+1）（3n2+1）（6n2+1）
（6n3
3n1）
2与（2n2+1）（3n2+1）（6n2+1）为
完全平方数矛盾。
12.证明：
对于任意正整数n，数1200522005
2005n
不能被
n2整除。
即可。
证明：
只需证2（n2）2（严522005n2005）
因为若n是正整数，则
yn（xy）（xn1
n2
xy
1）；
若n是正奇数，则xn
n1n2
（xy）（xxy
n
xy
20052005
2I2n;
2|32005（n1）
2005
2005
2In
亠2005
2
所以
2005
n2I2（2
2005、
n）。
又因为n
32，所以n22,
所以
n2005）+2,即（
2厂2（12005
2?
005
n2005）命题得证。
已知n为正奇数，求证:
60|6n3n2n
证明：
因为若n是正整数，则
nn
y（xy）（x
xy
若n是正奇数，则
yn（xy）（xn
n2
xy
1）；
所以3|6n
nn
3,3|2
从而3|6n3n
2n
n
4|6
2n,4|3n
从而4|6n3n
2n
5|6n
nn
1,5|32,
从而5|6n3n
2n
又（3,4,5）
1且34560，所以60|6n
3n
2n
14.设a、b、c为满足不等式1vavbvc的整数，且（ab-1）（bc-1）（ca-1）能被abc整除，求所有可能数组（a，b，c）
解'/（ab-1）（bc-1）（ca-1）=a2b2c2-abc（a+b+c）+ab+ac+bc-1
Tabc|（ab-1）（bc-1）（ca-1）二存在正整数k,使ab+ac+bc-仁kabc,②
111111133
k=口0Qv必亡v口EQvEvZ.・.k=1.
11111114?
_十一-+—_+_十_=
.只有a=2
若a>3，此时1=-』-■二…八-v矛盾，已知a>1,
2+2纟十2=A_
当a=2时，代入②中得2b+2c-仁be，即
1=：
-工V〔一〔L
••0vbv4，知b=3，从而易得c=5.
升级会员 