1、第六部分第六部分 初初 等等 数数 论论(elementary number theory) 黄志平物 光 学 院v 数论数论 是研究整数性质的一门很古老的数学分支，是研究整数性质的一门很古老的数学分支，其初等部分是以整数的整除性为中心的，包括其初等部分是以整数的整除性为中心的，包括 整除整除性、不定方程、同余式、连分数、素数性、不定方程、同余式、连分数、素数 (即整数即整数 )分分布以及数论函数布以及数论函数 等内容，统称初等数论。等内容，统称初等数论。初等数论的大部份内容早在古希腊初等数论的大部份内容早在古希腊 欧几里德欧几里德 的的 几几何原本何原本 中就已出现。欧几里得证明了素数有无穷
2、中就已出现。欧几里得证明了素数有无穷多个，他还给出求两个自然数的最大公约数的方法多个，他还给出求两个自然数的最大公约数的方法 ,即所谓欧几里得算法。即所谓欧几里得算法。我国古代在数论方面亦有杰出之贡献，现在一般数我国古代在数论方面亦有杰出之贡献，现在一般数论书中的论书中的 “中国剩余定理中国剩余定理 ”正是我国古代正是我国古代 孙子算经孙子算经 中的下卷第中的下卷第 26题，我国称之为题，我国称之为 “孙子定理孙子定理 ”。 近代初等数论近代初等数论 的发展得益于的发展得益于 费马、欧拉、拉格朗日费马、欧拉、拉格朗日、勒让德和高斯、勒让德和高斯 等人的工作。等人的工作。 1801年，高斯的年，
3、高斯的 算算术探究术探究 是数论的划时代杰作。高斯还提出：是数论的划时代杰作。高斯还提出： “数学数学是科学之王，数论是数学之王是科学之王，数论是数学之王 ”。可见高斯对数论的。可见高斯对数论的高度评价。高度评价。由于自由于自 20世纪以来引进了抽象数学和高等分析的巧世纪以来引进了抽象数学和高等分析的巧妙工具，数论得到进一步的发展，从而开阔了新的妙工具，数论得到进一步的发展，从而开阔了新的研究领域，出现了研究领域，出现了 代数数论、解析数论、几何数论代数数论、解析数论、几何数论等等 新分支。新分支。而且近年来而且近年来 初等数论初等数论 在在 计算器科学、组合数学、密计算器科学、组合数学、密码
4、学、代数编码、计算方法码学、代数编码、计算方法 等领域内更得到了等领域内更得到了 广泛广泛的应用，无疑同时促进着数论的发展。的应用，无疑同时促进着数论的发展。v 本课程介绍的内容包括本课程介绍的内容包括 : v 素数素数v 最大公约数与最小公倍数最大公约数与最小公倍数v 同余同余v 一次同余方程一次同余方程v 初等数论的几个应用初等数论的几个应用【 定义定义 】 设设 a,b是两个整数是两个整数 , 且且 b0, 如果存在整数如果存在整数 c使使 a=bc, 则称则称 a被被 b整数整数 , 或或 b整数整数 a, 记作记作 b|a 。又。又称称 a是是 b的的 倍数倍数 ， b是是 a的的
5、因子因子 。把把 b不整除不整除 a记作记作 b | a19.1 素数素数【 定义定义 】 设设 a, b是两个整数是两个整数 , 其中其中 b0 , 则存在惟一则存在惟一的整数的整数 q及及 r, 满足满足a=bq+r ， 0r1, p是素数且是素数且 d|p，则，则 d=p。【性质【性质 19.7】 设设 p素数且素数且 p|ab，则必有，则必有 p|a或或 p|b。更一般地，设更一般地，设 p是一个素数且是一个素数且 p|a1a2 ak, 则必存在则必存在1i k，使得，使得 p|ai。【性质【性质 19.8】 a1是合数当且仅当是合数当且仅当 a=bc, 其中其中11 则则 a能表成素
6、数能表成素数的乘积：的乘积：其中其中 是不同的素数，是不同的素数， 是正整数是正整数 ,且在且在 不计次序的意义下不计次序的意义下 ，表示上式是，表示上式是 惟一惟一 的。的。上式称为上式称为 整数整数 a的素因子分解的素因子分解 。【 例例 19.1】 (1)99099有多少个正因子？有多少个正因子？(2) 20的二进制表示中从最低位数起有多的二进制表示中从最低位数起有多少个连续的少个连续的 0.【 定理定理 19.2】 有无穷多个素数。有无穷多个素数。显然显然 , a的因子只能含有的因子只能含有 a中的素因子中的素因子 , 即可下述推论：即可下述推论：【 推论推论 】 设设 , 其中其中 是不是不 同的素数，同的素数， 是正整数是正整数 , 则正整数则正整数 d为为 a的因的因子的充分必要条件是子的充分必要条件是 ,其中其中 。 用反证法证明用反证法证明记记 为为 小于或等于小于或等于 n的素数个数的素数个数 。例如：例如： 【 定理定理 19.3】 (素数定理素数定理 )168 1229 9592 78498 664579145 1086 8686 72382 6204211.159 1.132 1.104 1.085 1.071
