2013寒假数学竞赛集训专题-数论代数组合导学讲义(打包4份)

ww w. qb xt .c n 北京清北学堂教育科技有限公司 电话：010-88400806，010-88400903 网址：www.topschool.org 1 / 23 2013 寒假集训六数论导学，数论是高考中没有要求，但是中学数学竞赛大纲中提出要求的内容，需要 引起同学们注意，希望能提前做好预习和学习准备. 一、整除和同余 知识点 1、整数的整除性 初等数论的基本研究对象是自然数集合及整数集合. 我们知道，整数集合中可以作加、减、乘法运算，并且 这些运算满足一些规律（即加法和乘法的结合律和交换律，加法与乘法的分配律），但一般不能做除法，即， 如 ba, 是整除， 0b ，则 b a 不一定是整数. 由此引出初等数论中第一个基本概念：整数的整除性. 定义 1：（带余除法）对于任一整数 a 和任一整数b ，必有惟一的一对整数 q ，r 使得 rbqa  ， br 0 ， 并且整数 q 和 r 由上述条件惟一确定，则 q 称为b 除 a 的不完全商， r 称为b 除 a 的余数. 若 0r ，则称 b 整除 a ，或 a 被 b 整除，或称 ba是 的倍数，或称 ab是 的约数（又叫因子），记为 ab | . 否则，b | a . 任何 a 的非 1, a 的约数，叫做 a 的真约数. 0 是任何整数的倍数，1 是任何整数的约数. 任一非零的整数是其本身的约数，也是其本身的倍数. 由整除的定义，不难得出整除的如下性质： （1）若 .|,|,| cacbba 则 （2）若 .,,2,1,,|,| 1 niZcbcaba i n i iii   其中则 （3）若 ca | ，则 .| cbab 反之，亦成立. （4）若 ||||,| baba 则 .因此，若 baabba 则又 ,|,| . （5） a 、b 互质，若 .|,|,| cabcbca 则 （6） p 为质数，若 ,| 21 naaap   则 p 必能整除 naaa ,,, 21  中的某一个. 特别地，若 p 为质数， .|,| apap n 则 （7）如在等式    m k k n i i ba 11 中除开某一项外，其余各项都是 c 的倍数，则这一项也是 c 的倍数. （8）n 个连续整数中有且只有一个是 n 的倍数. （9）任何 n 个连续整数之积一定是 n 的倍数. ww w. qb xt .c n 北京清北学堂教育科技有限公司 电话：010-88400806，010-88400903 网址：www.topschool.org 2 / 23 定理 1：设大于 1 的整数 a 的标准分解式为 1 21 2 1 2( n n na p p p p p p         为质数， i 均为非负整 数），则 a 的约数的个数为    n i iad 1 )1)( （ .所有的约数和为：       n i i i p p a i 1 1 1 1 )(   . 事实上，由算术基本定理的推论知    n i iad 1 )1()(  ，而各约数的和就是    n i ii i pap 1 )1(  展开后的各 项之和，所以        n i n i i ii p p ppa i i 1 1 1 1 1 )1()(    例如，25200=24·32·52·7，所以 90)11)(12)(12)(14()25200( d ， 99944 17 17 15 15 13 13 12 12 )25200( 2335              . 2、最大公约数和最小公倍数 定义 2：设 a 、b 是两个不全为 0 的整数.若整数 c 满足： bcac |,| ，则称 bac ,为 的公约数， ba与 的所有 公约数中的最大者称为 ba与 的最大公约数，记为 ),( ba .如果 ),( ba =1，则称 ba与 互质或互素. 定义 3：如果 ad是 、b 的倍数，则称 ad是 、b 的公倍数. ba与 的公倍数中最小的正数称为 ba与 的最小 公倍数，记为 ],[ ba . 最大公约数和最小公倍数的概念可以推广到有限多个整数的情形，并用 ),,,( 21 naaa  表示 naaa ,,, 21  的 最大公约数， ],,,[ 21 naaa  表示 naaa ,,, 21  的最小公倍数. 若 1),,,( 21 naaa  ，则称 naaaa