因而a个余数r0, r1, , ra1仅可能取a 1个值， 因此其中必有两个相等。
设为ri，rk，不妨设0 i k a，因而有 a(qk qi ) 2k 2i 2i (2ki 1)
因而a个余数r0, r1, , ra1仅可能取a 1个值， 因此其中必有两个相等。
• 我国近代：在解析数论、丢番图方程，一致分布 等方面有过重要贡献，出现了华罗庚、闵嗣鹤等 一流的数论专家，其中华罗庚在三角和估值、堆 砌素数论方面的研究享有盛名。
• 特别是在“篩法”、歌德巴赫猜想方面的研究， 已取得世界领先的优异成绩。陈景潤在1966年证 明歌德巴赫猜想方面证明了”1+2”(一个大偶数可 以表示为一个素数和一个不超过两个素数的乘积 之和)
m|aq
3、带余数除法
带余数除法的第二种表示 定理4 若a,b是两个整数，其中b 0，则存在着两个整数 q及r，使得 a bq r， 0 r b 成立，而且q及r是唯一的。
证明分析：作整数序列 ，-3 b ,-2 b ,- b ,0,b ,2 b ,3 b ,
则a必满足q b a<(q+1) b , 其中q Z , 令a q b r可得到a b q r,分b 0和 b 0来讨论q, 进一步证明q, r的唯一性。
(i)若在r1, , r5中数0，1，2都出现，不妨设
r1 0, r2 1, r3 2，
此时
a1 a2 a3 3(q1 q2 q3 ) 3
可以被3整除。
(ii)若在r1, , r5中数0，1，2至少有一个不出现，
这样至少有3个ri要取相同的值，不妨设
r1 r2 r3 r(r 0,1或2），
近代初等数论的发展得益於费马、欧拉、拉格朗日、 勒让德和高斯等人的工作。1801年，德国数学家高斯集 中前人的大成，写了一本书叫做《算术探究》，开始了 现代数论的新纪元。高斯还提出：“数学是科学之王， 数论是数学之王”。
由于自20世纪以来引进了抽象数学和高等分析的 巧妙工具，数论得到进一步的发展，从而开阔了新 的研究领域，出现了代数数论、解析数论、几何数 论等新分支。而且近年来初等数论在计算机科学、 组合数学、密码学、代数编码、计算方法等领域内 更得到了 广泛的应用，无疑同时也促进着数论的发 展。
带余数除法的第三种表示（课后习题）
定理4 若a,b是两个整数，其中b 0，则存在着两个整数
q及r，使得
a bq r，
b r
2
成立，而且当b是奇数时，q及r是唯一的；当b是偶数时，q及r
有可能是不唯一的。
例 当a 5, b 2时，可有 5 （ 2）（ 3）（1），即q 3, r 1; 或5 （ 2）（ 2）1，即q 2, r 1
rn1 0。
定理4 若a,b是任意两个正整数，则(a,b) rn ， rn是上式中最后一个不等于零的余数。
推论4.1 a,b的公因数与(a,b)的因数相同。
例1、a 1859,b 1573,求(1859,1573)
ቤተ መጻሕፍቲ ባይዱ
6、最大公因数的两个性质
定理5 设 a,b,是任意两个不全为零的整数，
其中q是非零整数，则a,b与b,c有相同的公因数， 因而(a,b)=(b,c)
思考：1、d|a,d|c时能否推出d|b?
5、下面要介绍一个计算最大公约数的算法——辗转 相除法，又称Euclid算法。它是数论中的一个重要 方法，在其他数学分支中也有广泛的应用。 定义 下面的一组带余数除法，称为辗转相除法。
设a,b是整数，b 0，依次做带余数除法
a bq1 r1，0 r1 b， b r1q2 r2，0 r2 r1，
rk 1 rk qk 1 rk 1，0 rk 1 rk ，
rn 2
rn1qn rn，0
rn

rn
，
1
rn1 rnqn 1 +rn1,
一个大于6的偶数可以表示为不同的两个质数之和。
陈景润在1966年证明了“哥德巴赫猜想”的“一个大 偶数可以表示为一个素数和一个不超过两个素数的乘 积之和”〔所谓的1+2〕，是筛法的光辉顶点，至今仍 是“哥德巴赫猜想”的最好结果。
2、费尔马大定理： 费马是十七世纪最卓越的数学家之一，他在数学 许多领域中都有极大的贡献，因为他的本行是专业的 律师，世人冠以“业余王子”之美称。在三百七十多 年前的某一天，费马正在阅读一本古希腊数学家戴奥 芬多斯的数学书时，突然心血来潮在书页的空白处， 写下一个看起来很简单的定理。
证明分析：作序列
，- 3 b ,- 2 b ,- b ,0, b ,2 b ,3 b , 2 2 2 22 2
则a必满足q b a<(q+1) b , 其中q Z,
2
2
分q为偶数时b 0和b 0；q为偶数时b 0和
b 0来讨论q及r的存在性, 进一步证明q, r的唯一性。
例1 求当b=15时, a取下列数值时的不完全 商和余数.
二 数论的发展
自古以来，数学家对于整数性质的研究一直十分重 视，初等数论的大部份内容早在古希腊欧几里德的《几 何原本》（公元前3世纪）中就已出现。欧几里得证明了 素数有无穷多个，他还给出求两个自然数的最大公约数 的方法，即所谓欧几里得算法。我国古代在数论方面亦 有杰出之贡献，现在一般数论书中的“中国剩余定理”， 正是我国古代《孙子算经》中的下卷第26题，我国称之 为孙子定理。
第一节 整除的概念 带余数除法
如果不存在整数q使得a bq成立，则称a不被b整除， 记为b † a。
2、整除的基本定理
思考：逆命题是否成立？ 1、m|(a±b) →m|a,m|b 2、m|(a±b) ，m|a→m|b
定理2’ m | a, m | (a b) m | b
特例：m||a
此时
a1 a2 a3 3(q1 q2 q3 ) 3r
可以被3整除。
例3、设a 1为奇数，证明： 存在正整数d a 1,使得a 2d 1
证：考虑下面的a个数： 20, 21, , 2a1，显然a不整除2 j (0 j a)，
由带余除法，对每个2 j (0 j a)， 2 j q ja rj , (0 rj a)
若 2n 1 是素数，则 2n1(2n 1) 是完全数
注意以上谈到的完全数都是偶完全数,至今仍 然不知道有没有奇完全数。
四、初等数论在中小学教育中的作用
• 在培养中学生思维能力方面大有作用。
国际数学奥林匹克从1959年起到2002 年已经举行了43届比赛，大致统计， 在总共260道题目中，可以主要用初等 数论知识来解及初等数论知识有关的 约有82题，约占31.5%。
三、几个著名数论难题
初等数论是研究整数性质的一门学科，历史上遗 留下来没有解决的大多数数论难题其问题本身容易 搞懂，容易引起人的兴趣，但是解决它们却非常困 难。
其中，非常著名的问题有：哥德巴赫猜想 ； 费尔马大定理 ；孪生素数问题 ；完全数问题等。
1、哥德巴赫猜想：
1742年,由德国中学教师哥德巴赫在教学中首先发现 的。1742年6月7日，哥德巴赫写信给当时的大数学家 欧拉,正式提出了以下的猜想：
方程 xn yn zn (n 3) 无非0整数解
经过8年的努力，英国数学家 安德鲁·怀尔斯 终 于在1995年完成了该定理的证明。
3、孪生素数问题
存在无穷多个素数 p, 使得 p+2 也是素数。
究竟谁最早明确提出这一猜想已无法考证，但是 1849年法国数学家 Alphonse de Polignac 提出猜想：
于是我们有
例2、证明：若n是正整数，则 21n 4 是既约分数。 14n 3
证明：因为（21n 4,14n 3) (7n 1,14n 3)
(7n 1,7n 2) (7n 1,1) 1
所以，命题得证。
第三节 整除的进一步性质及最小公倍数
第二节习题第二题要求证明(a,b) ax0 by0 成立，其中的x0和y0与a, b的关系如何？ 进一步，辗转相除法中任意rk 与a, b的关系又如何？
1、a=81; 2、a=-81;
• 例2(1)一个数除以2,余数可能为
,
所有的整数按被2除所得的余数分类可分
为
.
• (2)一个数除以3,余数可能为
,所有
的整数按被3除所得的余数分类可分为
.
• (3) 一 个 数 除 以 正 整 数 b, 余 数 可 能
为
,所有的整数按被b除所得的余
数分类可分为
.
带余数除法的应用举例
设为ri，rk，不妨设0 i k a，因而有 a(qk qi ) 2k 2i 2i (2ki 1)
则有 a 2ki 1，取d k i a 1，则d就满足要求。
例4
例6
第二节 最大公因数与辗转相除法
1、定义 设a1 , a2, , an是n(n 2)个整数，若整数d是 它们之中每一个的因数，那么d就叫作a1, a2, , an的一个 公因数。所有公因数中最大的一个叫最大公因数，记作 （a1, a2 , , an），若（a1, a2, , an）=1，则说a1, a2, , an互质 或互素。
第一章 整数的可除性
一 初等数论及其主要内容
数论是研究整数性质的一门很古老的数学分支， 其初等部分是以整数的整除性为中心的，包括整除 性、不定方程、同余式、连分数、素数（即质数） 分布 以及数论函数等内容，统称初等数论
（elementary number theory） 。
初等数论是数论中不求助于其他数学学科的帮助， 只依靠初等的方法来研究整数性质的分支。
4、最完美的数——完全数问题