《数学竞赛常用知识手册》由会员分享，可在线阅读，更多相关《数学竞赛常用知识手册（38页珍藏版）》请在金锄头文库上搜索。
1、1竞赛常用知识手册数论部分1整除1.定义对于整数a、b(b 6= 0),存在整数q,满足a = bq就叫做a能被b整除,记作b|a.其中a叫做b的倍数, b叫做a的约数(因数).若b 6= 1,则b叫做a的真约数.若a不能被b整除,则记作b - a.如果at|b, at+1- b, t N,记作atkb.2.关于整除的一些简单性质(1)b|0, 1|a, a|a(a 6= 0).(2)若b|a, a 6= 0,则1 6 |b| 6 |a|.(3)若c|b, b|a,则c|a.(4)若b|a, c 6= 0,则bc|ac.(5)若c|a, c|b,则c|(ma + nb)(m、n Z).(6)若
2、kPi=1ai= 0, b能整除a1, a2, , ak中的k 1个,则b能整除另一个.2同余1.定义设m为正整数,若整数a和b被m除的余数相同,则称a和b对模m同余,记作a b(modm).2.基本性质(1)a b(modm) m|(b a).(2)a b(modm) b = km + a(k Z).(3)a a(modm).(4)若a b(modm),则b a(modm).(5)若a b(modm), b c(modm),则a c(modm).博杰学习网 http:/lbj.80.hk2(6)若a b(modm), c d(modm),则a c b d(modm), ac bd(modm)
3、, an bn(modm).(7)若ac bc(modm), (c, m) = d,则a b(modm d).其中符号(c, m)表示c与m的最大公约数.特别地,当(c, m) = 1时,若ac bc(modm),则a b(modm).3.同余类由关于模m同余的整数组成的集合,每一个集合叫做关于模m的同余类(或叫做关于模m的剩余类).由于任何整数被m除的余数只能是0, 1, , m1这m种情形,所以,整数集可以按对模m同余的关系分成m个子集: A0, A1, , Am1.其中Ai= qm + i|m为模, q Z, i = 0, 1, , m 1.所有的Ai(i = 0, 1, , m 1)满
4、足m1Si=0Ai= Z,m1Ti=0Ai= .4.完全剩余系从横m的m个同余类A0, A1, , Am1中,每一类Ai取一数ai,则a0, a1, , am1叫做模m的一个完全剩余系(简称模m的完系).最简单的模m的完全剩余系是0, 1, , m 1,也叫做模m的最小非负完系.显然m个相继整数构成模m的一个完系.3质数与合数1.一个大于1的整数,如果只有1和它本身作为它的约数,这样的正整数叫做质数(也叫素数);如果除了1和它本身之外还有其他的正约数,这样的正整数叫做合数.1既不是质数也不是合数.因此,正整数集Z+= 1S质数S合数.2.大于1的整数的所有真约数中,最小的正约数一定是质数.3.
5、合数a的最小质约数不大于a.4.质数有无穷多个.5.不存在这样的整系数多项式f(n) =mPi=0aini,使得对任意的自然数n, f(n)都是质数.6.威尔逊(Wilson)定理p为质数的充分必要条件是(p 1)! 1(modp).4质因数分解1.质因数分解定理(整数的唯一分解定理)每一个大于1的整数都能分解成质因数连乘积的形式,且如果把这些质因数按照由小到大的顺序排列(相同因数的乘积写成幂的形式),这种分解方法是唯一的.32.整数n(n 1)的标准分解式为n =mQi=1pii.其中pi为质数, i为正整数, i = 1, 2, , m.3.约数个数定理设d(n) =Pd|n1表示大于1的
6、整数n的所有正约数的个数, n的标准分解式为n =mQi=1pii,则d(n) =mYi=1(1 + i).4.约数和定理设(n) =Pd|nd表示大于1的整数n的所有正约数的和, n的标准分解式为n =mQi=1pii,则(n) =mYi=1pi+1i 1 pi 1.5.在n!的标准分解式中,质因数p的方幂为Pr=1n pr .其中记号x表示不超过x的最大整数.5公约数和公倍数1.公约数和最大公约数(1)若c|a1, c|a2, , c|an,则c称为a1, a2, , an的公约数.a1, a2, , an的所有公约数中最大的一个称为a1, a2, , an的最大公约数.记作(a1, a2
7、, , an).(2)若a1, a2, , an的标准分解式为a1=mQi=1pii, a2=mQi=1pii, , an=mQi=1pii,其中pi为质数, i, i, i为非负整数, i = 1, 2, , m,则(a1, a2, , an) =mQi=1ptii,其中ti= mini, i, , i.(3)如果a是b的倍数,那么a和b的公约数的集合与b的约数集合相等.(4)如果a是b的倍数,则(a, b) = b.(5)设a和b是不同时等于1的正整数,且d = ax0+ by0是形如ax + by(x、y是整数)的整数中的最小正整数,则d = (a, b).(6)正整数a和b的公约数集合
8、与它们的最大公约数的约数集合相等.(7)设m是任意正整数,则(am, bm) = (a, b)m.(8)设n是a和b的一个公约数,则?a n,b n =(a, b) n.(9)设正整数a和b(a b)满足等式a = bq + r, 0 6 r r1 r2 r3 以及ri(i = 1, 2, )是非负整数,则一定在进行到某一次时,例如第n + 1次得到rn+1= 0.但由于rn6= 0,则有(a, b) = (b, r1) = (r1, r2) = = (rn1, rn) = rn.用此法还可以求(5)中形如ax + by的最小正整数d = ax0+ by0.2.公倍数和最小公倍数(1)若a1|
9、b, a2|b, , an|b,则b称为a1, a2, , an的公倍数. a1, a2, , an的所有公倍数中最小的一个称为a1, a2, , an的最小公倍数.记作a1, a2, , an.(2)若a1, a2, , an的标准分解式为a1=mQi=1pii, a2=mQi=1pii, , an=mQi=1pii,其中pi为质数, i, i, i为非负整数, i = 1, 2, , m,则a1, a2, , an =mQi=1prii,其中ri= maxi, i, , i.(3)a1, a2, , an的最小公倍数是它们的任一公倍数的约数.(4)a, b =ab (a, b).6互质数、
10、 费马小定理和孙子定理1.互质数(1)若(a1, a2, , an) = 1,就叫做a1, a2, , an互质(也叫做互素).这n个数叫互质数(互素数).特别地, 1和任何整数互质;相邻两个整数互质;相邻两个奇数互质;对质数p,若p不能整除a,则p与a互质.(2)若(a, b) = 1,则(a b, a) = 1, (a b, ab) = 1.(3)若(a, b) = 1, a|bc,则a|c.(4)若a|c, b|c, (a, b) = 1,则ab|c.(5)若(a, b) = 1,则(b, ac) = (b, c).(6)若(a, b) = 1, c|a,则(c, b) = 1.(7)若
11、(a, b) = 1,则(a, bk) = 1.(8)若a1, a2, , am中的每一个与b1, b2, , bn中的每一个互质,则(a1a2am, b1b2bn) = 1.2.欧拉函数定义:小于m且与m互质的正整数的个数叫做欧拉(Euler)函数,记作(m).5若m =nQi=1pii,则(m) = mnQi=1? 1 1 pi .其中pi是质数, i是正整数(i = 1, 2, , n).当m为质数时, (m) = m 1.性质:(1)(m)是积性函数,即(a, b) = 1,则(a)(b) = (ab).(2)若p是质数,则(p) = p 1, (pk) = pk pk1.(3)设m
12、= p11p22pkk,则(m) = m? 1 1 p1? 1 1 p2 ? 1 1 pk .(4)设d1, d2, , dT(m)是m的所有正约数,则T(m)Pi=1(di) = m.3.欧拉定理和费马小定理(1)欧拉定理设m 2,且(a, m) = 1, (m)为欧拉函数,则a(m) 1(modm).(2)费马(Fermat)小定理设p是质数,且(a, p) = 1,则ap1 1(modp).注:费马小定理是欧拉定理当m为质数时的特例.4.孙子定理设m1, m2, , mk是k个两两互质的正整数.则同余式组x b1(modm1),x b2(modm2),x bk(modmk)有唯一解x M
13、01M1b1+ M02M2b2+ + M0 kMkbk(modM).其中M = m1m2mk, Mi=M mi, i = 1, 2, , k, M0iMi 1(modmi), i = 1, 2, , k.注:孙子定理又叫中国剩余定理.7奇数和偶数1.若一个整数能被2整除,则这个整数叫偶数;若一个整数被2除余1,则这个整数叫奇数.奇数集合和偶数集合都是以2为模的同余类.62.奇数个奇数的和(或差)是奇数,偶数个奇数的和(或差)是偶数.任意多个偶数的和(或差)为偶数.一个奇数与一个偶数的和(或差)是奇数.两个整数的和与差在相同的奇偶性.3.任意多个奇数的积是奇数.若任意多个整数中至少有一个偶数,则
14、它们的积是偶数.8完全平方数1.若a是整数,则a2叫做a的完全平方数.2.完全平方数的个位数只能是0, 1, 4, 5, 6, 9.3.奇数的平方的十位数是偶数.4.个位数是5的平方数,其十位数是2,百位数是偶数.5.如果一个完全平方数的个位数是6,那么它的十位数是奇数.6.偶数的平方能被4整除;奇数的平方被4除余1.7.偶数的平方被8余余0或4;奇数的平方被8除余1.8.若一个整数能被3整除,则这个数的平方能被3整除;若一个整数不能被3整除,则这个数的平方被3除余1.9.若一个整数能被5整除,则这个数的平方能被5整除;若一个整数不能被5整除,则这个数的平方被5除余+1或1.10.把完全平方数
15、的各位数码相加,如果所得到的和不是一位数,再把这个和的各位数码相加,直到和是一位数为止,这个一位数只能是0, 1, 4, 7, 9.11.两个相邻完全平方数之间不可能有完全平方数.12.完全平方数的所有正约数个数为奇数,并且反过来也成立.13.如果质数p是一个完全平方数的约数,那么p2也是这个完全平方数的约数.9整数的可除性特征1.一个整数能被2整除的充分必要条件是这个数的个位数是偶数.2.一个整数能被4整除的充分必要条件是这个数的末两位数能被4整除.3.一个整数能被5整除的充分必要条件是这个数的个位数是0或5.4.一个整数能被3整除的充分必要条件是这个数的各位数字之和能被3整除.75.一个整数能被9整除的充分必要条件是这个数的各位数字之和能被9整除.6.一个整数能被11整除的充分必要条件是这个数的奇位数字之和与偶位数字之和的差能被11整除.7.一个整数能被10n 1(n为正整数)整除的充分必要条件是把这个数的个位数截去之后,再加上这个个
