小学奥数论:整除和余数知识点总结及经典例题
哥特式寂寞-歇后语大全及答案
1. 数论——数的整除和余数
2.1基本概念和基本性质
2.1.1定义
整数a除以整数b(b≠0),除得的商是整数而没有余数,我们就说a能被b整除,
或者说b
能整除a。
2.1.2表达式和读法
b∣a,读着b能整除a;或a能被b整除;b
a,不能整除;
2.1.3基本性质
①
传递性:如果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.2数的整除的判别法
2.2.1末位判别法
整除数 特
征
好朋友10,1个零,所以判断末1位;
2和5
2:末1位能被2整除;尾是0、2、4、6、8;
5:末1位能被5整除;尾是0、5;
好朋友100,2个零,所以判断末2位;
4和25
4或25:末2位数是4(或25)的倍数
好朋友1000,3个零,所以判断末3位;
8和125
8或125:末3位数是8(或125)的倍数
好朋友10000,4个零,所以判断末4位;
16和625
16或625:末4位数是16(或625)的倍数
2.2.2数字和判别法(用以判别能否被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。
2.2.3奇偶数位判别法(用以判别能否被11整除)
从右往左编号,编号
为奇数的为奇数位,编号为偶数的为偶数位,看奇数位
上的数字的和与偶数位上的数字的
和的两者之差是否能被11整除;
81729033÷11:奇数位和为6,偶数位和为27;如果
奇数位和比偶数位和小,
则奇数位和加1个或多个11,直到够减。余数的判断法与整数位的判断法一致
。
2.2.4三位一截判别法(用以判别能否被71113整除)
2.2.4.1基本用法
从右往左三位一截并编号,编号为奇数的为奇数段,编号为偶数的为
偶数段,
看奇数段的数字的和与偶数段的数字的和的两者之差是否能被7、11、13整除;
如,86372548,奇数段的和为(548+86),偶数段的和为372,求两者差
看能否被7
整除,同样,不够减前面加1个或多个7,直到够减,余数位的判断
法与整数位的判断法一致。
2.2.4.2特殊用法
① 一般求空格数
如果中间有空格,则利用加减性加或减
除数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整除的空格数
abcabcabcaaaaaaaaa
2.2.5有关9系列截判法(用以判别能否被999999整除)
除数是几位数就可以从右
往左几位一截,将截取的段位数相加再截取,直至
不能再截取,看相应的数能否被相应的除数99999
9整除。
除数是11时,也可以用两位一截判别法,因为根据整数的因数性,能被99
整除的
数,肯定能被11整除。
例如:
2.3余数的判别法
2.3.1余数的定义和性质
① 整除是余数为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)
2.3.2余数的判别法(与整除相同)
【注意】:当被除数是比除数小的非零自然数,则被除数为余数;当被除数比余数大,则减
去除
数的倍数所得比除数小的数即为余数。
序号
1
2和5
2
4和25 末2位判断法
看末1位能被5整除;尾是0、5能;
末2位数是4(或25)的倍数即能被4或25整除
除数 余数判别法 特别要点
末1位判断法; 看末1位能否被2整除;尾是0、2、4、6、8能;
3
4
5
8和125 末3位判断法; 末3位数是8(或125)的倍数
16和625 末4位判断法; 末4位数是16(或625)的倍数
数字和法;
各数位上数字的和是3或9的倍数,则能被3或9整除。
弃3(9)法;
利用整除的加减性,可以去掉1个或多个9(包括几个数
3或9
的和是3或9的倍数的也可划掉),剩下数字的和x再除
以3或9;如果x﹥9,则余数为x-9;
如x=0,则余数为0,
能整除;如果x﹤9,则余数为x。
6
三位一截奇偶
位求差判别法
7、11、13
(1001)
从右往左三位
一截并编号,编号为奇数的为奇数段,编号
为偶数的为偶数段,看奇数段的数字的和与偶数段的数字的和的两者之差是否能被7、11、13整除;
如,86372548,奇数段的和为(548
+86),偶数段的
和为372,求两者差看能否被7整除,同样,不够减前
面加1个或多个7
,直到够减;
7
11、99
两位一截求和
再截判别法
两位一
截,将截取的段位数相加再截取,直至不能再截取,
看能否被11或99整除,注意,根据整数的因数性
,能
被99整除的数,肯定能被11整除。
8 奇偶数字和求
差判别法
从
右往左编号,编号为奇数的为奇数位,编号为偶数的为
偶数位,看奇数位上的数字的和与偶数位上的数字
的和的
两者之差是否能被11整除; 81729033÷11:奇数位和
11
为6
,偶数位和为27;如果奇数位和比偶数位和小,则
奇数位和加1个或多个11,直到够减。11可以无
敌乱切,
但还是常用奇偶位截断求差法;
9
999
三位一截求和
再截法
从右往左三位一截,将截取的段位数相加再截取,直至不
能再截取,看相应的数能否被999整除。
从右往左四位一截,将截取的段位数相加,看相应的数能
否被11整除。
10
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+…+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个数依次写下来,得到一个
很大的多位数:
1112….20102011,则这个数除以9余数是1.
无敌乱切,按1234到2011的等差数列求和,看除以9的余数;
2.3.3同余定理
2.3.2.1同余定义和充要条件
定义: 用给定的正整数m分别除整数a、b,如果所得
的余数相等,则称a、
b关于模m同余或a同余于b模m,记作a≡b(mod m),如 56≡0
(mod 8),
式子称为同余式,m称为该同余式的模。
充要条件:整数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、b的同倍数也关于模m同余;
定理2
若ca≡cb(mod m), (c,m)=d(最大公约数),
且a,b为整数,则
a≡b(mod md).
推论若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]).
【例】将1
996加上一个整数,使和能被9和11整除,加的整数尽可能小,
那么加的整数是多少?
1996≡16(mod 99);99-16=83
定理4若a≡b (mod
m),则a
n
≡b
n
(modm),其中n是自然数。
2.3.2.5同余定理的重要推论:两个同模同余式的加减乘运算
若a≡b(mod m), c≡d (mod
m),则可以将这两个同余式左右两边分别相加、
相减或相乘:
1)a+c≡b+d
(mod m);即和的余数等于余数的和
2)a-c≡b-d (mod
m);即差的余数等于余数的差;
3)ac≡bd (mod m);即积的余数等于余数的积;
【例】316×419×813除以13所得的余数
2.3.4只知被除数和余数,求除数或求商
2.3.4.1余数确定(注意余数比除数小)
有余数的情况:a÷b=c…..d(0﹤d﹤b);
b=(a-d)
÷c;或c=(a-d) ÷b
如果,只知a和d,求b或c
【例】1111
÷某2位数=()…..66
2.3.4.2余数不确定
① 余数不确定——余数的和
【例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个:
1258
2129
386
643
因为余数要小于除数,判断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的约数有165,513,除数大于余数,排除1和65,5和13都
满足;
④ 余数不确定——余数的倍数
【例4】61=m×(商)+2a
90=m×()+a
变为180=m×()+2a,
根据同余定理:
m∣(180-61)= m∣(119);
119的约数有1119,717,除数大于余数,排除1和119,仅17
满足;
2.3.5幂和连乘积的余数——余数的周期性
周期性的用法:可用以求某个数的若干次方的个位数:
【例】3
2015
的个位数:
3的若干次方的个位数,依次枚举,找出循环
规律,4个一个周期,2015
除以4,余几为周期内第几个。
幂的余数的求法:先求底数的
余数,再算底数的幂的余数的周期性,再根据
指数相应的周期来确定最终的余数;
【例】2015
100
除以7的余数:
2015
100
≡6
100
≡1(mod7)
6,36,196,1176…除以7的余数分别为6,1,6,1,2个为1周期,100÷2=50余0,故余数为1。
特殊情况:
①
【例】3
2014
除以8的余数:
3
2014
≡9
1007
≡1(mod8)
9除8的余数为1,所以无论指数多少,余数皆为1。
【例】316
25
除以9的余数:
【例】143
89
除以7的余数:
【例】3333
5555
+5555
3333
除以7的余数:
② 作业5,2的3次方以上模8的余数皆为0
2.3.6中国剩余定理——物不知数 (韩信点兵)
2.3.6.1传统题目和传统解法
【题目】今物知其数三三数剩二(数除三余数二意思),五五数剩三,七七数
剩二,问物几何(
韩信点兵算所谓剩余定理)
【解法】
三人同行七十稀;把除以3所得的余数用70乘
五树梅花廿一枝;把除以5所得的余数用21乘;
七子团圆正半月;把除以7所得的余数用15乘
除百零五便得知;把上述三个积加起来,除以105的余数即为得数;
2×70+3×21+2×15=233 233÷105=2…23;得数为23。
2.3.6.2物不知数:余数问题的通解:基本的枚举法
① 从除数大的开始枚举;
②
先找同时满足两个除数的最小符合数,再加这俩除数的最小公倍数,直
到满足所有除数的最小的符合数;
③ 再加所有除数的最小公倍数×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。
③ 在所有除数的最小公倍数内一定能找到最小的满足数;
④ 多个符合数必然是一个以所有除数的最小公倍数为等差的等差数列
2.3.6.3物不知数:余数问题的通解:特殊情况
① 余数相同的——最
小符合数就是余数,其他的为除数的最小公倍数的倍
数+余数(即最小符合数+除数的最小公倍数的倍数
);
【例】5余4,7余4,9余4,最小的为4;
【例】某除4、除5、除6皆余1,某=456的公倍数+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=251
9
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
个的最小公倍数;
2.3.6.4物不知数:可以用来解决除以12和6的余数的算法:互质分
解
求A=123456……319被1214154599除的余数;
将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=20162016……2016被495除的余数;
︸
100个2016
互质分解法:将495互质分解
=9×5×7,求同时满足除以9余0,除以5余
1,除以11余9的物不知数,即为余数;
2.3.6.4物不知数:非典型物不知数题目转为物不知数题目
【例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=
5n+1
3
除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;与辗转
相除法类似;