性质4实质上是求最大公约数的一种方法，这种方法叫做辗转相除法。
性质5若b∣a,则[a,b]=a.
性质6若[a,b]=m,且n为正整数，则[na,nb]=nm.
性质7若n∣a,n∣b,则
.
4、数的整除性
定义3 对于整数a和不为零的整数b，如果存在整数q，使得a=bq成立，则就称b整除a或a被b整除，记作b∣a，若b∣a，我们也称a是b倍数；若b不能整除a，记作ba
5、数的整除性的性质
性质1若a∣b，b∣c，则a∣c
性质2若c∣a，c∣b，则c∣（a±b）
性质3若b∣a,n为整数，则b∣na
6、同余
定义4设m是大于1的整数，如果整数a，b的差被m整除，我们就说a，b关于模m同余，记作a≡b（modm）
7、同余的性质
性质1如果a≡b（modm），c≡d（modm），
那么a±c≡b±d（modm），ac≡bd（modm）
性质2如果a≡b（modm），那么对任意整数k
有ka≡kb（modm）
性质3如果a≡b（modm），那么对任意正整数k
有ak≡bk（modm）
性质4如果a≡b（modm），d是a，b的公约数，
那么
二、例题精讲
例1设m和n为大于0的整数，且3m+2n=225.如果m和n的最大公约数为15，求m+n的值（第11届“希望杯”初一试题）
解：
（1）因为（m,n）=15,故可设m=15a，n=15b，且（a,b）=1
因为3m+2n=225，所以3a+2b=15
因为a,b是正整数，所以可得a=1,b=6或a=b=3，但（a,b）=1，所以a=1,b=6
从而m+n=15（a+b）=157=105
评注：
1、遇到这类问题常设m=15a，n=15b，且（a,b）=1，这样可把问题转化为两个互质数的求值问题。
这是一种常用方法。
2、思考一下，如果将m和n的最大公约数为15，改成m和n的最小公倍数为45，问题如何解决？
例2 有若干苹果，两个一堆多一个，3个一堆多一个，4个一堆多一个，5个一堆多一个，6个一堆多一个，问这堆苹果最少有多少个？
分析：
将问题转化为最小公倍数来解决。
解 设这堆苹果最少有x个，依题意得
由此可见，x-1是2，3，4，5，6的最小公倍数
因为 [2,3,4,5,6]=60，所以x-1=60，即x=61
答：
这堆苹果最少有61个。
例3 自然数a1，a2，a3，…，a9，a10的和1001等于，设d为a1，a2，a3，…，a9，a10的最大公约数，试求d的最大值。
解 由于d为a1，a2，a3，…，a9，a10的最大公约数，所以和a1+a2+a3+…+a9+a10＝1001能被d整除，即d是1001＝7
11
13的约数。
因为dak，所以ak≥d，k＝1，2，3，…，10
从而1001＝a1+a2+a3+…+a9+a10≥10d
所以
由d能整除1001得，d仅可能取值1，7，11，13，77，91。
因为1001能写成10个数的和：
91+91+91+91+91+91+91+91+91+182
其中每一个数都能被91整除，所以d能达到最大值91
例4某商场向顾客发放9999张购物券，每张购物券上印有四位数码，从0001到9999号，如果号码的前两位之和等于后前两位之和，则这张购物券为幸运券，如号码0734，因0+7=3+4，所以这个号码的购物券为幸运券。
证明：
这个商场所发购物券中，所有幸运券的号码之和能被101整除。
（第7届初中“祖冲之杯”数学邀请赛试题）
证明：
显然，9999的购物券为幸运券，除这张外，若号码为n的购物券为幸运券，则号码为m=9999-n的购物券也为幸运券。
由于9999是奇数，所以m，n的奇偶性不同，即m≠n，由于m+n=9999，相加时不出现进位。
就是说，除号码为9999的幸运券外，其余所有的幸运券可两两配对，且每对号码之和为9999，从而可知所有的幸运券的号码之和为9999的倍数。
由101∣9999，所以所有幸运券的号码之和能被101整除。
评注：
本题是通过将数两两配对的方法来解决。
例5在1，2，3，…，1995这1995个数中，找出所有满足条件的数来：
（1995+a）能整除1995
a（第五届华杯赛决赛试题）
分析：
分子、分母都含有a，对a的讨论带来不便，因此可以将
化成
，这样只有分母中含有a，就容易对a进行讨论。
解
因为（1995+a）能整除1995
a，所以
是整数，从而
是整数
因为1995
1995=32
52
72
192，所以它的因数1995+a可以通过检验的方法定出。
注意到1≤a≤1995，所以1995<1995+a≤3990
如果1995+a不被19整除，那么它的值只能是以下两种：
3
52
72=3675，32
5
72=2205
如果1995+a能被19整除，但不被192整除，那么它的值只能是以下两种：
3
72
19=2793，52
7
19=3325
如果1995+a能被192整除，那么它的值只能是以下两种：
7
192=2527，32
192=3249
于是满足条件的a有6个，即从上面6个值中分别减去1995，得到
1680、210、798、1330、532、1254
评注：
本题通过对
的适当变形，便于对a的讨论。
讨论时通过将1995
1995分解质因数，然后将因数1995+a通过检验的方法定出。
这种方法在解决数的整除问题中经常使用。
例611+22+33+44+55+66+77+88+99除以3的余数是几？
为什么？
（第四届华杯赛复赛试题）
解显然11≡1（mod3），33≡0（mod3），66≡0（mod3），99≡0（mod3）
又22=4≡1（mod3），44≡14≡1（mod3），55≡25≡（-1）5≡（-1）（mod3），
77≡17≡1（mod3），88≡（-1）8≡1（mod3）
∴11+22+33+44+55+66+77+88+99≡1+1+0+1-1+0+1+1+0≡4≡1（mod3）
即所求余数是1
评注：
用同余式求余数非常方便。
例7已知：
，问a除以13，所得余数是几？
（第三届华杯赛决赛试题）
分析：
将a用十进制表示成
，1991除以13，所得余数是显然的，主要研究
除以13的余数规律。
解
mod13，103≡（-3）3=-27≡-1，
1+104+108≡1-10+102=91≡0，1991≡2
∴a≡
≡
=-18≡8，即a除以13，所得余数是8
例8n是正偶数，a1,a2,…,an除以n，所得的余数互不相同b1,b2,…,bn除以n，所得的余数也互不相同。
证a1+b1，a2+b2，…，an+bn除以n，所得的余数必有相同的。
证明∵n是正偶数，所以n-1为奇数，
∴
不是n的倍数，
∵a1,a2,…,an除以n，所得的余数互不相同，所以这n个余数恰好是0，1，…，n-1.从而a1+a2+…+an≡0+1+…+（n-1）=
0（modn）
同样b1+b2+…+bn≡
0（modn）
但（a1+b1）+（a2+b2）+…+（an+bn）=（a1+a2+…+an）+（b1+b2+…+bn）≡
≡0（modn）
所以a1+b1，a2+b2，…，an+bn除以n，所得的余数必有相同的。
例9十进制中，44444444的数字和为A，A的数字和为B，B的数字和为C，求C
分析：
由于10≡1（mod9），所以对整数a0，a1，a2，…，an有
它表明十进制中，一个数与它的各位数字和模9同余。
根据上述结论有C≡B≡A≡44444444（mod9）.所以只要估计出C的大小，就不难确定C
解：
4444≡7（mod9），而73≡（-2）3=-8≡1（mod9），
所以44444444≡74444=731481+1≡7（mod9），
所以C≡B≡A≡44444444≡7（mod9），
另一方面，44444444<（105）4444=1022220，所以44444444的位数不多于22220从而A<922220=199980，即A至多是6位数。
所以B<96=54在1到53的整数中，数字和最大的是49，所以C≤4+9=13在小于13的自然数中，只有7模9同余于7，所以C=7
评注：
本题用了十进制中，一个数与它的各位数字和模9同余这个结论。
根据这个结论逐步估计出C的大小，然后定出C。
三、巩固练习
选择题
1、两个二位数，它们的最大公约数是8，最小公倍数是96，这两个数的和是（A）
A、56B、78C、84D、96
2、三角形的三边长a、b、c均为整数，且a、b、c的最小公倍数为60，a、b的最大 公约数是4，b、c的最大公约数是3，则a+b+c的最小值是（B）
A、30B、31C、32D、33
3、在自然数1，2，3，…，100中，能被2整除但不能被3整除的数的个数是（B）
A、33B、34C、35D、37
4、任意改变七位数7175624的末四位数字的顺序得到的所有七位数中，能被3整除的数的个数是（D）
A、24B、12C、6D、0
5、若正整数a和1995对于模6同余，则a的值可以是（C）
A、25B、26C、27D、28
6、设n为自然数，若19n+14≡10n+3（mod83），则n的最小值是（B）
A、4B、8C、16D、32
填空题
7、自然数n被3除余2，被4除余3，被5除余4，则n的最小值是59
8、满足[x,y]=6，[y,z]=15的正整数组（x,y,z）共有2组
9、一个四位数能被9整除，去掉末位数后得到的三位数是4的倍数，则这样的四位数中最大的一个，它的末位数是
10、有一个11位数，从左到右，前k位数能被k整除（k=1,2,3,…,11），这样的最小11位数是
11、设n为自然数，则32n+8被8除的余数是
12、14+24+34+44+…+19944+19954的末位数是
解答题
13、求两个自然数，它们的和是667，它们的最小公倍数除以最大公约数所得的商是120。
14、已知两个数的和是40，它们的最大公约数与最小公倍数的和是56，求这两个数。
15、五位数
能被12整除，它的最末两位数字所成的数
能被6整除，求出这个五位数。
16、若a,b,c,d是互不相等的整数，且整数x满足等式（x-a）（x-b）（x-c）（x-d）=9
求证：
4∣（a+b+c+d）
17、一个数是5个2，3个3，2个5，1个7的连乘积，这个数当然有许多约数是两位数，这些两位约数中，最大的是多少？
18、求2400被11除，所得的余数。
19、证明31980+41981被5整除。
20、xi=1或-1（i=1，2，…，1990），证明
升级会员 