模二除法
我的姐姐们-有益的动物
2023年2月21日发(作者：大战拖延症)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,b能整除c，
且ab互质，则ab的积能整除c;
⑤a个连续自然数中必恰有一个数能被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或625：末4位数是16（或625）的倍数
数字和判别法（用以判别能否被3或9整除）
各数位上数字的和是3或9的倍数，则能被3或9整除。
173652÷9:1+7+3+6+5+2的和除以3或9；
简便算法，利用整除的加减性，可以去掉1个或多个9，剩下数字的和x再
除以3或9；如果x﹥9,则余数为x-9;如果x﹤9,则余数为x。
奇偶数位判别法（用以判别能否被11整除）
从右往左编号，编号为奇数的为奇数位，编号为偶数的为偶数位，看奇数位
上的数字的和与偶数位上的数字的和的两者之差是否能被11整除；
÷11:奇数位和为6，偶数位和为27；如果奇数位和比偶数位和小，则奇数
位和加1个或多个11，直到够减。余数的判断法与整数位的判断法一致。
三位一截判别法（用以判别能否被7/11/13整除）
基本用法
从右往左三位一截并编号，编号为奇数的为奇数段，编号为偶数的为偶数段，
看奇数段的数字的和与偶数段的数字的和的两者之差是否能被7、11、13整除；
如，，奇数段的和为（548+86），偶数段的和为372，求两者差看能否被7整
除，同样，不够减前面加1个或多个7，直到够减，余数位的判断法与整数位的
判断法一致。
特殊用法
①一般求空格数
如果中间有空格，则利用加减性加或减除数7的倍数，分别从右边和左边抵
消缩减位数，到最后看7的哪个倍数与缩减后的末位数相同，并看7的哪个倍数
与缩减后的首位数相同，则前一个倍数的十位数和后一个倍数的个位数的和即为
空格中应填的数。注意，如果这个数加或减7后为1到9间的自然数，则加或减
7后的这个数也为正确答案。
395864□82365，答案为5
463925□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整除的空格数
有关9系列截判法（用以判别能否被9/99/999整除）
除数是几位数就可以从右往左几位一截，将截取的段位数相加再截取，直至
不能再截取，看相应的数能否被相应的除数9/99/999整除。
除数是11时，也可以用两位一截判别法，因为根据整数的因数性，能被99
整除的数，肯定能被11整除。
例如：
余数的判别法
余数的定义和性质
①整除是余数为0的情况。a÷b=c…..0；
此时，a=b×c;b=a÷c
②有余数的情况：a÷b=c…..d（0﹤d﹤b）；
此时，a=b×c+d;b=(a-d)÷c;c=(a-d)÷b
记着：a≡d(modb)
余数的判别法（与整除相同）
【注意】：当被除数是比除数小的非零自然数，则被除数为余数；当被除数比余数大，则减
去除数的倍数所得比除数小的数即为余数。
序号除数余数判别法特别要点
1
2和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
3或9
数字和法；
弃3（9）法；
各数位上数字的和是3或9的倍数，则能被3或9整除。
利用整除的加减性，可以去掉1个或多个9（包括几个数
的和是3或9的倍数的也可划掉），剩下数字的和x再除
以3或9；如果x﹥9,则余数为x-9;如x=0,则余数为0，
能整除；如果x﹤9,则余数为x。
6
7、11、13
（1001）
三位一截奇偶
位求差判别法
从右往左三位一截并编号，编号为奇数的为奇数段，编号
为偶数的为偶数段，看奇数段的数字的和与偶数段的数字
的和的两者之差是否能被7、11、13整除；
如，，奇数段的和为（548+86），偶数段的和为372，求两
者差看能否被7整除，同样，不够减前面加1个或多个7，
直到够减；
7
11、99
两位一截求和
再截判别法
两位一截，将截取的段位数相加再截取，直至不能再截取，
看能否被11或99整除，注意，根据整数的因数性，能被
99整除的数，肯定能被11整除。
8
11
奇偶数字和求
差判别法
从右往左编号，编号为奇数的为奇数位，编号为偶数的为
偶数位，看奇数位上的数字的和与偶数位上的数字的和的
两者之差是否能被11整除；÷11:奇数位和为6，偶数
位和为27；如果奇数位和比偶数位和小，则奇数位和加1
个或多个11，直到够减。11可以无敌乱切，但还是常用
奇偶位截断求差法；
9
999
三位一截求和
再截法
从右往左三位一截，将截取的段位数相加再截取，直至不
能再截取，看相应的数能否被999整除。
10
11
四位一截求和
法
从右往左四位一截，将截取的段位数相加，看相应的数能
否被11整除。
如：，除以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+2×10+1×10+8+6+4+2=53
115-53=62；62÷11，余7；
【例】求被13除余数是多少
解：注意13|111111，即每连续6个1是13的倍数，且2012除以6余2，所
以答案为11．
【例】把自然数1到2011这2011个数依次写下来，得到一个很大的多位数：
12….，则这个数除以9余数是1.
无敌乱切，按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为整数）。
基本定理
同余关系具有自身性、对称性与传递性，即
1）自身性：a≡a(modm);
2）对称性：若a≡b(modm),则b≡a(modm);
3）传递性：若a≡b(modm),b≡c(modm)，则a≡c(modm).
重要定理：一个同余式的加减乘及幂的运算
定理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(modm),a≡b(modn),则a≡b(mod[m,n]).
推论若a≡b(modmi),i=1,2,…,n，则a≡b(mod[m1,m2,..,mn]).
【例】将1996加上一个整数，使和能被9和11整除，加的整数尽可能小，
那么加的整数是多少
1996≡16(mod99)；99-16=83
定理4若a≡b(modm),则an≡bn(modm),其中n是自然数。
同余定理的重要推论：两个同模同余式的加减乘运算
若a≡b(modm),c≡d(modm),则可以将这两个同余式左右两边分别相加、
相减或相乘：
1）a+c≡b+d(modm);即和的余数等于余数的和
2）a-c≡b-d(modm);即差的余数等于余数的差；
3）ac≡bd(modm)；即积的余数等于余数的积；
【例】316×419×813除以13所得的余数
只知被除数和余数，求除数或求商
余数确定（注意余数比除数小）
有余数的情况：a÷b=c…..d（0﹤d﹤b）；
b=(a-d)÷c;或c=(a-d)÷b
如果，只知a和d,求b或c
【例】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
因为余数要小于除数，判断9﹤m﹤63；所以m=43
②余数不确定——余数相同
【例2】300=m×（商）+a
262=m×（）+a
205=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+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×（）+2a,
根据同余定理：
m∣（180-61）=m∣（119）；
119的约数有1/119,7/17，除数大于余数，排除1和119,仅17满
足；
幂和连乘积的余数——余数的周期性
周期性的用法：可用以求某个数的若干次方的个位数：
【例】的个位数：
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
中国剩余定理——物不知数（韩信点兵）
传统题目和传统解法
【题目】今物知其数三三数剩二（数除三余数二意思）,五五数剩三,七七数
剩二,问物几何（韩信点兵算所谓剩余定理）
【解法】
三人同行七十稀；把除以3所得的余数用70乘
五树梅花廿一枝；把除以5所得的余数用21乘；
七子团圆正半月；把除以7所得的余数用15乘
除百零五便得知；把上述三个积加起来,除以105的余数即为得数；
2×70+3×21+2×15=233233÷105=2…23；得数为23。
物不知数：余数问题的通解：基本的枚举法
①从除数大的开始枚举；
②先找同时满足两个除数的最小符合数，再加这俩除数的最小公倍数，直
到满足所有除数的最小的符合数；
③再加所有除数的最小公倍数×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，连续两个自然数的最小
公倍数为其积；48×49能整除14，余数是0,23除14的余数，全是9。
③在所有除数的最小公倍数内一定能找到最小的满足数；
④多个符合数必然是一个以所有除数的最小公倍数为等差的等差数列
物不知数：余数问题的通解：特殊情况
①余数相同的——最小符合数就是余数，其他的为除数的最小公倍数的倍
数+余数（即最小符合数+除数的最小公倍数的倍数）；
【例】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：
【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
③和相同——余数都不相同的，但除数与余数的和相同的，可以转化为同
余的，最小符合数就为最小的除数+余数；其他的符合数为除数的最小
公倍数的倍数+和（也即最小符合数+除数的最小公倍数的倍数）；
【例】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个
的最小公倍数；
物不知数：可以用来解决除以12和6的余数的算法：互质分解
求A=123456……319被12/14/15/45/99除的余数；
将12互质分解=4×3,求同时满足除以4和除以3的；
A≡3（mod4）;
A≡(1+2+3+….+319)
≡(1+319)×319÷2
≡160×319
≡1×1（mod3）
4余3,3余1，最小符合数为7，其他符合数为7+12×n
所以A≡7（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的；
A≡123×123
≡6×6
≡0（mod9）;
A≡(62×123)-(61×123)
≡123
≡2（mod11）
9余0,11余2，最小符合数为90，其他符合数为90+99×n
所以A≡90（mod99）;
两位截断法：
A≡(23+31+12)×61+(1×23)
≡66×61+24
≡4026+24
≡66+24
≡90（mod99）
③求A=……2016被495除的余数
100个2016
互质分解法：将495互质分解=9×5×7,求同时满足除以9余0，除以5余1，
除以11余9的物不知数，即为余数；
物不知数：非典型物不知数题目转为物不知数题目
【例1】三个非0的连续自然数，分别是3、5、7的倍数，找出符合要求的
最小的一组自然数；
设n,n+1,n+2分别能被3、5、7整除，则
n÷3余0，（n+1）÷5余0，（n+2）÷7余0，
3余0，5余4，7余5
19
54
答案为54、55、56
【例2】三个非0的连续自然数，分别是7、9、11的倍数，找出符合要求
的最小的一组自然数；
设n,n+1,n+2分别能被7、9、11整除，则
n÷7余0，（n+1）÷9余0，（n+2）÷11余0
7余0，9余8，11余9
53
350
答案为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=
除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；与辗转相除法类似；