2014年寒假数学联赛提高班导学4-重点难点 知识点 例题精讲

2014 年寒假 数学联赛 提高 班 导学 （第 四 次） 资料 说明 本 导学用于学员在实际授课之前，了解授课方向及重难点。同时还附上部分知识点的详细解读。每个班型导学共由 4 次书面资料构成。此次发布的为第四次导学。 4 次导学的相应关联以及课程详细授课内容，请参见相应班型的详细授课大纲。寒假授课即将开始，除现场授课及答疑外，欢迎大家参加寒假之后的在线答疑活动。祝大家在寒假中收获良多，学习进步！ 自主招生邮箱： 数学竞赛邮箱： 物理竞赛邮箱： 化学竞赛邮箱： 生物竞赛邮箱： 理科精英邮箱： 2013-12-25 发布 清北学堂教学研究部 清北学堂集中 培训课程 导学资料 （ 2014 年寒假集中培训 课程 使用 ） QBXT/JY/DX2013/12-4-4 清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 1 页 2014 年寒假 数学联赛 提高 班 导学 (初等数论 部分 ) 目录 一、 课程重点及难点概述 . 2 二、 清北导学 . 3 整数问题 . 3 重点及难点 . 3 知识点 . 3 整除 . 5 重点及难点 . 5 知识点 . 5 思考题 . 8 同余 . 9 重点及难点 . 9 知识点 . 9 思考题 . 13 不定方程 . 14 重点及难点 . 14 知识点 . 14 思考题 . 17 清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 2 页 一、 课程重点及难点概述 本次课程的重点为整除与同余问题。剩余类的概念、欧拉函数和不定方程有关的定理是本次培训的难点。提高班以真题讲解为主，穿插相关知识点，训练同学的解题思路。 清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 3 页 二、 清北导学 整数问题 重点及难点 整数相关问题是初等数论的基础。本部分需要重点掌握算术基本定理，并了解进制的相互转换规则。 知识点 1. 整数与其进位制 ： 在集合观点下，整数是整数集合的简称，记为 Z ， =n|n=0, 1, 2, Z 。整数对“加、减、乘”三种运算封闭，对“除、开方”运算不封闭。 正整数有无穷多个，为了用有限的个数符号表示出无限个正整数，前人发明了进位制。 10 是十进制的基，任何大于 1 的整数 r 均可作为 r 进位制的基。 自然数 N 的 r 进制是把 N 表示成 r 的 n 次多项式的形式，即 11 1 0nnnnN a r a r a r a ，其中 0 , 1 , 2 , , 1 , 0 , 1 , 2 , . 0ina r i n a ，并记作1 1 0()n n rN a a a a 。 r 进制记数法的基本原则是“逢 r 进 1”。 不同进位制的数可以相互转换，如 324 1 0(1 0 2 1 ) 1 4 0 4 2 4 1 ( 7 3 ) 。十进制数转换成 P 进制数是“除 P 取余”法，例如 4 3 21 3 7 1 3 + 2 3 + 0 3 + 0 3 + 2 ，故 3137 (12002) 。 a进制数转为 b 进制数，只需先把 a 进制数转换为十进制数，再由十进制数转换为 b 进制数。 2. 整数的奇偶性： 将全体整数分为两类，凡是 2 的倍数的数称为偶数，否则称为奇数，因此，任意 偶数可表示成 2 ( )mm Z ，任意奇数可表示为 21m 的形式。奇数偶数具有如下性质： 奇数 奇数 =偶数；偶数 偶数 =偶数；奇数 偶数 =奇数；偶数 偶数 =偶数； 清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 4 页 奇数 偶数 =奇数；奇数 奇数 =奇数。 奇数的平方都可以表示为 81m 的形式，偶数的平方都可以表示为 8m 或 84m 的形式。任何一个正整数 n，都可以写成 2mnl 的形式，其中 m 为非负整数， l 为奇数。 3. 质数与合数、算术基本定理： 大于 1 的整数按它具有因数的情况可以分为质数和合数两类。 一个大于 1 的整数，如果除了 1 和它自身外没有任何正因子，则称此数为质数或素数，否则，称为合数。 显然， 1 既不是质数也不是合数； 2 是最小的且是唯一的偶质数。 算术基本定理：任何大于 1 的整数 A 都可以分解成质数的乘积，若不计这些质数的 次序，则这种质因子分解表达式是唯一的，进而 A 可以写成标准分解式：12 naaa nA p p p ，其中 12 np p p ， ip 为质数， ia 为非负整数， 1,2, ,in 。 合数的因子个数计算公式：若 12 naaa nA p p p 为标准分解式，则 A 的所有因子（包括 1 和 A 本身）的个数为1( 1)n ii a 。 质数的判定定理：设 n 是大于 2 的整数，如果不大于 n 的质数都不是 n 的因子，则 n 是质数。 质数的个数是无穷的。 清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 5 页 整除 重点及难点 整除问题是初等数论中非常重要的一类问题。费马定理、裴蜀定理和辗转相除法是本次学习的重点。 知识点 1. 整数的整除性 初等数论的基本研究对象是自然数集合及整数几何。我们知道，整数集合中可以作加、减、乘运算，并且这些运算满足一些规律（即加法和乘法的结合律和交换律，加法与乘法的分配率），但一般不能做除法，即，如 ,ab是整数， 0b ，则 ab不一定是整数。由此引出初等数论中第一个基本概念：整数的整除性。 带余除法：对于任一整数 a 和任一整数 b ，必有唯一的一对整数 ,qr，使得 =abq r ，0 rb ，并且整数 q 和 r 由上述条件唯一确定，则 q 称为 b 除 a 的不完全商， r 称为 b除 a 的余数。 若 =0r ，则称 b 整除 a ，或 a 被 b 整除，或称 a 是 b 的倍数，或称 b 是 a 的约数（又叫因子），记为 |ba，否则 |ba 。 任何 a 的非 1a， 的约数，叫做 a 的真约数。 0 是任何整数的倍数， 1 是任何整数的约数。任一非零的整数是其本身的约数，也是其本身的倍数。由整除的定义，不难得出整除的如下性质： （ 1）若 | , |abbc ，则 |ac （ 2）若 |iab ，则1|n iiia cb，其中 , 1,2, ,ic Z i n （ 3）若 |ac，则 |abcb （ 4）若 |ab，则 ab 。因此，若 |ab，又 |ba，则 ab 。 （ 5） ab、 互质，若 |ac， |bc，则 |abc 。 （ 6） p 为质数，若 12| npa a a ，则 p 必能整除 12, , , na a a 中的某一个。特别地，若 p为质数， | npa，则 |pa。 清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 6 页 （ 7）如在等式11nmikikab中除开某一项外，其余各项都是 c 的倍数，则这一项也是 c的倍数。 （ 8） n 个连续整数中有且只有一个是 n 的倍数。 （ 9）任何 n 个连续整数之积一定是 n 的倍数。 2. 费马定理 Fermat 定理：设 p 为质数，对任何整数 n ，都成立 | ppn n （或 (mod )pn n p ） 推论： p 为质数，且 |pn ，则 -1|1ppn （或 -1 1(mod )pnp ） 3. 最大公约数和最小公倍数 定理一：算术基本定理 定理二：设大于 1 的整数 a 的标准分解式为 12 naaa na p p p （ 1 npp为质数， ia 均为非负整数），则 a 的约数个数为： 1( ) ( 1)n iid a a 所有的约数和为： 111() 1ian ii ipa p 定义 2：设 ab、 是两个不全为 0 的整数。若整数 c 满足： |,|cacb ，则称 c 为 ,ab的公约数， ab、 的所有公约数中的最大者称为 a 与 b 的最大公约数，记为 (,)ab 。如果(, ) 1ab ，则称 a 与 b 互质或互素。 定义 3：如果 d 是 a 、 b 的倍数，则称 d 是 a 与 b 的公倍数。 a 与 b 的公倍数中最小的正数称为 a 与 b 的最小公倍数，记为 ,ab 。 最大公约数和最小公倍数的概念可以推广到有限多个整数的情形。若 12( , , , ) 1na a a ，则称 12, , , na a a 互质，若 12, , , na a a 中任何两个都互质，则称它们是两两互质的。 定理 3：设 a 、 b 、 c 是三个不全为 0 的正数，且有正数 t 使得 a bt c，则 ( , ) ( , )a b b c ，即 ( , ) ( , )a b b a bt 定理 4（裴蜀定理）：设 a 、 b 是整数，则 ( , )ab d 的充要条件是存在整数 u ， v ，使得 a vb d 辗转相除法（欧几里得算法）：设 a 、 bN ，且 ab ，由带余除法有 清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 7 页 因为每进行一次带余除法，余数至少减少 1，即 ,而 b 为有限数，因此，必有一个最多不超过 b 的正整数 n 存在，是的 rn0 ,，故 最大公约数和最小公倍数的常用性质： （ 1） a 和 b 的任一公约数都是它们的最大公约数的约数 （ 2） mN ,则 (am,bm) = m(a,b) （ 3）设 c 为 a ， b 的公约数，则 (ac,bc)=(a,b)c （ 4）设 是任意 n 个正整数，如果 ，则 （ 5）设 a 和 b 均与 m互素，则 ab 也与 m互素 （ 6）若 b|ac ，且 (b,c)=1 ，则 b|a （ 7）若 (a,b)=1 ，则 (ac,b)=(c,b) （ 8）若 m是整数， a|m,b|m ，则 a,b|m （ 9）若 m是正整数，则 ma,b=ma,mb （ 10）两两互素的正整数的最小公倍数等于它们的乘积 （ 11）设 是任意 n 个正整数，如果 ，则 4. 方幂问题 一个正整数 n 能否表示成 m 个整数的 k 次方和的问题称为方幂和问题。 能表示成某整数的平方的数称为完全平方数，简称平方数。关于平方数，明显有如下一些简单地性质和结论： （ 1） 平方数的个位素质只能是 0， 1， 2， 4， 5， 6， 9 （ 2） 偶数的平方数是 4 的倍数，奇数的平方数被 8 除余 1，即任何平方数被 4 除的余数只能是 0 或 1. 清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 8 页 （ 3） 奇数平方的十位数字是偶数 （ 4） 十位数字是奇数的平方数的个位数一定是 6 （ 5） 不能被 3整除的数的平方被 3除余 1，能被 3整除的数的平方也能被 3整除。因而，平方数被 9 除的余数为 0， 1， 4， 7，且此平方数的各位数字的和被9 除的余数也只能是 0， 1， 4， 7 （ 6） 平方数的约数的个数为奇数 （ 7） 任何四个连续整 数的乘积加 1，必定是一个平方数 定理：奇素数 p 能表示成两个正整数的平方和的充要条件是 p=4m+1 思考题 一、 ABC 中，边长 a,b,c(a b c)同时满足下列三个条件 （ 1） a,b,c 均为整数（ 2） a,b,c 组成等比数列（ 3） a 与 c 至少有一个等于 100 求出三元数组 (a,b,c) 的所有可能的解 二、 确定所有的正整数对 (n,p) ，满足： p 是一个质数， n2p ，且 (p-1)n +1能够被 np-1 整除。（ 40th IMO NO.3） 清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 9 页 同余 重点及难点 同余是数论中的重要概念，同余理论是研究整数问题的重要工具之一。本部分介绍同余的基本概念、剩余类和完全剩余类、同余方程和中国剩余定理。其中同余和剩余类是学习的重点。 知识点 1. 基本概念 定义 1：设 m 是一个给定的正整数，如果两个整数 a,b 用 m 除所得的余数相同，则称 a,b 对模 m 同余，记作 a b(modm) ；否则，记为 a / b(modm) 。 等价定义：（ 1）若 m|a-b ，则称 a,b 对模 m 同余 （ 2）若 a = b + mt(t Z )，则称 a,b 对模 m 同余 同余的基本性质： （ 1） a 0 (m od m ) m | a （ 2）a a ( m od m )a b ( m od m ) b a ( m od m )a b ( m od m )b c ( m od m ) a c ( m od m ) （ 3）若 a b ( modm) ， c d(modm) ，则 a c b d ( m od m )； ac bd (mod m) （ 4）若 ，则 （ 5）若 ac bc(mod m)，则 a b(mod m(m, c)。 特别地，若 (c,m)=1 ，则 a b(modm) 。 （ 6） a b(modm) ，而 d| m(d 0) ，则 a b(modd) 。 清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 10 页 （ 7）设 a b(modm) a：若 c0 ，则 ac bc(mod m) b:d 为 a,b,m 的任一公约数，则 ad bd (mod md ) （ 8） 若 a b(mod m1) , a b(mod m2 )且 (m1,m2)=1 ，则 a b(mod m1m2 ) （ 9） 若 a b(modm) ，则 (a,m) = (b,m) （ 10） 若 p 为质数，则 ap a(mod p)。 特别地， p 为质数且 (a,p)=1 ，则 a p-1 1(mod p)。 2. 剩余类和完全剩余类 定义 2：设 mN* ，把全体整数按其对模 m 的余数 r(0 r m -1)归于一类，记为，每一类 均称为模 m 的剩余类（又叫同余类）。同一类中任一数称为该类中另一数的剩余。 剩余类 kr 是数集 kr=qm+ r （ m 是模， r 是余数， qZ ），也即k r = a | a Z , a r ( m od m ) ，它是一个公差为 m 的（双边无穷）等差数列。 定义 3：设 是模 m 的（全部）剩余类，从每个 kr 中任取一个数 ar ，这 m 个数 组成一个组称为模 m 的一个完全剩余系，简称完系。 定理 1： m 个整数 是模 m 的一个完系 当 ij 时， ai / aj (mod m)。 定理 2 ：设 (b,m)=1 ， c 为任意整数。若 为一个完系，则也是模 m 的一个完全剩余类。 定义 4： m 为一正整数，把 中与 m 互质的数的个数叫做 m 的欧拉函数，记为 j(m) 。 定义 5：如果一个模 m 的剩余类 kr 中任一数与 m 互质，则称 kr 是与模 m 互质的剩余类；在与模 m 互质的每个剩余类中任取一个数（共 j(m) 个）所组成的数组，称为模 m 的一个简化剩余系。 清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 11 页 定理 3： 是模 m 的简化剩余系 (ai,m)=1 ，且 。 定理 4：在模 m 的一个完全剩余系中，取出所有 与 m 互质的数组成的数组，就是一个模 m 的简化剩余系。 定理 5：设 是模 m 的简化剩余类。若 (k,m)=1 ，则也是模 m 的简化剩余类。 定理 6（欧拉定理）：若 (a,m)=1 ，则 （费马小定理）若 m=p 为质数， p|a ，则 a p-1 1(mod p)。 定理 7（威尔逊定理）：设 p 是素数，则 ( p - 1)! -1(m od p ) 定理 8（欧拉函数值计算公式）令 m 的标准分解式为 则 j ( m ) = m (1 - 1p i )i =1k 3. 同余方程 设 为 x 的正系数多项式 定义 6：同余式 f ( x ) 0 m od( m ) , a n / 0 ( m od m )叫做一元 n 次同余方程 定义 7：若 c 使得 ( ) 0 mod( )f x m 成立，则 x c(modm) 叫做同余方程f (x) 0(mod m)的一个解 1、 一次同余方程 ax b (m od m ), m /| a称为一次同余方程 定理 9：若 (a,m)=1 ，则 ax b(mod m)有一个解。 定理 10：若 ( a , m ) = d 1, d /| b，则 ax b(mod m)无解，其中 a / 0(modm) 定理 11：若 (a,m) = d 1,d |b，则 ax b(mod m)有 d 个解，并且，若a x b (mod m1)的一个解为 x r(modm1) ，则 d 个解为： aj (m ) 1(mod m)清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 12 页 ，其中 a = ad , b = bd , m1 = md 推论：一次同余方程 ax b (m od m ), ( a , m ) = 1的解法 解法 1：因 (a, m) =1 ，则存在二数 s,t, 使得 as+mt =1 ，即 as 1(modm)，由此有 asx bs (mod m)，于是 x bs(mod m)为原方程的解 解法 2：原方程变形为 x ba (mod m) (ba 仅只是形式上的记号 )，然后用与 m 互质的数陆续乘右端的分子分母，直至把分母绝对值变成 1（通过分子分母各对模 m取余数）而得到解 解法 3：利用欧拉定理。因 aj (m ) 1(mod m)，由 ax b(mod m)可得a j (m )x b a j (m )-1(m od m )，从而有解。 x b a j ( m )-1 (m od m ) 2、 一次同余方程组 定义 8：若数 r 同时满足 n 个同余方程： ，则 r叫做这 n 个同余方程组成的同余方程组的解 定理 12：对同余方程组 x c1 (m od m 1 )x c2 (m od m 2 ) 记 ( m 1 , m 2 ) = d , m 1 , m 2 = M （ 1） 若 d/| c1-c2 ，则此同余方程组无解 （ 2） 若 d|c1-c2 ，则此同余方程组有对模 M 的一类剩余解。 4. 中国剩余定理（孙子定理） 设 是两两互质的正整数，记 则同余方程组 清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 13 页 有且只有解 x M ia i c ii = 1n (m od M ) 其中 思考题 一、 解同余方程组 2 x 3 ( m od 5 ) , 10 x 4 ( m od 2 ) 二、 设 p,q 是不同的奇素数，证明： pq | 2 pq - 1 - 1 p | 2 q - 1 - 1 ( and ) q | 2 p - 1 - 1 清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 14 页 不定方程 重点及难点 所谓不定方程（组），是指未知数的个数多于方程的个数，且未知数受到某些限制（如整数，正整数或有理数）的方程（组）。 对于一个一般得不定方程（组），除个别情况下，通常没有一个统一的解法，而且有许多不定方程）（组），目前还无法判断其是否有解，因此，必须对给定的不定方程（组）的具体形式进行分析，确定解题方向。下面介绍几种常见的方法。 知识点 1. 公式法 （ 1） 一次不定方程 在不定方程和不定方程组中，最简单地不定方程是整系数方程 ax + by + c = 0 , ( a b , b 0 ) 通常称之为二元一次不定方程。 定理 1：二元一次不定方程 ax + by = c , (a , b , c Z )有正整数解的充要条件 是 (a,b)|c 定理 2：若 (a,b) =1 ,且 x0,y0 为 ax + by + c = 0 , ( a b , b 0 )之一解，则其全部解为 x = x 0 + bt , y = y 0 - at ( t Z ) （ 2） 沛尔（ pell）方程 二元二次不定方程本质上归结为（双曲型）方程 x2 -dy2 =c 的研究，其中 d,c 都是整数， d0 且非平方数，而 c0 . 特别的， x2 -dy2 =1 称为沛尔方程。沛尔方程有无穷多组正整数解。设 (x1,y1) 是沛尔方程的正整数解 (x,y) 中使 x+y d 最小的解，则沛尔方程的全部正整数解为 清北学堂集中培训课程导学资料 北京清北学堂教育科技有限公司 第 15 页 实际上有递推关系成立 x n = 2 x 1 x n - 1 - x n - 2y n = 2 x 1 y n - 1 - y n - 2 （ 3） 勾股方程 x2 +y2 =z2 定理 3：方程 x2 +y2 =z2 满足 (x,y) =1,z | y 的全部正整数解 (x,y,z) 可以表示为x = a 2 - b 2 , y = 2 ab , z = a 2 + b 2 其中， a,b 是满足 ab0 ,a,b 一奇一偶，且 (a,b)=1 的任意整数。 （ 4） 不定方程 xy=zt 设 (x,z)=a ，则 x = ac,z = ad ，其中 (c,d)=1 ，故 acy=adt ，即 cy=dt ，因(c,d)=1 ，所以 d|y ，设 y=bd ，则 t=bc ，因此方程 xy=zt 的正整数解可以表示为 x = ac , y = bd , z = ad , t = bc ( a , b , c , d Z + , ( c , d ) = 1 ) 2. 奇偶分析法 整数分为奇数和偶数两类，所以解不定方程可以从未知数、系数的奇偶性入手，讨论取值的可能情形，一方面可以达到缩小未知数的取值范围