《（经典）高中数学竞赛常用知识汇集》由会员分享，可在线阅读，更多相关《（经典）高中数学竞赛常用知识汇集（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. (
2、5)若c|a, c|b,则c|(ma + nb)(m、n Z). (6)若 k P i=1 ai= 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). 2 (5)若a b(modm), b c(modm),则a c(modm). (6)若a b(modm), c d(mo
3、dm),则a c b d(modm), ac bd(modm), an bn(modm). (7)若ac bc(modm), (c, m) = d,则a b(mod m 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,
4、 i = 0, 1, , m 1. 所有的Ai(i = 0, 1, , m 1)满足 m1 S i=0 Ai= Z, m1 T i=0 Ai= . 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既不
5、是质数也不是合数.因此,正整数集Z+= 1 S质数S合数. 2.大于1的整数的所有真约数中,最小的正约数一定是质数. 3.合数a的最小质约数不大于a. 4.质数有无穷多个. 5.不存在这样的整系数多项式f(n) = m P i=0 aini,使得对任意的自然数n, f(n)都是质数. 6.威尔逊(Wilson)定理 p为质数的充分必要条件是(p 1)! 1(modp). 4质因数分解 1.质因数分解定理(整数的唯一分解定理) 3 每一个大于1的整数都能分解成质因数连乘积的形式,且如果把这些质因数按照由小到大的顺序排 列(相同因数的乘积写成幂的形式),这种分解方法是唯一的. 2.整数n(n 1)
6、的标准分解式为n = m Q i=1 pi i .其中pi为质数, i为正整数, i = 1, 2, , m. 3.约数个数定理 设d(n) = P d|n 1表示大于1的整数n的所有正约数的个数, n的标准分解式为n = m Q i=1 pi i ,则 d(n) = m Y i=1 (1 + i). 4.约数和定理 设(n) = P d|n d表示大于1的整数n的所有正约数的和, n的标准分解式为n = m Q i=1 pi i ,则 (n) = m Y i=1 pi+1 i 1 pi 1 . 5.在n!的标准分解式中,质因数p的方幂为 P r=1 n pr .其中记号x表示不超过x的最大整
7、数. 5公约数和公倍数 1.公约数和最大公约数 (1)若c|a1, c|a2, , c|an,则c称为a1, a2, , an的公约数. a1, a2, , an的所有公约数中最大的一个称为a1, a2, , an的最大公约数.记作(a1, a2, , an). (2)若a1, a2, , an的标准分解式为a1= m Q i=1 pi i , a2= m Q i=1 pi i , , an= m Q i=1 pi i ,其中pi为质数, i, i, , i为非负整数, i = 1, 2, , m,则(a1, a2, , an) = m Q i=1 pti i ,其中ti= mini, i,
8、, 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的公约数集合与它们的最大公约数的约数集合相等. (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 b, q、r Z.则(a, b
9、) = (b, r). 4 由此可得到求a、b最大公约数的辗转相除法. 设a = bq1+ r1, 0 6 r1 b. 若r1= 0,则(a, b) = b. 若r16= 0,则又可用r1去除b得b = r1q2+ r2, 0 6 r2 r1. 若r2= 0,则(a, b) = (b, r1) = r1. 若r26= 0,再用r2去除r1得r1= r2q3+ r3, 0 6 r3 r1 r2 r3 以及ri(i = 1, 2, )是非负整数,则一定在进行到某一次 时,例如第n + 1次得到rn+1= 0.但由于rn6= 0,则有(a, b) = (b, r1) = (r1, r2) = = (
10、rn1, rn) = rn. 用此法还可以求(5)中形如ax + by的最小正整数d = ax0+ by0. 2.公倍数和最小公倍数 (1)若a1|b, a2|b, , an|b,则b称为a1, a2, , an的公倍数. a1, a2, , an的所有公倍数中最小的一个 称为a1, a2, , an的最小公倍数.记作a1, a2, , an. (2)若a1, a2, , an的标准分解式为a1= m Q i=1 pi i , a2= m Q i=1 pi i , , an= m Q i=1 pi i ,其中pi为质数, i, i, , i为非负整数, i = 1, 2, , m,则a1, a
11、2, , an = m Q i=1 pri i ,其中ri= maxi, i, , i. (3)a1, a2, , an的最小公倍数是它们的任一公倍数的约数. (4)a, b = ab (a, b). 6互质数、 费马小定理和孙子定理 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
12、, 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)若(a, b) = 1,则(a, bk) = 1. (8)若a1, a2, , am中的每一个与b1, b2, , bn中的每一个互质,则(a1a2am, b1b2bn) = 1. 5 2.欧拉函数 定义:小于m且与m互质的正整数的个数叫做欧拉(Euler)函数,记作(m). 若m = n Q i=1 pi i ,则(m) = m n Q i=1 ? 1 1 pi .
13、 其中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 = p1 1 p2 2 pk k ,则(m) = m ? 1 1 p1 ? 1 1 p2 ? 1 1 pk . (4)设d1, d2, , dT(m)是m的所有正约数,则 T(m) P i=1 (di) = m. 3.欧拉定理和费马小定理 (1)欧拉定理 设m 2,且(a, m) = 1, (m)为欧拉函数,则a(m) 1(
14、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 M0 1M1b1+ M 0 2M2b2+ + M 0 kMkbk(modM). 其中M = m1m2mk, Mi= M mi , i = 1, 2, , k, M0 iMi 1(modmi), i = 1, 2, , k. 注:孙子定理又叫中国剩余定理. 7奇数和偶数 1.若一
15、个整数能被2整除,则这个整数叫偶数;若一个整数被2除余1,则这个整数叫奇数. 6 奇数集合和偶数集合都是以2为模的同余类. 2.奇数个奇数的和(或差)是奇数,偶数个奇数的和(或差)是偶数. 任意多个偶数的和(或差)为偶数. 一个奇数与一个偶数的和(或差)是奇数. 两个整数的和与差在相同的奇偶性. 3.任意多个奇数的积是奇数. 若任意多个整数中至少有一个偶数,则它们的积是偶数. 8完全平方数 1.若a是整数,则a2叫做a的完全平方数. 2.完全平方数的个位数只能是0, 1, 4, 5, 6, 9. 3.奇数的平方的十位数是偶数. 4.个位数是5的平方数,其十位数是2,百位数是偶数. 5.如果一个
16、完全平方数的个位数是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.把完全平方数的各位数码相加,如果所得到的和不是一位数,再把这个和的各位数码相加,直到 和是一位数为止,这个一位数只能是0, 1, 4, 7, 9. 11.两个相邻完全平方数之间不可能有完全平方数. 12.完全平方数的所有正约数个数为奇数,并且反过来也成立. 13.如果质数p是一个完全平方数的约数,那么p2也是这个完全平方数的约数. 9整数的可除性特征 1.一个整数能被2整除的充分必要条件是这个数的个位数是偶数. 2.一个整数能被4整除的充分必要条件是
