初等数论1——整除性.doc

高一·联赛班·第4讲·学生版

高一·联赛班·第4讲·学生版

第四讲初等数论1——整除性
本讲概述
数论是数学中极其重要又非常迷人的一个分支，目前我们仅学习初等数论中较浅的内容.
初等数论是数学竞赛四大模块中较难以掌握的模块之一，在数学竞赛中占据极其重要的位置.特别是联赛改制以后，二试必考一道50分的数论大题，一试也会有一到两道数论方面的问题.数论与组合水平如何是大家能否获得联赛一等奖甚至更好成绩的关键.
初等数论这块的竞赛问题涉及到的知识点极少，甚至可以说绝大部分同学在小学初中的培训中基本都接触过.但是限于初中的知识面和同学的年龄，考试中一般不出现较为深入、难度较高的数论问题.到了高中，大家将复习小学初中阶段的数论知识，并将其中的很多知识更为理论化、系统化.高中的数论问题难度也会明显增高.但是在数论这一模块中，我们并不提倡大家过多地掌握很多高深的数论知识，而是提倡大家真正去灵活熟练地运用最基本、最重要的数论基础知识和重要定理来解决问题.
由于同学们在小学、初中都已经学过不少关于初等数论的初步知识，所以这里我们把大家比较熟悉的知识都罗列在下面，对其中大部分定理将不给出证明，直接给出结论.
如果不特别说明，本讲中所有字母均代表正整数.
一、整除
1．整除的定义
两个整数a和b(b≠0)，若存在整数k，使得a=bk，我们称a能被b整除，记作b|a．此时把a叫做b的倍数，b叫做a的约数．如果a除以b的余数不为零，则称a不能被b整除，或b不整除a，记作．
2．数的整除特征
（1）1与0的特性：
1是任何整数的约数，即对于任何整数a，总有1|a．
0是任何非零整数的倍数，a≠0，a为整数，则a|0．
（2）能被2，5；4，25；8，125；3，9；11，7，13整除的数的特征：
能被2整除的数的特征：个位为0，2，4，6，8的整数能被2整除，我们记为2k(k为整数)．
能被5整除的数的特征：个位数为0或5的整数必被5整除，我们记为5k(k为整数)．
能被4、25整除的数的特征：末两位数字组成的两位数能被4（25）整除的整数必能被4（25）整除．
能被8，125整除的数的特征：末三位数字组成的三位数能被8（125）整除的整数必能被8（125）整除．
能被3，9整除的数的特征：各个数位上数字之和能被3或9整除的整数必能被3或9整除．
能被11整除的数的特征：一个整数的奇数位数字之和与偶数位数字之和的差如果是11的倍数，则这个数就能被11整除．
能被7，11，13整除的数的特征：一个三位以上的整数能否被7（11或13）整除，只须看这个数的末三位数字表示的三位数与末三位以前的数字组成的数的差（以大减小）能否被7（11或13）整除．
3．整除的几条性质
（1）自反性：a|a(a≠0)
（2）对称性：若a|b,b|a，则a=b
（3）传递性：若a|b,b|c，则a|c
（4）若a|b,a|c，则a|(b,c)
（5）若a|b,m≠0，则am|bm
（6）若am|bm,m≠0，则a|b
（7）若a|b,c|b,(a,c)=1，则ac|b
二、带余除法
对于任一整数a及大于1的整数m，存在唯一的一对整数q,r(0≤r<m)，使得a=qm+r成立，这个式子称为带余除法式。q就是a除以m的不完全商，r就是a除以m的余数。
证明：取由所有m的整数倍排成一列数
…,－km,…,－2m,－m,0,m,2m,…,km,…(k∈N)
a必介于该数列中的某两个相邻数之间，即存在整数q，使qm≤a<(q+1)m。
令r=a－qm，则0≤r<m，于是有a=qm+r
如还有整数q1,r1满足a=q1m+r1(0≤r1<m)，则
q1m+r1=qm+rm(q1－q)=r－r1
若q1≠q，则|m(q1－q)|≥m，而|r－r1|<m，这是不可能的.
这说明q1=q,于是r1=r。

三、基本定义：奇数、偶数、素数、合数、最大公约数、最小公倍数、完全平方数、阶乘
1、将全体整数分为两类，凡是2的倍数的数称为偶数，否则称为奇数.因此，任一偶数可表为2m（m∈Z），任一奇数可表为2m+1或2m－1的形式.奇、偶数具有如下性质：
（1）奇数±奇数=偶数；偶数±偶数=偶数；
奇数±偶数=奇数；偶数×偶数=偶数；
奇数×偶数=偶数；奇数×奇数=奇数；
（2）任何一个正整数n，都可以写成的形式，其中m为非负整数，l为奇数.
2、一个大于1的整数n如果没有真因子（大于1而小于n的约数），则称n为素数；否则称它为合数.
素数的性质1：若p为素数，a,b为整数,如p|ab,那么p必整除a,b之一.
素数的性质2：素数有无穷多个.(欧几里得在公元3世纪给出了一个经典的利用反证法的证明)
3、设a,b,…,c是有限个不全为零的整数，同时整除它们的整数叫做