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

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

1、1. 数论数的整除和余数 整数a除以整数bb0，除得的商是整数而没有余数，我们就说a能被b整除，或者说b能整除a。ba，读着b能整除a;或a能被b整除；b a，不能整除； 传递性：如果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能整除c，且ab互质，那么ab的积能整除c; a个连续自然数中必恰有一个数能被a整除。整除数特 征2和5好朋友10，1个

2、零，所以判断末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或625：末4位数是16或625的倍数2.2.2数字和判别法用以判别能否被3或9整除各数位上数字的和是3或9的倍数，那么能被3或9整除。1736529:1+7+3+6+5+2的和除以3或9；简便算法，利用整除的加减性，可以去掉1个或多个9，剩下数字的和x再除以3或9；如果x

3、9,那么余数为x-9;如果x9,那么余数为x。2.2.3奇偶数位判别法用以判别能否被11整除从右往左编号，编号为奇数的为奇数位，编号为偶数的为偶数位，看奇数位上的数字的和及偶数位上的数字的和的两者之差是否能被11整除； 11:奇数位和为6，偶数位和为27；如果奇数位和比偶数位和小，那么奇数位和加1个或多个11，直到够减。余数的判断法及整数位的判断法一致。2.2.4三位一截判别法用以判别能否被7/11/13整除从右往左三位一截并编号，编号为奇数的为奇数段，编号为偶数的为偶数段，看奇数段的数字的和及偶数段的数字的和的两者之差是否能被7、11、13整除； 如，86372548，奇数段的和为548+8

4、6，偶数段的和为372，求两者差看能否被7整除，同样，不够减前面加1个或多个7，直到够减，余数位的判断法及整数位的判断法一致。 一般求空格数如果中间有空格，那么利用加减性加或减除数7的倍数，分别从右边和左边抵消缩减位数，到最后看7的哪个倍数及缩减后的末位数一样，并看7的哪个倍数及缩减后的首位数一样，那么前一个倍数的十位数和后一个倍数的个位数的和即为空格中应填的数。注意，如果这个数加或减7后为1到9间的自然数，那么加或减7后的这个数也为正确答案。39586482365，答案为546392501234，答案为1和8 特殊求空格数根据整除的因数性，如果1个数能被1001整除，那么这个数能被7、11、

5、13、77、91、143整除，因为：71113=1001;7713=1001;9911=1001;7143=1001; 根据abcabc=abc1001; aaaaaa=aaa1001;求能被7整除的空格数2.2.5有关9系列截判法用以判别能否被9/99/999整除除数是几位数就可以从右往左几位一截，将截取的段位数相加再截取，直至不能再截取，看相应的数能否被相应的除数9/99/999整除。除数是11时，也可以用两位一截判别法，因为根据整数的因数性，能被99整除的数，肯定能被11整除。例如： 整除是余数为0的情况。ab=c.0；此时，a= bc;b= ac 有余数的情况：ab=c.d0db；此时

6、，a=bc+d;b=(a-d) c; c=(a-d) b记着：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的倍数53或9数字和法；弃39法；各数位上数字的和是3或9的倍数，那么能

7、被3或9整除。利用整除的加减性，可以去掉1个或多个9包括几个数的和是3或9的倍数的也可划掉，剩下数字的和x再除以3或9；如果x9,那么余数为x-9; 如x=0,那么余数为0，能整除；如果x9,那么余数为x。67、11、131001三位一截奇偶位求差判别法从右往左三位一截并编号，编号为奇数的为奇数段，编号为偶数的为偶数段，看奇数段的数字的和及偶数段的数字的和的两者之差是否能被7、11、13整除； 如，86372548，奇数段的和为548+86，偶数段的和为372，求两者差看能否被7整除，同样，不够减前面加1个或多个7，直到够减；711、99两位一截求和再截判别法两位一截，将截取的段位数相加再截取

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

9、的数能否被11整除。如：9876543223456768，除以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+12+0+9+7+5+3+1=115偶数位数字和：3+210+110+8+6+4+2=53115-53=62；6211，余7；【例】求被13除余数是多少？ 解：注意13|111111，即每连续6 个1 是13 的倍数，且2021 除以6 余2，所以答案为11.20212021，那么这个数除以9余数是1.无敌乱切，按1/2/3/4到2021的等差数列

10、求和，看除以9的余数；2.3.3同余定理 定义: 用给定的正整数m分别除整数a、b，如果所得的余数相等，那么称a、b关于模m同余或a同余于b模m，记作ab(mod m)，如 560 mod 8，式子称为同余式，m称为该同余式的模。充要条件：整数a,b对模m同余的充要条件是 a-b能被m整除即m|a-b；或 ab(mod m)的充要条件是a=mt+bt为整数。2.3.2.2根本定理同余关系具有自身性、对称性及传递性，即1自身性：aa (mod m);2对称性：假设ab (mod m), 那么ba (mod m);3传递性：假设ab (mod m), bc (mod m)，那么ac (mod m)

11、.2.3.2.3重要定理：一个同余式的加减乘及幂的运算定理1 假设ab(mod m),n为自然数，那么anbn (mod m)；即a、b关于关于模m同余，那么a、b的同倍数也关于模m同余；定理2假设cacb(mod m), (c,m)=d最大公约数, 且a,b为整数，那么ab(mod m/d).推论假设ca=cb(mod m), (c,m)=1,且a,b为整数，那么ab(mod m).定理3假设ab (mod m),ab (mod n),那么ab(mod m,n).推论假设ab(mod mi), i=1,2,n，那么ab (mod m1,m2,.,mn).【例】将1996加上一个整数，使和能被

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

13、的情况：ab=c.d0db； b=(a-d) c;或c=(a-d) b如果，只知a和d,求b或c【例】1111 某2位数=.66 余数不确定余数的和【例1】63=m+a 90=m+b130=m+c,余数和为25；63+90+130=m+a+b+c=m+2563+90+130-25=m258=m258的约数有8个：1/2582/1293/866/43因为余数要小于除数，判断9m63；所以m=43 余数不确定余数一样【例2】300=m商+a 262=m+a205=m+a,根据同余定理：m300-262= m38；m262-205= m57；m300-205= m95；满足两个即可，选数小的算，求同

14、时满足能整除38和57，即求这两个数的公约数，分别有1和19，答案为19。 余数不确定余数的差【例3】97=m商+a+3 29=m+a变为94=m+a,根据同余定理：m94-29= m65；65的约数有1/65,5/13，除数大于余数，排除1和65,5和13都满足； 余数不确定余数的倍数【例4】61=m商+2a 90=m+a变为180=m+2a,根据同余定理：m180-61= m119；119的约数有1/119,7/17，除数大于余数，排除1和119,仅17满足； 2.3.5幂和连乘积的余数余数的周期性 周期性的用法：可用以求某个数的假设干次方的个位数：【例】32015的个位数：3的假设干次方

15、的个位数，依次枚举，找出循环规律，4个一个周期，2021 除以4，余几为周期内第几个。幂的余数的求法：先求底数的余数，再算底数的幂的余数的周期性，再根据指数相应的周期来确定最终的余数；【例】2015100除以7的余数：201510061001mod76,36,196,1176除以7的余数分别为6,1,6,1，2个为1周期，1002=50余0，故余数为1。特殊情况： 【例】32014除以8的余数：32014910071mod89除8的余数为1，所以无论指数多少，余数皆为1。【例】31625除以9的余数：【例】14389除以7的余数：【例】33335555+55553333除以7的余数： 作业5，

16、2的3次方以上模8的余数皆为02.3.6中国剩余定理物不知数 韩信点兵【题目】今物知其数三三数剩二数除三余数二意思,五五数剩三,七七数剩二,问物几何韩信点兵算所谓剩余定理【解法】三人同行七十稀；把除以3所得的余数用70乘五树梅花廿一枝；把除以5所得的余数用21乘；七子团圆正半月；把除以7所得的余数用15乘除百零五便得知；把上述三个积加起来,除以105的余数即为得数；270+321+215=233 233105=223；得数为23。2.2物不知数：余数问题的通解：根本的枚举法 从除数大的开场枚举； 先找同时满足两个除数的最小符合数，再加这俩除数的最小公倍数，直到满足所有除数的最小的符合数； 再加

17、所有除数的最小公倍数n，直到符合题意；【例】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。 在所有除数的最小公倍数内一定能找到最小的满足数； 多个符合数必然是一个以所有除数的最小公倍数为等差的等差数列2.3物不知数：余数问题的通解：特殊情况 余数一样的最小符合数就是余数，其他的为除数的

18、最小公倍数的倍数+余数即最小符合数+除数的最小公倍数的倍数；【例】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，问到底多少根火柴棍？10余9，9余8，8余7，7余6，6余5：

19、【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个；求开场有多少个苹果？【10,9,6,5,3】-1=89 和一样余数都不一样的，但除数及余数的和一样的，可以转化为同余的，最小符合数就为最小的除数+余数；其他的符合数为除数的最小公倍数的倍数+和也即最小符合数+除数的最小公倍数的倍数；【例】5余4,7余2,6余3：最小符合数为5+4=9；【注意】多个除数的时候一定先看有无特殊情况；先利用局部特殊

20、规律的，再找一般的；【例】3余2,5余4,7余1，【例】3余1,5余2,7余2,11余3；先找同余，2+35,37+已满足的3个的最小公倍数；2.4物不知数：可以用来解决除以12和6的余数的算法：互质分解求A=123456319被12/14/15/45/99除的余数；将12互质分解=43,求同时满足除以4和除以3的；A 3mod4;A (1+2+3+.+319)(1+319) 3192160 31911mod34余3,3余1，最小符合数为7，其他符合数为7+12n所以A 7mod12;【注意】 常见的互质分解有：12=43,14=27,15=35,45=59，99=911；105=357，其中

21、105的频率最高； 【例】5余4,97余1； 1,98,195，得389； 99有两种算法，两位截断法和互质分解；求A=123123123被99除的余数； 123个123互质分解法：将99互质分解=911,求同时满足除以9和除以11的；A 123123660mod9;A (62123)- (61123)1232mod119余0,11余2，最小符合数为90，其他符合数为90+99n所以A 90mod99;两位截断法：A (23+31+12)61+ (123)6661+244026+2466+2490mod99 求A=202120212021被495除的余数； 100个2021互质分解法：将495

22、互质分解=957,求同时满足除以9余0，除以5余1，除以11余9的物不知数，即为余数；2.4物不知数：非典型物不知数题目转为物不知数题目 【例1】三个非0的连续自然数，分别是3、5、7的倍数，找出符合要求的最小的一组自然数；设n,n+1,n+2分别能被3、5、7整除，那么n3余0，n+15余0，n+27余0， 3余0，5余4，7余51954答案为54、55、56【例2】三个非0的连续自然数，分别是7、9、11的倍数，找出符合要求的最小的一组自然数；设n,n+1,n+2分别能被7、9、11整除，那么n7余0，n+19余0，n+211余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:4x+3(x+1)=a=7x+3;所以，3m+1=5n+2，m=5n+13除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，再往回算为237；及辗转相除法类似；第 11 页