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

1、1.数论一一数的整除和余数2.1 基本概念和基本性质整数a除以整数b (bw0),除得的商是整数而没有余数，我们就说a能被b整除，或者说b能整除a。b la,读着b能整除a;或a能被b整除；b* a,不能整除； 传递性：如果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;I '/ " 互质性，如果a|c, b|c ,且(a,b) =1,那么ab|c,即如果a能整除c,b能整除c,且ab互质，则a

2、b的积能整除c;a个连续自然数中必恰有一个数能被a整除。'| |2.2 数的整除的判别法整除数特 征2和5好朋友10 ,1个零，所以判断末1位；2:末1位能被2整除；尾是0、2、4、6、8;1_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 ）的倍数各数位上数字的和是3或9的倍数，则能被3或9

3、整除。173652 M:1+7+3+6+5+2的和除以 3 或 9;简便算法，利用整除的加减性，可以去掉 1个或多个9,剩下数字的和x再除以3或9;如果 x>9,则余数为x-9;如果x< 9,则余数为x。从右往左编号，编号为奇数的为奇数位，编号为偶数的为偶数位，看奇数位上的数字的和与偶数位上的数字的和的两者之差是否能被 11整除；奇数位和为6,偶数位和为27;如果奇数位和比偶数位和小，则奇数位和加 1个或多个11, 直到够减。余数的判断法与整数位的判断法一致。2.2.4三位一截判别法（用以判别能否被7/11/13 整除）丁 ¥ / /I2.3 1 r %从右往左三位一截并

4、编号，编号为奇数的为奇数段，编号为偶数的为偶数段，看奇数段的数字的和与偶数段的数字的和的两者之差是否能被 7、11、13整除；两者差看能否被7整除，同样，不够减前面加1个或多个7,直到够减，余数位的判断法与整 数位的判断法一致。一般求空格数 -f . |X、/、尸 产/如果中间有空格，则利用加减性加或减除数7的倍数，分别从右边和左边抵消缩减位数，至U最后看7的哪个倍数与缩减后的末位数相同，并看 7的哪个倍数与缩减后的首位数相同，则前一 个倍数的十位数和后一个倍数的个位数的和即为空格中应填的数。注意，如果这个数加或减7后为1到9间的自然数，则加或减7后的这个数也为正确答案。395864 0823

5、65 ,答案为 5463925 C01234 ,答案为 1 和 8特殊求空格数根据整除的因数性，如果1个数能被1001整除，则这个数能被7、11、13、77、91、143整除，因为：7X11 X13=1001;77X13=1001;99X11=1001;7X143=1001;根据二Nx1001;益京二静"X1001;求能被7整除的空格数系列截判法(用以判别能否被9/99/999 整除)除数是几位数就可以从右往左几位一截，将截取的段位数相加再截取，直至不能再截取，看相应的数能否被相应的除数9/99/999整除。产厂211 二J 二丁除数是11时，也可以用两位一截判别法，因为根据整数的因

6、数性，能被 99整除的数，肯定能被11整除。例如：2.3余数的判别法1 .- ： ：-； ,； 整除是余数为0的情况。a+b=c一。；-f. : IX 式产 产 /止匕时，a= b xc;b= a +c 有余数的情况：ab=c - -.d (0<d<b);止匕时，a=b xc+d;b=(a-d)-c; c=(a-d)也记着：aW(modb)2.3.2余数的判别法(与整除相同)【注意】：当被除数是比除数小的非零自然数，则被除数为余数；当被除数比余数大，则减去除数的倍数所得比 除数小的数即为余数。序号除数余数判别法特别要点12和5末1位判断法；看末1位能否被2整除；尾是0、2、4、6、

7、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数字和法；弃3 （9）法；各数位上数字的和是 3或9的倍数，则能被3或9整除。利用整除的加减性， 可以去掉1个或多个9 （包括几个数 的和是3或9的倍数的也可划掉），剩下数字的和x再除 以3或9 ;如果x > 9,则余数为x-9;如x=0,则余数为0 , 能整除；如果x<9,则余数为x。67、 11、 13(1001 ) ; 1 .三

8、位一截奇偶位求差判别法从右往左三位一截并编号， 编号为奇数的为奇数段， 编号为偶数的为偶数段，看奇数段的数字的和与偶数段的数字的和的懈TN差是否能被 7、11、13整除；两者差看能否被 7整除，同样，不够减前囿加 1个或多个7,直到够减；711、99两位一戚求和再截判别法两位一截，将截取的段位数相加再截取， 直至不能再截取，看能否被11或99整除，注意，根据整数的因数性，能被99整除的数，肯定能被 11整除。811奇偶数字和求差判别法从右往左编号，编号为奇数的为奇数位，编号为偶数的为偶数位，看奇数位上的数字的和与偶数位奇数位和为6,偶数位和为27 ;如果奇数位和比偶数位和小，则奇数位和加1个或

9、多个11 ,直到够减。11可以无敌乱切，但还是常用奇偶位截断求差法；9999二位一截求和再截法从右往左三位一截， 将截取的段位数相加再截取，直至不能再截取，看相应的数能否被999整除。1011四位一戚求和法从右往左四位一截， 将截取的段位数相加， 看相应的数能否被11整除。为 0,3,0,8,0,18【例】将1, 2,3,4,30从左往右依次排列成一个51位数，这个数被11除的余数是多少？奇数位数字和：(0+9+8+ -+1 ) X2+0+9+7+5+3+1=115偶数位数字和：3+2 X10+1 X10+8+6+4+2=53115-53=62 ; 62-11,余 7;. Ii -I<

10、r 小in.11【例】求4 被13除余数是多少？解：注意13|111111 ,即每连续6个1是13的倍数，且2012除以6余2,所以答案为11.无敌乱切，按1/2/3/4至U2011的等差数列求和，看除以9的余数；定义：用给定的正整数m分别除整数a、b,如果所得的余数相等，则称a、b关于模m同余<| I 或a同余于b模m ,记作amb(mod m),表56 = 0 (mod 8 ),式子称为同余式，m称为该同余 式的模。充要条件：整数a,b对模m同余的充要条件是 a-b能被m整除(即m|a-b );或amb(mod m)的充要条件是a=mt+b (t为整数)。2.3.2.2基本定理同余关

11、系具有自身性、对称性与传递性，即1)自身性:a m a (mod m);2)对称性：若amb (mod m),则bma (mod m);3) 传递性： 若 am b (mod m), b = c (mod m)a=,c 贝mod m).2.3.2.3重要定理：一个同余式的加减乘及哥的运算定理1若amb(mod m),n为自然数，则an = bn (nod m);即a、b关于关于模 m同余，则 a、b的同倍数也关于模 m同余；定理 2?若 ca = cb(mod m), (c,m)=d(最大公约80) a,b 为整数，则 a m b(mod m/d).推论若 ca=cb(mod m), (c,m

12、)=1, 且 a,b 为整数，则 a三 b(mod m).定理 3?若 a= b (mod m),a= b (mod na= b(mod m,n).推论若 am b(mod mi), i=1,2,- a=n b (mod m1,m2,.,mn).产厂211 二J _二,【例】将1996加上一个整数，使和能被9和11整除，加的整数尽可能小，那么加的整数是 'r 1< .多少？1996 m6(mod 99) ; 99-16=83"'.:定理4若amb (mod m), an拿巾(modm),其中n是自然数。i 两个同模同余式的加减乘运算若amb(mod m), c

13、md (mod m),则可以将这两个同余式左右两边分别相加、相减或相乘:1) a+c = b+d (mod m);即和的余数等于余数的和2) a-c = -d (mod m);即差的余数等于余数的差；3) ac = bdmod m)；即积的余数等于余数的积；【例】316 X419 X813除以13所得的余数2.3.4只知被除数和余数，求除数或求商(注意余数比除数小)有余数的情况：ab=c .d (0 < d < b);b=(a-d) +c;或 c=(a-d) +b如果，只知a和d,求b或c【例】1111 +某2位数=().66余数不确定余数的和例 1 63=m x () +a90=

14、m x () +b<厂 " i: 一一，二130=m x () +c,余数和为 25;(63+90+130 ) =m X () + (a+b+c ) =m x () +25(63+90+130-25 ) =m x ()258=m x ()258的约数有8个：I 占二1/2582/1293/866/43因为余数要小于除数，判断 9 < m < 63 ;所以m=43余数不确定余数相同例 2 300=m X (商)+a262=m x () +a 205=m x () +a, 根据同余定理：mI300-262)= mI38);mI262-205)= mI57);mI300-

15、205)= mI95);满足两个即可，选数小的算，求同时满足能整除38和57,即求这两个数的公约数, 分别有1和19 ,答案为19。余数不确定余数的差例 3 97=m X (商)+a+329=m x () +a变为 94=m x () +a,产r It 二一 二一7根据同余定理：i 1m I 94-29 ) = m I 65);65的约数有1/65,5/13 ,除数大于余数，排除1和65,5和13都满足；余数不确定余数的倍数【例4】61=m X (冏)+2a(，二 X 二"尸90=m x () +aI /.x X /变为 180=m X () +2a,根据同余定理：m I 180-6

16、1 ) = m I 119);119的约数有1/119,7/17 ,除数大于余数，排除1和119，仅17满足；2.3.5 余和连乘积的余数一一余数的周期性周期性的用法：可用以求某个数的若干次方的个位数：【例】乎""的个位数：3的若干次方的个位数，依次枚举，找出循环规律，4个一个周期，2015除以4,余几为周期内第几个。幕的余数的求法：先求底数的余数，再算底数的幕的余数的周期性，再根据指数相应的周期来 确定最终的余数；【例】2015以。除以7的余数：201510t（mod7）6,36,196,1176除以7的余数分别为6,1,6,1 , 2个为1周期，100 +2=50余0,

17、故余数为1。特殊情况：【例】乎4除以8的余数：q2014_qL007. / .o xm （mod8）9除8的余数为1 ,所以无论指数多少，余数皆为1。 1x.j-【例】316质除以9的余数：【例】143里卜除以7的余数:一. 二【例】3333宗.+5555m3除以7的余数：作业5, 2的3次方以上模8的余数皆为0 （，二 X 二"尸2.3.6 中国剩余定理一一物不知数（韩信点兵）【题目】今物知其数三三数剩二（数除三余数二意思），五五数剩三，七七数剩二，问物几何（韩信点兵算所谓剩余定理）【解法】三人同行七十稀；把除以3所得的余数用70乘五树梅花廿一枝；把除以5所得的余数用21乘；七子团

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

19、忽略商为0的情况；【例】某除48余23 ,除49余23 ;某最小的答案就是23 ;【例】例3: 49余23,48余23 ;最小符合数为23,连续两个自然数的最小公倍数为其积；48 X49能整除14,余数是0,23除14的余数，全是9。在所有除数的最小公倍数内一定能找到最小的满足数； -f . - I .X、产*尸产/多个符合数必然是一个以所有除数的最小公倍数为等差的等差数列2.3.6.3 物不知数：余数问题的通解：特殊情况 余数相同的一一最小符合数就是余数，其他的为除数的最小公倍数的倍数十余数（即最小符合数十除数的最小公倍数的倍数）；【例】5余4,7余4,9余4,最小的为4;【例】某除4、除5

20、、除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:15,6,7,8,9 -1= 11,2,3,4,5,6,7

21、,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 ; （，二 X 二"尸【注意】多个除数的时候一定先看有无特殊情况；先利用部分特殊规律

22、的，再找一般的； - I、，尸 / /【例】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 X3,求同时满足除以4和除以3的；A 三3 （mod4）;A V1+2+3+ .+319)31+319) X319+2空60 X319M X1 (mod3)4余3,3余1,最小符合数为7,其他符合数为7+12 Xn所以 A / (mod12);【注意】常见的互质分解有：12

23、=4X3,14=2 X7,15=3X5,45=5X9, 99=9X11; 105=3X5X7,其中105的频率最高；【例】5 余 4,97 余 1 ; 1,98,195 ,得 389 ;99有两种算法，两位截断法和互质分解； .,7一一、 I -'-I = 二'I求A=123123 123被99除的余数.123 个 123一一. 二互质分解法：将99互质分解=9 X11，求同时满足除以9和除以11的；A m23X123(，二 X 二"尸三6X6 - Ix、衣尸 “ /司(mod9);A 362 X123)-(61 X123)M23至(mod11 )9余0,11余2,最小符合数为90,其他符合数为90+99 Xn所以 A 国0 (mod99);两位截断法：A