整除

1)整除概念

2)整除性质

1. 若b|a，c|a，且b和c互质，则bc|a
2. 若a|b，b|a，则|a|=|b|
3. 若b|a，则b|ac c∈Z
4. 若a|b，b|c，则a|c
5. 若a|b，则(m*a)|(m*b) a,b,m∈Z && m≠0
6. 对任意非零整数a，±a|a=±1。
7. 若a|b，a|c,则 a|(b*x+c*y),a,b,c,x,y∈Z
8. 若m|(a+b) 则m|(a-b)
9. a*x+b*y=1 x,y∈Z && a|n,b|n ,then (a*b)|n

证明

设n=a*q,n=b*w

则nb=a*b*q,na=a*b*w

则ab|na,ab|nb 由⑦可知 ab|(na*x+nb*y)

ab|n(a*x+b*y)故当a*x+b*y==1时,a*b|n

1. 如果甲数能被乙数整除，乙数能被丙数整除，那么甲数能被丙数整除。
2. 如果两个数都能被一个自然数整除，那么这两个数的和与差都能被这个自然数整除。
3. 如果一个数能分别被几个两两互质的自然数整除，那么这个数能被这几个两两互质的自然数的乘积整除。
4. 如果一个质数能整除两个自然数的乘积，那么这个质数至少能整除这两个自然数中的一个。
5. 几个数相乘，如果其中一个因数能被某数整除，那么乘积也能被这个数整除。
6. 对任意整数a，b>0，存在唯一的数对q，r，使a=bq+r，其中0≤r带余除法定理，是整除理论的基础。
7. 若c|a，c|b，则称c是a，b的公因数。若d是a，b的公因数，d≥0，且d可被a，b的任意公因数整除，则d是a，b的最大公因数。若a，b的最大公因数等于1，则称a，b互素，也称互质。累次利用带余除法可以求出a，b的最大公因数，这种方法常称为辗

3)整除特性

3)例题练习题1

例题1.四位数“3AA1”是9的倍数，那么A=_____。

练习（1） 在“25□79这个数的□内填上一个数字,使这个数能被11整除,方格内应填_____。

练习（2）已知一个五位数□691□能被55整除,所有符合题意的五位_____。

例题2. 1至100以内所有不能被3整除的数的和是_____。

练习 所有能被3整除的两位数的和是___。

例题3.能同时被2、3、5整除的最大三位数是_____。

练习 能同时被2、5、7整除的最大五位数是_____。

例题4. 173□是个四位数字，数学老师说：“我在这个□中先后填入3个数字,所得到的3个四位数,依次可被9、11、6整除。”问：数学老师先后填入的3个数字的和是多少？

练习  在1992后面补上三个数字，组成一个七位数，使它们分别能被2、3、5、11整除，这个七位数最小值是多少？

3)练习题2

1. 讲分别写有数字3,7,8的三张卡片排除三位数abc,使他是43的倍数,求abc
2. 求被 7除，余数是3的最小的三位数。
3. 求被 7除，余数是4的最大的四位数。
4. 从1开始，依次写出1234..20032004，这个多位数除以9 的余数是多少?
5. 一个两位数与 109 的乘积为四位数，它能被 23 整除且商是一位数，这个两位数最大等于多少?
6. 已知六位数a9786b是99的整数倍，这个六位数除以 99 的商是多少?
7. 判断 15158 能否被 7、11 或13 整除。
8. 六位数2012ab能被 18 整除，则两位数ab最大是多少?
9. 在所有五位数中，各位数字之和等于 43，且能够被 11 整除的数有多少个?其中最大的一个五位数是?
10. 有72名学生共捐款a94.9b元，那么平均每人捐了多少元?
11. 已知五位数x679y能被8和9 整除，则x+y 是多少?
12. 一个六位数567abc能被99整数,这个六位数最小是多少?
13. 七位数a7358bc能分别被9，25和8整除。求a,b,c。
14. 若四位数7a6a能被 11 整除，那么a 表示哪个数?
15. 如果653整除ab2347，则 a+b=。

同余

1)同余概念

2)同余性质

1. 反身性：a≡a(mod m)。
2. 对称性：若a≡b(mod m)，则b≡a(mod m)。
3. 传递性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)。
4. 同余式相加：若a≡b(mod m),c≡d(mod m),则a±c≡b±d(mod m)。
5. 同余式相乘：若a≡b(mod m),c≡d(mod m),则a*c = b*d(mod m)。
6. 除法：若a*c≡b*d(mod m),则a≡b(mod m/gcd(c,m))。
7. 特殊地,gcd(c,m)=1则a≡b(mod m)。
8. 幂运算。若a≡b(mod m),那么aⁿ≡bⁿ(mod m)
9. 若a≡(mod mᵢ),(i=1,2,...,n),则a≡b(mcd m₁,m₂,...mn]),其中m1,m2,...mₙ|表示m₁,m₂,...mₙ的最小公倍数。
10. a*b mod m = (a mod m) * (b mod m) mod m
11. a mod p = x; b mod q = x; 若gcd(p,p)=1,则a mod p*q=x

3)同余-初级习题(略)

3)同余-中级习题

1. 2001 年元旦是星期一，问 20 年后的元旦是星期几？
2. 某年级有将近 400 名学生。有一次演出节目排队时出现：如果每 8 人站成一列则多余 1 人；如果改为每 9 人站成一列则仍多余 1 人；结果发现现成每 10 人结成一列，结果还是多余 1 人；同学们你们知道该年级共有学生多少名吗？
3. 计算机录入员平均每分钟可以输入 72 个汉字，输入一篇有x679y个汉字的文章所用的分钟数恰好是整数，求五位数x679y。

3)同余-高级习题

1. 证明:任意平方数除以4,余数为0或1;
2. 证明:任意平方数除以8,余数为0或1或4;
3. 证明:一个十进制数被9除所得的余数,等于它的各位数字被9除所得的余数;
4. 证明:2903ⁿ-803ⁿ-464ⁿ+261ⁿ能被1897整除,n是任意正整数;
5. 证明:5555²²²²+2222⁵⁵⁵⁵能被7整除;

3)同余-终极习题(实际不难)

3)同余-编程题