《小奥数论1-整除和余数知识点总结归纳及经典例题》由会员分享，可在线阅读，更多相关《小奥数论1-整除和余数知识点总结归纳及经典例题（16页珍藏版）》请在金锄头文库上搜索。
1、1 / 16 1.数论数的整除和余数2.1 基本概念和基本性质整数a除以整数 b（ b 0），除得的商是整数而没有余数，我们就说 a能被b整除，或者说 b能整除 a。b a，读着 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 互质，则
2、ab的积能整除 c; a个连续自然数中必恰有一个数能被a整除。2.2 数的整除的判别法整除数特征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 ）的倍数2 / 16 8 和 125 好朋友 1000 ， 3 个零，所以判断末3 位；8 或 125 ：末 3 位数是 8（或 125 ）的倍数16 和 625 好朋友 10000 ，4 个零，所以判断末4 位；16 或 625 ：末 4 位
3、数是 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，直到够减。余数的判断法与整数位的判断法一致。2.2.4 三位一截判别法
4、（用以判别能否被7/11/13整除）从右往左三位一截并编号，编号为奇数的为奇数段，编号为偶数的为偶数段，看奇数段的数字的和与偶数段的数字的和的两者之差是否能被7、11 、13整除；两者差看能否被7 整除，同样，不够减前面加1 个或多个 7，直到够减，余数位的判断法与整数位的判断法一致。 一般求空格数如果中间有空格，则利用加减性加或减除数7 的倍数，分别从右边和左边抵消缩减位数，到最后看7 的哪个倍数与缩减后的末位数相同，并看7 的哪个3 / 16 倍数与缩减后的首位数相同，则前一个倍数的十位数和后一个倍数的个位数的和即为空格中应填的数。注意，如果这个数加或减7 后为 1 到 9 间的自然数，则
5、加或减 7 后的这个数也为正确答案。395864 82365 ，答案为 5 463925 01234 ，答案为 1 和 8 特殊求空格数根据整除的因数性，如果1 个数能被 1001 整除，则这个数能被7、11、13、77、91、143 整除，因为：711 13=1001; 77 13=1001; 99 11=1001; 7143=1001; 根据= 1001;= 1001; 求能被 7 整除的空格数系列截判法（用以判别能否被9/99/999整除）除数是几位数就可以从右往左几位一截，将截取的段位数相加再截取，直至不能再截取，看相应的数能否被相应的除数9/99/999整除。除数是 11 时，也可以
6、用两位一截判别法，因为根据整数的因数性，能被99 整除的数，肯定能被11 整除。例如：4 / 16 2.3 余数的判别法 整除是余数为 0 的情况。 a b=c .0；此时， a= b c;b= a c 有余数的情况： a b=c .d（0db） ；此时， a=b c+d;b=(a-d) c; c=(a-d) b 记着： a d(modb) 2.3.2 余数的判别法（与整除相同）【注意】：当被除数是比除数小的非零自然数，则被除数为余数；当被除数比余数大，则减去除数的倍数所得比除数小的数即为余数。序号除数余数判别法特别要点1 2 和 5 末 1 位判断法；看末 1 位能否被2 整除；尾是0、2、
7、4、 6、8 能；看末 1 位能被 5 整除；尾是0、5 能；2 4 和 25 末 2 位判断法末 2 位数是 4（或 25 ）的倍数即能被4 或 25 整除3 8 和 125 末 3 位判断法；末 3 位数是 8（或 125 ）的倍数4 16 和 625 末 4 位判断法；末 4 位数是 16 （或 625 ）的倍数5 3 或 9 数字和法；弃 3（9）法；各数位上数字的和是3 或 9 的倍数，则能被 3 或 9 整除。利用整除的加减性，可以去掉1 个或多个9（包括几个数的和是 3 或 9 的倍数的也可划掉） ，剩下数字的和x 再除以 3 或 9； 如果 x9,则余数为x-9; 如 x=0,
8、 则余数为 0，能整除；如果x 9,则余数为 x。5 / 16 6 7、11 、13 （ 1001 ）三位一截奇偶位求差判别法从右往左三位一截并编号，编号为奇数的为奇数段，编号为偶数的为偶数段， 看奇数段的数字的和与偶数段的数字的和的两者之差是否能被7、11 、13 整除；两者差看能否被7 整除，同样，不够减前面加1 个或多个 7，直到够减；7 11 、 99 两位一截求和再截判别法两位一截，将截取的段位数相加再截取，直至不能再截取，看能否被 11 或 99 整除，注意，根据整数的因数性，能被 99 整除的数，肯定能被11 整除。8 11 奇偶数字和求差判别法从右往左编号， 编号为奇数的为奇数
9、位，编号为偶数的为偶数位，看奇数位上的数字的和与偶数位奇数位和为6，偶数位和为27 ；如果奇数位和比偶数位和小，则奇数位和加 1 个或多个11 ，直到够减。 11 可以无敌乱切， 但还是常用奇偶位截断求差法；9 999 三位一截求和再截法从右往左三位一截，将截取的段位数相加再截取，直至不能再截取，看相应的数能否被999 整除。10 11 四位一截求和法从右往左四位一截，将截取的段位数相加，看相应的数能否被 11 整除。为 0,3,0,8,0,18 【例】将 1，2,3,4，30 从左往右依次排列成一个51 位数，这个数被 11 除的余数是多少？奇数位数字和：（0+9+8+1 ）2+0+9+7+
10、5+3+1=115 偶数位数字和： 3+2 10+1 10+8+6+4+2=53 6 / 16 115-53=62；62 11，余 7；【例】求被 13 除余数是多少？解：注意 13|111111 ，即每连续 6 个 1 是 13 的倍数，且 2012 除以 6 余 2，所以答案为 11无敌乱切，按 1/2/3/4到 2011 的等差数列求和，看除以9 的余数；定义: 用给定的正整数 m 分别除整数 a、b，如果所得的余数相等， 则称 a、b 关于模 m 同余或 a 同余于 b 模 m，记作 a b(mod m)，如 56 0 （mod 8 ） ，式子称为同余式， m 称为该同余式的模。充要条
11、件：整数 a,b 对模 m 同余的充要条件是a-b 能被 m 整除 （即 m|a-b ） ；或 a b(mod m)的充要条件是 a=mt+b（t 为整数） 。2.3.2.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).2.3.2.3 重要定理：一个同余式的加减乘及幂的运算定理 1 若 a b(mod m),n 为自然数，则 an bn ( mod m) ；即 a、b 关于关于模 m 同余，则 a
12、、b 的同倍数也关于模 m 同余；定理 2?若 ca cb(mod m), (c,m)=d（最大公约数） , 且 a,b 为整数，则7 / 16 a b(mod m/d).推论若 ca=cb(mod m), (c,m)=1,且 a,b 为整数，则 a b(mod m).定理 3?若 a b (mod m),a b (mod n),则a b(mod m,n).推论若 a b(mod mi), i=1,2, ,n ，则a b (mod m1,m2,.,mn).【例】将 1996 加上一个整数， 使和能被 9 和 11 整除，加的整数尽可能小，那么加的整数是多少？1996 16(mod 99) ；9
13、9-16=83 定理 4 若 a b (mod m),则anbn(modm), 其中 n 是自然数。两个同模同余式的加减乘运算若 a b(mod m), c d (mod m),则可以将这两个同余式左右两边分别相加、相减或相乘：1） a+c b+d (mod m);即和的余数等于余数的和2）a-cb -d (mod m);即差的余数等于余数的差；3） ac bd (mod m) ；即积的余数等于余数的积；【例】 316419 813 除以 13 所得的余数2.3.4 只知被除数和余数，求除数或求商（注意余数比除数小）有余数的情况： a b=c .d（0db） ；b=(a-d) c;或 c=(a
14、-d) b 如果，只知 a 和 d,求 b 或 c 8 / 16 【例】 1111 某2 位数=（）.66 余数不确定余数的和【例 1】63=m （）+a 90=m （）+b 130=m （）+c, 余数和为 25；（63+90+130）=m （）+（a+b+c ）=m （）+25 （63+90+130-25）=m （）258=m （）258 的约数有 8 个：1/258 2/129 3/86 6/43 因为余数要小于除数，判断9m 63；所以 m=43 余数不确定余数相同【例 2】300=m （商）+a 262=m （）+a 205=m （）+a, 根据同余定理：m （ 300-262 ）=
15、 m （ 38） ；m （ 262-205 ）= m （ 57） ；m （ 300-205 ）= m （ 95） ；9 / 16 满足两个即可，选数小的算，求同时满足能整除38 和 57 ，即求这两个数的公约数，分别有1 和 19，答案为 19 。 余数不确定余数的差【例 3】97=m （商）+a+3 29=m （）+a 变为 94=m （）+a, 根据同余定理：m （ 94-29 ）= m （ 65） ；65 的约数有 1/65,5/13 ，除数大于余数，排除1 和 65,5 和 13 都满足； 余数不确定余数的倍数【例 4】61=m （商）+2a 90=m （）+a 变为 180=m （）
16、+2a, 根据同余定理：m （ 180-61 ）= m （ 119 ） ；119 的约数有 1/119,7/17，除数大于余数，排除1 和 119,仅 17满足；2.3.5 幂和连乘积的余数余数的周期性周期性的用法：可用以求某个数的若干次方的个位数：【例】的个位数：10 / 16 3 的若干次方的个位数，依次枚举，找出循环规律，4 个一个周期， 2015除以 4，余几为周期内第几个。幂的余数的求法： 先求底数的余数，再算底数的幂的余数的周期性，再根据指数相应的周期来确定最终的余数；【例】除以 7 的余数： 1（mod7）6,36,196,1176 除以 7 的余数分别为 6,1,6,1 ，2 个为 1 周期，100 2=50余 0，故余数为 1。特殊情况： 【例】除以 8 的余数： 1（mod8）9 除 8 的余数为 1，所以无论指数多少，余数皆为1。【例】除以 9 的余数：【例】除以 7 的余数：【例】+除以 7 的余数： 作业 5，2 的 3 次方以上模 8 的余数皆为 0 2.3.6 中国剩余定理物不知数（韩信点兵）【题目】今物知其数三三数剩二（数除三余数二意思）,五五数剩三 ,
