小奥数论整除和余数知识点总结及例题

1、2.1 基本概念和基本性质整数 a 除以整数 b （ b 0，）除得的商是整数而没有余数，我们就说a 能被 b 整除，或者 说 b 能整除 a。b a，读着 b 能整除 a;或 a 能被 b 整除； ba ，不能整除；传递性：如果a|b,b|c, 那么 a|c; 即 b 是 a 的倍数， c 是 b 的倍数，则 c 肯定是 a 的倍数；加减性：如果a|b 、a|c ，那么 a|(b c);因数性：如果ab|c ，那么 a|c， b|c; 即如果 ab 的积能整除 c,则 a 或 b 皆能整除 c;互质性，如果a|c ，b|c ，且（ a,b ） =1, 那么 ab|c,即如果 a 能整除 c,

2、b 能整除 c，且ab 互质，则ab 的积能整除 c;2.2a 个连续自然数中必恰有一个数能被 a 整除。整除数特征2和5好朋友 10，1 个零，所以判断末 1 位；2：末 1 位能被 2 整除；尾是 0 、2、4 、6、8；5：末 1 位能被 5 整除；尾是 0 、5；4 和 25好朋友 100 ， 2 个零，所以判断末 2 位；4 或 25：末 2 位数是 4（或 25 ）的倍数8 和 125好朋友 1000 ， 3 个零，所以判断末 3 位；8 或 125 ：末 3 位数是 8（或 125 ）的倍数数的整除的判别法16 和625好朋友 10000 ，4 个零，所以判断末 4 位；16 或

3、 625 ：末 4 位数是 16 （或 625 ）的倍数各数位上数字的和是 3 或 9 的倍数，则能被 3 或 9 整除。173652 ÷9:1+7+3+6+5+2 的和除以 3 或 9； 简便算法，利用整除的加减性，可以去掉 1 个或多个 9，剩下数字的和 x 再除以 3 或 9；如果 x9,则余数为 x-9; 如果 x9,则余数为 x。从右往左编号，编号为奇数的为奇数位，编号为偶数的为偶数位，看奇数 位上的数字的和与偶数位上的数字的和的两者之差是否能被 11 整除；奇数位和为 6 ，偶数位和为 27 ；如果奇数位和比偶数位和小，则奇数位和 加 1 个或多个 11 ，直到够减。余数

4、的判断法与整数位的判断法一致。2.2.4 三位一截判别法（用以判别能否被 7/11/13 整除）从右往左三位一截并编号，编号为奇数的为奇数段，编号为偶数的为偶数 段，看奇数段的数字的和与偶数段的数字的和的两者之差是否能被7、 11 、 13整除；两者差看能否被 7 整除，同样，不够减前面加 1 个或多个 7 ，直到够减， 余数位的判断法与整数位的判断法一致。 一般求空格数如果中间有空格，则利用加减性加或减除数 7 的倍数，分别从右边和左边 抵消缩减位数，到最后看 7 的哪个倍数与缩减后的末位数相同，并看 7 的哪个 倍数与缩减后的首位数相同，则前一个倍数的十位数和后一个倍数的个位数的 和即为空

5、格中应填的数。注意，如果这个数加或减 7 后为 1 到 9 间的自然数， 则加或减 7 后的这个数也为正确答案395864 82365 ，答案为 5463925 01234 ，答案为 1 和 8 特殊求空格数根据整除的因数性，如果 1 个数能被 1001 整除，则这个数能被 7 、11 、13 、77 、91 、143 整除，因为：7×11 ×13=1001;77×13=1001;99×11=1001;7×143=1001;根据 = ×1001; = ×1001; 求能被 7 整除的空格数 abc abc abcaaa aa

6、a aaa系列截判法(用以判别能否被 9/99/999 整除)除数是几位数就可以从右往左几位一截，将截取的段位数相加再截取，直 至不能再截取，看相应的数能否被相应的除数 9/99/999 整除。除数是 11 时，也可以用两位一截判别法，因为根据整数的因数性，能被99 整除的数，肯定能被 11 整除。例如：2.3 余数的判别法 整除是余数为 0 的情况。 a÷b=c .0 ；此时， a=b ×c;b=a ÷c 有余数的情况： a÷b=c .d(0d b )；此时， a=b ×c+d;b=(a-d) ÷c;c=(a-d) ÷b记

7、着： ad(modb)2.3.2 余数的判别法（与整除相同）注意】：当被除数是比除数小的非零自然数，则被除数为余数；当被除数比余数大，则减去除数的倍数所得比除数小的数即为余数。序号除数余数判别法特别要点12和5末 1 位判断看末 1 位能否被 2 整除；尾是 0、2、4、6、8 能；法；看末 1 位能被 5 整除；尾是 0 、5 能；24 和 25末 2 位判断法末 2 位数是 4 （或 25 ）的倍数即能被 4 或 25 整除38 和 125末 3 位判断末 3 位数是 8 （或 125 ）的倍数法；416 和 625末 4 位判断末 4 位数是 16 （或 625 ）的倍数法；5数字和法；

8、各数位上数字的和是 3 或 9 的倍数，则能被 3 或 9 整弃 3 （9）除。法；利用整除的加减性，可以去掉 1 个或多个 9 （包括几个3或9数的和是 3 或 9 的倍数的也可划掉） ，剩下数字的和 x再除以 3 或 9；如果 x 9,则余数为 x-9; 如 x=0, 则余数为 0，能整除；如果 x 9,则余数为 x 。6三位一截奇偶从右往左三位一截并编号，编号为奇数的为奇数段，编7 、11 、位求差判别法号为偶数的为偶数段，看奇数段的数字的和与偶数段的13数字的和的两者之差是否能被 7、11 、13 整除；（ 1001 ）两者差看能否被 7 整除，同样，不够减前面加 1 个或多个 7 ，

9、直到够减；711 、 99两位一截求和再截判别法两位一截，将截取的段位数相加再截取，直至不能再截 取，看能否被 11 或 99 整除，注意，根据整数的因数 性，能被 99 整除的数，肯定能被 11 整除。811奇偶数字和求差判别法从右往左编号，编号为奇数的为奇数位，编号为偶数的 为偶数位，看奇数位上的数字的和与偶数位上的数字的 和的两者之差是否能被 11 整除；奇数位和为 6 ，偶数位 和为 27 ；如果奇数位和比偶数位和小，则奇数位和加 1 个或多个 11 ，直到够减。 11 可以无敌乱切，但还是常 用奇偶位截断求差法；9999三位一截求和再截法从右往左三位一截，将截取的段位数相加再截取，直

10、至不能再截取，看相应的数能否被 999 整除。1011四位一截求和法从右往左四位一截，将截取的段位数相加，看相应的数能否被 11 整除。为 0,3,0,8,0,18【例】将 1，2,3,4，30 从左往右依次排列成一个 51 位数，这个数被 11 除的余数是多少？奇数位数字和：(0+9+8+ +1 )×2+0+9+7+5+3+1=115 偶数位数字和： 3+2 ×10+1 ×10+8+6+4+2=53115-53=62 ；62÷11 ，余 7；例】求被 13 除余数是多少？解：注意 13|111111 ，即每连续 6 个 1 是 13 的倍数，且 201

11、2 除以 6 余 2， 所以答案为 11 无敌乱切，按 1/2/3/4 到 2011 的等差数列求和，看除以 9 的余数；定义 :用给定的正整数 m 分别除整数 a、b ，如果所得的余数相等，则称 a、b 关于模 m 同余或 a 同余于 b 模 m，记作 a b(modm) ，如56 0 ( mod8 )，式子称为同余式， m 称为该同余式的模。充要条件： 整数 a,b 对模 m 同余的充要条件是 a-b 能被 m 整除(即 m|a- b )；或 a b(modm) 的充要条件是a=mt+b (t 为整数)。2.3.2.2 基本定理同余关系具有自身性、对称性与传递性，即1) 自身性： a a(

12、modm);2) 对称性：若 a b(modm), 则b a(modm);3) 传递性：若 a b(modm),b (mcodm) ，则 a c(modm).2.3.2.3 重要定理：一个同余式的加减乘及幂的运算定理 1 若 a b(modm),n 为自然数，则 an bn(modm) ；即a、b 关于关 于模 m 同余，则 a 、b 的同倍数也关于模 m 同余；定理 2 ?若 ca cb(modm),(c,m)=d(最大公约数,且)a,b 为整数，则a b(modm/d).推论若 ca=cb(modm),(c,m)=1, 且 a,b 为整数，则 a b(modm).定理 3 ?若 a b(m

13、odm),a b(modn),a 则b(modm,n).推论若 a b(modmi),i=1,2, ,an，b则(modm1,m2,.,mn).【例】将 1996 加上一个整数，使和能被 9 和11 整除，加的整数尽可能 小，那么加的整数是多少？1996 16(mod99) ；99-16=83定理 4 若 a b(modm), 则anbn(modm), 其中 n 是自然数。 两个同模同余式的加减乘运算若 a b(modm),c d(modm), 则可以将这两个同余式左右两边分别相加、 相减或相乘：1) a+c b+d(modm); 即和的余数等于余数的和2) a-c b-d(modm); 即差

14、的余数等于余数的差；3) ac b(dmodm) ；即积的余数等于余数的积；【例】 316 ×419 ×813 除以 13 所得的余数2.3.4 只知被除数和余数，求除数或求商(注意余数比除数小)有余数的情况： a÷b=c .d (0d b)；b=(a-d) ÷c;或 c=(a-d) ÷b 如果，只知 a和 d,求b 或 c【例】 1111 ÷某2 位数= ().66 余数不确定余数的和【例 1 】63=m ×()+a90=m ×()+b130=m ×()+c, 余数和为 25；( 63+90+130 )

15、=m ×()+ (a+b+c ) =m ×()+25（ 63+90+130-25 ）=m ×（）258=m ×（）258 的约数有 8 个：1/2582/1293/866/43因为余数要小于除数，判断 9m 63；所以 m=43 余数不确定余数相同【例 2 】300=m ×（商）+a262=m ×（）+a205=m ×（）+a,根据同余定理：m（300-262 ）=m （38 ）；m（262-205 ）=m （57 ）；m（300-205 ）=m （95 ）；满足两个即可，选数小的算，求同时满足能整除 38 和 57，即求

16、这两个数的公约数，分别有 1 和 19 ，答案为 19 。 余数不确定余数的差【例 3 】97=m ×（商）+a+329=m ×（）+a变为 94=m ×（）+a,根据同余定理：m（94-29 ）=m （65 ）；65 的约数有 1/65,5/13 ，除数大于余数，排除 1 和 65,5 和13 都 满足； 余数不确定余数的倍数【例 4 】61=m ×（商）+2a90=m ×（）+a变为 180=m ×（）+2a,根据同余定理：m （180-61 ）=m （119 ）；119 的约数有 1/119,7/17 ，除数大于余数，排除 1

17、和 119, 仅 17 满足；2.3.5 幂和连乘积的余数余数的周期性周期性的用法：可用以求某个数的若干次方的个位数：【例】 32015 的个位数：3 的若干次方的个位数，依次枚举，找出循环规律， 4 个一个周期， 2015 除以 4 ，余几为周期内第几个。幂的余数的求法： 先求底数的余数，再算底数的幂的余数的周期性，再根 据指数相应的周期来确定最终的余数；【例】 2015100除以 7 的余数：2015 100 6100 1（mod7）6,36,196,1176 除以 7 的余数分别为 6,1,6,1 ，2 个为 1 周期， 100 ÷ 2=50 余 0，故余数为 1。特殊情况：

18、【例】 32014 除以 8 的余数：32014 91007 1（mod8 ）9 除 8 的余数为 1 ，所以无论指数多少，余数皆为 1 。【例】 31625除以 9 的余数：【例】 14389除以 7 的余数：【例】 3333 5555 + 55553333 除以 7 的余数： 作业 5 ， 2 的 3 次方以上模 8 的余数皆为 02.3.6 中国剩余定理物不知数（韩信点兵）【题目】今物知其数三三数剩二（数除三余数二意思） ,五五数剩三 ,七七数 剩二,问物几何（韩信点兵算所谓剩余定理）【解法】三人同行七十稀；把除以 3 所得的余数用 70 乘五树梅花廿一枝；把除以 5 所得的余数用 21

19、 乘；七子团圆正半月；把除以 7 所得的余数用 15 乘 除百零五便得知；把上述三个积加起来 ,除以 105 的余数即为得数；2×70+3 ×21+2 ×15=233233 ÷105=2 23 ；得数为 23。2.3.6.2 物不知数：余数问题的通解：基本的枚举法 从除数大的开始枚举； 先找同时满足两个除数的最小符合数，再加这俩除数的最小公倍数，直到满足所有除数的最小的符合数； 再加所有除数的最小公倍数× n ，直到符合题意；【例】3 余 2，5 余3，7 余2，求满足条件的数；【注意】 从除数大的着手；【例】5 余 4,97 余1；1,98,

20、195 ，得 389； 找最小符合数时不要忽略商为 0 的情况；【例】某除 48 余23，除 49 余23 ；某最小的答案就是 23；【例】例 3：49 余 23,48 余 23 ；最小符合数为 23 ，连续两个自然数的最 小公倍数为其积； 48×49 能整除 14 ，余数是 0,23 除14 的余数，全是 9。 在所有除数的最小公倍数内一定能找到最小的满足数； 多个符合数必然是一个以所有除数的最小公倍数为等差的等差数列2.3.6.3 物不知数：余数问题的通解：特殊情况 余数相同的 最小符合数就是余数 ，其他的为除数的最小公倍数的 倍数+余数（即最小符合数 +除数的最小公倍数的倍数）

21、 ；【例】5 余 4,7 余 4,9 余 4，最小的为 4；【例】某除 4、除 5、除 6 皆余 1，某=4/5/6 的公倍数 +1； 差相同的余数都不相同但除数与余数的差相同的， 最小符合数为 除数的最小公倍数 -差；其他符合数为除数的最小公倍数的倍数 - 差 （也即最小符合数 +除数的最小公倍数的倍数） ；【例】 5 余 3,7 余 5,9 余 7 ：都补上两个的就都整齐了，所以为最小公 倍数-2；为 313 ； 【例】5 千多根火柴棍， 10 根一盒的分余 9，9 根一盒的分余 8，8 根 一盒的分余 7，7 根一盒的分余 6， 6 根一盒的分余 5，5 根一盒的分 余 4 ，问到底多少

22、根火柴棍？10 余 9，9 余 8，8 余 7，7 余 6，6 余 5：【5,6,7,8,9 】-1= 【1,2,3,4,5,6,7,8,9 ，10 】-1=2520-1=2519 2519+2520=5039【例】有不足 100 个苹果，如果是 10 个一堆，那么剩余 9 个；9 个一 堆剩余 8 个；6 个一堆剩余 5 个； 5 个 1 堆剩余 4 个； 3 个一堆剩 2 个；求开始有多少个苹果？【 10,9,6,5,3 】-1=89 和相同余数都不相同的，但除数与余数的和相同的，可以转化为 同余的， 最小符合数就为最小的除数 + 余数； 其他的符合数为除数的最 小公倍数的倍数 +和（也即

23、最小符合数 +除数的最小公倍数的倍数） ； 【例】 5 余 4,7 余 2,6 余 3 ：最小符合数为 5+4=9 ；【注意】多个除数的时候一定先看有无特殊情况；先利用部分特殊规律 的，再找一般的；【例】3 余 2,5 余 4,7 余 1，【例】3 余 1,5 余 2,7 余 2,11 余 3；先找同余， 2+35,37+ 已满足的 3 个的最小公倍数；2.3.6.4 物不知数：可以用来解决除以 12和 6 的余数的算法：互质分解求 A=123456 319 被 12/14/15/45/99 除的余数；将 12 互质分解 =4 ×3, 求同时满足除以 4 和除以 3 的；A3（mod

24、4）;A(1+2+3+ .+319)（1+319） ×319÷2160×3191×1（ mod3 ）4余 3,3 余 1，最小符合数为 7，其他符合数为 7+12 ×n所以 A7（mod12 ）;【注意】 常见的互质分解有： 12=4 ×3,14=2 ×7,15=3 ×5,45=5 ×9 ，99=9 ×11 ；105=3 ×5×7，其中 105 的频率最高；【例】5 余 4,97 余1；1,98,195 ，得 389； 99 有两种算法，两位截断法和互质分解；求 A=123123 123 被 99 除的余数；123 个 123互质分解法：将 99 互质分解 =9 ×11,求同时满足除以 9 和除以 11 的； A123×1236×60（ mod9 ） ;A（62 ×123）-（61 ×123）1232（mod11 ）9余 0,11 余 2，最小符合数为 90，其他符合数为 90+99 ×n所以 A 90 （ mod99 ）;两位截断法：A（23+31