小奥数论1-整除和余数知识点总结及经典例题.pdf

《小奥数论1-整除和余数知识点总结及经典例题.pdf》由会员分享，可在线阅读，更多相关《小奥数论1-整除和余数知识点总结及经典例题.pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、除c，且ab互质，则ab的积能整除c; a个连续自然数中必恰有一个数能被a整除。2.22.2 数的整除的判别法数的整除的判别法末位判别法末位判别法整除数整除数2 2 和和 5 5特征特征好朋友好朋友 1010，1 1 个零，所以判断末个零，所以判断末 1 1 位；位；.z.-2 2：末：末 1 1 位能被位能被 2 2 整除；尾是整除；尾是 0 0、2 2、4 4、6 6、8 8；5 5：末：末 1 1 位能被位能被 5 5 整除；尾是整除；尾是 0 0、5 5；4 4 和和 25258 8 和和 1251251616 和和 625625好朋友好朋友 100100，2 2 个零，所以判断末个零

3、，所以判断末 2 2 位；位；4 4 或或 2525：末：末 2 2 位数是位数是 4 4（或（或 2525）的倍数）的倍数好朋友好朋友 10001000，3 3 个零，所以判断末个零，所以判断末 3 3 位；位；8 8 或或 125125：末：末 3 3 位数是位数是 8 8（或（或 125125）的倍数）的倍数好朋友好朋友 1000010000，4 4 个零，所以判断末个零，所以判断末 4 4 位；位；1616 或或 625625：末：末 4 4 位数是位数是 1616（或（或 625625）的倍数）的倍数数字和判别法（用以判别能否被数字和判别法（用以判别能否被 3 3 或或 9 9 整除

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

5、1，直到够减。余数的判断法与整数位的判断法一致。三位一截判别法（用以判别能否被三位一截判别法（用以判别能否被 7/11/137/11/13 整除）整除）基本用法基本用法从右往左三位一截并编号， 编号为奇数的为奇数段， 编号为偶数的为偶数段，看奇数段的数字的和与偶数段的数字的和的两者之差是否能被 7、11、13 整除；如，86372548，奇数段的和为（548+86） ，偶数段的和为372，求两者差看能.z.-否被 7 整除，同样，不够减前面加 1 个或多个 7，直到够减，余数位的判断法与整数位的判断法一致。特殊用法特殊用法 一般求空格数一般求空格数如果中间有空格，则利用加减性加或减除数 7 的

6、倍数，分别从右边和左边抵消缩减位数，到最后看 7 的哪个倍数与缩减后的末位数相同，并看 7 的哪个倍数与缩减后的首位数相同， 则前一个倍数的十位数和后一个倍数的个位数的和即为空格中应填的数。注意，如果这个数加或减7 后为 1 到 9 间的自然数，则加或减7 后的这个数也为正确答案。39586482365，答案为 546392501234，答案为 1 和 8 特殊求空格数特殊求空格数根据整除的因数性，如果 1 个数能被 1001 整除，则这个数能被 7、11、13、77、91、143 整除，因为：71113=1001;7713=1001;9911=1001;7143=1001;根据整除的空格数=

7、1001;=1001;求能被 7.z.-有关有关 9 9 系列截判法（用以判别能否被系列截判法（用以判别能否被 9/99/9999/99/999 整除）整除）除数是几位数就可以从右往左几位一截， 将截取的段位数相加再截取，直至不能再截取，看相应的数能否被相应的除数 9/99/999 整除。除数是 11 时，也可以用两位一截判别法，因为根据整数的因数性，能被 99整除的数，肯定能被 11 整除。例如：2.32.3 余数的判别法余数的判别法余数的定义和性质余数的定义和性质 整除是余数为 0 的情况。ab=c.0；此时，a= bc;b= ac 有余数的情况：ab=c.d（0db） ；此时，a=bc+

8、d;b=(a-d)c; c=(a-d)b记着：ad(modb)余数的判别法（与整除相同）余数的判别法（与整除相同）【注意】【注意】 ：当被除数是比除数小的非零自然数，则被除数为余数；当被除数比余数大，则减：当被除数是比除数小的非零自然数，则被除数为余数；当被除数比余数大，则减去除数的倍数所得比除数小的数即为余数。去除数的倍数所得比除数小的数即为余数。序号序号1 12 23 34 45 5除数除数2 2 和和 5 54 4 和和 25258 8 和和 1251251616 和和 6256253 3 或或 9 9余数判别法余数判别法特别要点特别要点末末 1 1 位判断法；位判断法； 看末看末 1

9、1 位能否被位能否被 2 2 整除；尾是整除；尾是 0 0、2 2、4 4、6 6、8 8 能；能；看末看末 1 1 位能被位能被 5 5 整除；尾是整除；尾是 0 0、5 5 能；能；末末 2 2 位判断法位判断法末末 2 2 位数是位数是 4 4（或（或 2525）的倍数即能被）的倍数即能被 4 4 或或 2525 整除整除末末 3 3 位判断法；位判断法； 末末 3 3 位数是位数是 8 8（或（或 125125）的倍数）的倍数末末 4 4 位判断法；位判断法； 末末 4 4 位数是位数是 1616（或（或 625625）的倍数）的倍数数字和法；数字和法；各数位上数字的和是各数位上数字的

10、和是 3 3 或或 9 9 的倍数，则能被的倍数，则能被 3 3 或或 9 9 整除。整除。弃弃 3 3（9 9）法；）法；.z.-利用整除的加减性，可以去掉利用整除的加减性，可以去掉1 1 个或多个个或多个 9 9（包括几个数（包括几个数的和是的和是 3 3 或或 9 9 的倍数的也可划掉）的倍数的也可划掉） ， 剩下数字的和剩下数字的和* *再除以再除以3 3 或或 9 9； 如果如果* *9, 9,则余数为则余数为*-9;*-9; 如如*=0,*=0,则余数为则余数为 0 0， 能整除；能整除；如果如果* *9, 9,则余数为则余数为* *。6 6三位一截奇偶三位一截奇偶位求差判别法位求

11、差判别法从右往左三位一截并编号，从右往左三位一截并编号， 编号为奇数的为奇数段，编号为奇数的为奇数段， 编号编号为偶数的为偶数段，为偶数的为偶数段， 看奇数段的数字的和与偶数段的数字看奇数段的数字的和与偶数段的数字的和的两者之差是否能被的和的两者之差是否能被7 7、1111、1313 整除；整除；如，如，8637254886372548，奇数段的和为（，奇数段的和为（548+86548+86） ，偶数段的和为，偶数段的和为372372，求两者差看能否被，求两者差看能否被 7 7 整除，同样，不够减前面加整除，同样，不够减前面加 1 1个或多个个或多个 7 7，直到够减；，直到够减；7 7111

12、1、9999两位一截求和两位一截求和再截判别法再截判别法两位一截，两位一截， 将截取的段位数相加再截取，将截取的段位数相加再截取， 直至不能再截取，直至不能再截取，看能否被看能否被 1111 或或 9999 整除，注意，根据整数的因数性，能被整除，注意，根据整数的因数性，能被9999 整除的数，肯定能被整除的数，肯定能被 1111 整除。整除。8 8奇偶数字和求奇偶数字和求差判别法差判别法从右往左编号，从右往左编号， 编号为奇数的为奇数位，编号为奇数的为奇数位， 编号为偶数的为编号为偶数的为偶数位，偶数位， 看奇数位上的数字的和与偶数位上的数字的和的看奇数位上的数字的和与偶数位上的数字的和的两

13、者之差是否能被两者之差是否能被 1111 整除；整除；817290338172903311:11:奇数位和为奇数位和为 6 6，偶数位和为偶数位和为 2727；如果奇数位和比偶数位和小，则奇数位；如果奇数位和比偶数位和小，则奇数位和加和加 1 1 个或多个个或多个 1111，直到够减。，直到够减。1111 可以无敌乱切，但还可以无敌乱切，但还是常用奇偶位截断求差法；是常用奇偶位截断求差法；9 999999910101111三位一截求和三位一截求和再截法再截法四位一截求和四位一截求和法法从右往左三位一截，从右往左三位一截， 将截取的段位数相加再截取，将截取的段位数相加再截取， 直至不直至不能再截

14、取，看相应的数能否被能再截取，看相应的数能否被 999999 整除。整除。从右往左四位一截，从右往左四位一截， 将截取的段位数相加，将截取的段位数相加， 看相应的数能看相应的数能否被否被 1111 整除。整除。7 7、1111、1313（10011001）1111如：56768，除以 2,5,4,25,8,125,3,9,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+210+110+8+6+4+2=53.z.-115

15、-53=62；6211，余 7；【例】求被 13 除余数是多少？解：注意 13|111111，即每连续 6 个 1 是 13 的倍数，且 2012 除以 6 余 2，所以答案为 11【例】把自然数 1 到 2011 这 2011 个数依次写下来，得到一个很大的多位数：1112.20102011，则这个数除以 9 余数是 1.无敌乱切，按 1/2/3/4 到 2011 的等差数列求和，看除以 9 的余数；同余定理同余定理同余定义和充要条件同余定义和充要条件定义定义: : 用给定的正整数 m 分别除整数 a、b，如果所得的余数相等，则称 a、b 关于模 m 同余或 a 同余于 b 模 m，记作ab

16、(mod m)，如 560 （mod 8） ，式子称为同余式，m 称为该同余式的模。充要条件：充要条件：整数 a,b 对模 m 同余的充要条件是 a-b 能被 m 整除（即 m|a-b） ；或 ab(mod m)的充要条件是 a=mt+b（t 为整数） 。基本定理基本定理同余关系具有自身性、对称性与传递性，即1）自身性：aa (mod m);2）对称性：若 ab (mod m), 则 ba (mod m);3）传递性：若 ab (mod m), bc (mod m)，则 ac (mod m).z.-重要定理：一个同余式的加减乘及幂的运算重要定理：一个同余式的加减乘及幂的运算定理定理 1 1 若

17、 ab(mod m),n 为自然数，则 anbn (mod m)；即 a、b 关于关于模m 同余，则 a、b 的同倍数也关于模 m 同余；定理定理 2 2 若 cacb(mod m), (c,m)=d （最大公约数） , 且 a,b 为整数， 则 ab(modm/d).推论推论若 ca=cb(mod m), (c,m)=1,且 a,b 为整数，则 ab(mod m).定理定理 3 3 若 ab (mod m),ab (mod n),则 ab(mod m,n).推论推论若 ab(mod mi), i=1,2,n，则 ab (mod m1,m2,.,mn).【例】将 1996 加上一个整数，使和能

18、被 9 和 11 整除，加的整数尽可能小，则加的整数是多少？199616(mod 99)；99-16=83定理定理 4 4 若 ab (mod m),则 anbn(modm),其中 n 是自然数。同余定理的重要推论：两个同模同余式的加减乘运算同余定理的重要推论：两个同模同余式的加减乘运算若 ab(mod m), cd (mod m),则可以将这两个同余式左右两边分别相加、相减或相乘：1）a+cb+d (mod m);即和的余数等于余数的和2）a-cb-d (mod m);即差的余数等于余数的差；3）acbd (mod m)；即积的余数等于余数的积；【例】316419813 除以 13 所得的余

19、数.z.-只知被除数和余数，求除数或求商只知被除数和余数，求除数或求商余数确定（注意余数比除数小）余数确定（注意余数比除数小）有余数的情况：ab=c.d（0db） ；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）=m（）+（a+b+c）=m（）+25（63+90+130-25）=m（）258=m（）258 的约数有 8 个：1/2582/1293/866/43因为余数

20、要小于除数，判断 9m63；所以 m=43.z.- 余数不确定余数相同余数不确定余数相同【例 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，即求这两个数的公约数，分别有 1 和 19，答案为 19。 余数不确定余数的差余数不确定余数的差【例 3】97=m（商）+a+329=m（）+a变为 94=m（）+a,根据同余定理：m（94-29）= m（65） ；65 的约数有 1/65,5/13， 除

21、数大于余数， 排除 1 和 65,5 和 13 都满足； 余数不确定余数的倍数余数不确定余数的倍数【例 4】61=m（商）+2a90=m（）+a变为 180=m（）+2a,根据同余定理：.z.-m（180-61）= m（119） ；119 的约数有 1/119,7/17， 除数大于余数， 排除 1 和 119,仅 17 满足；幂和连乘积的余数余数的周期性幂和连乘积的余数余数的周期性周期性的用法：可用以求*个数的若干次方的个位数：【例】的个位数：3 的若干次方的个位数，依次枚举，找出循环规律，4 个一个周期，2015 除以 4，余几为周期第几个。幂的余数的求法：幂的余数的求法：先求底数的余数，再

22、算底数的幂的余数的周期性，再根据指数相应的周期来确定最终的余数；【例】除以 7 的余数：1（mod7）6,36,196,1176除以 7 的余数分别为 6,1,6,1，2 个为 1 周期，1002=50 余 0，故余数为 1。特殊情况： 【例】除以 8 的余数：.z.-1（mod8）9 除 8 的余数为 1，所以无论指数多少，余数皆为 1。【例】除以 9 的余数：【例】除以 7 的余数：【例】+除以 7 的余数： 作业 5，2 的 3 次方以上模 8 的余数皆为 0中国剩余定理物不知数（信点兵）中国剩余定理物不知数（信点兵）传统题目和传统解法传统题目和传统解法【题目】今物知其数三三数剩二（数除

23、三余数二意思）,五五数剩三,七七数剩二,问物几何（信点兵算所谓剩余定理）【解法】三人同行七十稀；把除以 3 所得的余数用 70 乘五树梅花廿一枝；把除以 5 所得的余数用 21 乘；七子团圆正半月；把除以 7 所得的余数用 15 乘除百零五便得知；把上述三个积加起来,除以 105 的余数即为得数；270+321+215=233233105=223；得数为 23。物不知数：余数问题的通解：基本的枚举法物不知数：余数问题的通解：基本的枚举法 从除数大的开始枚举；.z.- 先找同时满足两个除数的最小符合数，再加这俩除数的最小公倍数，直到满足所有除数的最小的符合数； 再加所有除数的最小公倍数n，直到符

24、合题意；【例】3 余 2，5 余 3，7 余 2，求满足条件的数；【注意】 从除数大的着手；【例】5 余 4,97 余 1； 1,98,195，得 389； 找最小符合数时不要忽略商为 0 的情况；【例】*除 48 余 23，除 49 余 23；*最小的答案就是 23；【例】例3：49 余 23,48 余 23；最小符合数为23，连续两个自然数的最小公倍数为其积；4849 能整除 14，余数是 0,23 除 14 的余数，全是 9。 在所有除数的最小公倍数一定能找到最小的满足数； 多个符合数必然是一个以所有除数的最小公倍数为等差的等差数列物不知数：余数问题的通解：特殊情况物不知数：余数问题的通

25、解：特殊情况 余数相同的最小符合数就是余数最小符合数就是余数，其他的为除数的最小公倍数的倍数+余数（即最小符合数（即最小符合数+ +除数的最小公倍数的倍数）除数的最小公倍数的倍数） ；【例】5 余 4,7 余 4,9 余 4，最小的为 4；【例】*除 4、除 5、除 6 皆余 1，*=4/5/6 的公倍数+1； 差相同的余数都不相同但除数与余数的差相同的，最小符合数为除最小符合数为除数的最小公倍数数的最小公倍数- -差差；其他符合数为除数的最小公倍数的倍数-差（也即（也即最小符合数最小符合数+ +除数的最小公倍数的倍数）除数的最小公倍数的倍数） ；.z.-【例】5 余 3,7 余 5,9 余

26、7：都补上两个的就都整齐了，所以为最小公倍数-2；为 313；【例】5 千多根火柴棍，10 根一盒的分余 9，9 根一盒的分余 8，8 根一盒的分余 7，7 根一盒的分余 6，6 根一盒的分余 5，5 根一盒的分余 4，问到底多少根火柴棍？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=25192519+2520=5039【例】有不足 100 个苹果，如果是 10 个一堆，则剩余 9 个；9 个一堆剩余 8 个；6 个一堆剩余 5 个；5 个 1 堆剩余 4 个；3 个一堆剩 2 个；求开

27、始有多少个苹果？【10,9,6,5,3】-1=89 和相同余数都不相同的，但除数与余数的和相同的，可以转化为同余的，最小符合数就为最小的除数最小符合数就为最小的除数+ +余数；余数；其他的符合数为除数的最小公倍数的倍数+和（也即最小符合数（也即最小符合数+ +除数的最小公倍数的倍数）除数的最小公倍数的倍数） ；【例】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 个的

28、最小公倍数；.z.-物不知数：可以用来解决除以物不知数：可以用来解决除以 1212 和和 6 6 的余数的算法：互质分解的余数的算法：互质分解求 A=123456319 被 12/14/15/45/99 除的余数；将 12 互质分解=43,求同时满足除以 4 和除以 3 的；A3（mod4）;A(1+2+3+.+319)(1+319)319216031911（mod3）4 余 3,3 余 1，最小符合数为 7，其他符合数为 7+12n所以 A7（mod12）;【注意】 常见的互质分解有： 12=43,14=27,15=35,45=59， 99=911； 105=357，其中 105 的频率最高

29、；【例】5 余 4,97 余 1； 1,98,195，得 389； 99 有两种算法，两位截断法和互质分解；求 A=123123123 被 99 除的余数123 个 123互质分解法：将 99 互质分解=911,求同时满足除以 9 和除以 11 的；A123123660（mod9）;.z.-A(62123)- (61123)1232（mod11）9 余 0,11 余 2，最小符合数为 90，其他符合数为 90+99n所以 A90（mod99）;两位截断法：A(23+31+12)61+ (123)6661+244026+2466+2490（mod99） 求 A=201620162016 被 49

30、5 除的余数100 个 2016互质分解法： 将 495 互质分解=957,求同时满足除以 9 余 0， 除以 5 余 1，除以 11 余 9 的物不知数，即为余数；物不知数：非典型物不知数题目转为物不知数题目物不知数：非典型物不知数题目转为物不知数题目【例 1】三个非 0 的连续自然数，分别是 3、5、7 的倍数，找出符合要求的最小的一组自然数；设 n,n+1,n+2 分别能被 3、5、7 整除，则n3 余 0， （n+1）5 余 0， （n+2）7 余 0，.z.-3 余 0，5 余 4，7 余 51954答案为 54、55、56【例 2】三个非0 的连续自然数，分别是7、9、11 的倍数

31、，找出符合要求的最小的一组自然数；设 n,n+1,n+2 分别能被 7、9、11 整除，则n7 余 0， （n+1）9 余 0， （n+2）11 余 07 余 0，9 余 8，11 余 953350答案为 350、351、352图 1:2m+(m+1)=a=3m+1;图 2:3n+2(n+1)=a=5n+2;图 3:4*+3(*+1)=a=7*+3;所以，3m+1=5n+2，m=除 3 余 1，除 5 余 2；除 7 余 3；根据物不知数通常求法，得出 a=52作业 6：如果倒过来不够减怎么办，-450 时，前面加一个够减的 7 的倍数就可以；例 2：19 余 9,23 余 7；用余数来取代，7+23 的倍数，模 19 时，变为 7+4 的倍数，列举除19 余 9 的数直到符合的，9,28,47，从 47 往回导出倍数为 10，再往.z.-；与辗转相除法类似；.z.回算为 237