经金国中小学教材审定委员会 2005年初审通过 普通高中课程标准实验教科书 数学 选修4-6 初等数论初步 人民教育出版社课程教材研究所编著 中学数学课程教材研究开发中心 人AA 社 版
目录 引言………………………1 第一讲整数的整除 …………………2 整除 1.整除的概念和性质 2.带余除法 ……………4 3.素数及其判别法………………………5 习題………………………7 二最大公因数与最小公倍数 l,最大公因数……………"……8 2.最小公倍数……………………………11 习题……………………………………………13 三算术基本定理…………………………13 习题 14
第二讲同余与同余方程 15 同余 15 1.同余的概念…… …15 2同余的性质 17 习题 18 剩余类及其运算 18 习题 …22 三费马小定理和欧拉定理………22 习题 四一次同余方程 …25 1.一次同余方程…………… …25 2.大衍求一术…… ,,, ………26 习题 28 五拉格朗日插值法和孙子定理…………28 习题 …30 六弃九验算法…………………………31 习题 32 第三讲一次不定方程……………,33 二元一次不定方程 ………33 习题………36 二二元一次不定方程的特解 …36 习题 3 ………………38 0 多元一次不定方程 ………38 习题…………………………………40 第四讲数论在密码中的应用 信息的加密与去密……………………41 二大数分解和公开密钥…………………43 学习总结报告…………… 46 附录一剩余系和欧拉函数…… 47 附录二多项式的整除性 50
相0需 a32 22930 x引言 数论是研究整数的性质和方程的整数解的一门学科.它起源于古代的东方,距今大约 有3000年的历史 我国古代数学家在数论方面取得了一些重要成就《周髀算经》记载有西周人商高提 出的“勾广三,股修四,径隅五”的论断,它实际上给出了方程x2+y2=x2有一组正整数 解(3,4,5).《九章算术》记载有另外的四组正整数解:(5,12,13),(8,15,17), (7,24,25),(20,21,29).我国另一部重要数学著作《孙子算经》中记载有“物不知 数”问题:“今有物不知其数,三三数之余二,五五数之余三,七七数之余二,问物几 何?”答曰:“二十三”这一问题和它的解法一起被后人称为孙子定理(国外文献称之为 中国剩余定理) 我国古代的数论研究具有鲜明的直观、实用和算法特性.古希腊的数论研究则具有理 性的特点,其成就集中反映在两部数学著作中,一部是欧几里得的《几何原本》,它给出 了算术基本定理、素数有无限多个、辗转相除法等初等数论的重要结果;另一部是丢番图 的《算术》,这是历史上第一部脱离几何,完全讲述数论的著作,书中讨论了300多个数 论问题,列举了一些一次方程和二次方程的整数解的解法 数论是一门古老而又基础的数学分支,至今仍有许多没有解决的问题.这些数论问题 对人类智慧产生极大的挑战,人们为解决这些数论问题所作的贡献,对数论乃至整个数学 的发展起了重要的推动作用.一个典型的例子就是费马猜想的解决 1637年,法国数学家费马提出猜想:方程x+y=x没有正整数解,其中n为大于2 的整数.300多年来,许多专业数学家和业余数学爱好者为解决此猜想作了不懈的努力, 最终于1994年被英国数学家威尔斯(wles)解决.在费马猜想的研究过程中,人们创造 了研究数论的许多新方法,建立了数论的一些新分支,发现了它与数学其他领域的奇妙而 深刻的联系 当今的数论已经发展成为一门艰深的学问.而且,随着计算机技术和数字通信技术的 飞速发展,数论已经成为计算机科学和通信工程的重要数学工具之一 本专题中,同学们将通过具体的问题,学习有关整数和整除的知识,探索用辗转相除 法求解一次同余方程、一次同余方程组、简单的一次不定方程等,从中体会数论的基本思 想方法,同时了解我国古代数学的一些重要成就 ■■■1
a=bg,+r b=r,q:+7 =F,+F 2 g. tr ,=9 第饼 整数的整除 =“+(.2)=(0,n)= 我们知道,两个整数进行加法、减法、乘法运算,结果仍为整数.但是,两个整数相 除,不一定能除尽,也就是说,所得结果不一定为整数 给定非零整数n,如何找出所有除尽n的整数和被n除尽的整数;给定两个非零整数a 和b,如何找出所有同时除尽a,b的整数和同时被a,b除尽的整数.如果给定的是多个非 零整数,又该如何? 这些问题不仅有理论意义,而且还是后面解同余方程和不定方程的基础.要完整地回 答这些问题,我们需要学习整数的一些基本知识 整除 1.整除的概念和性质 思 如何从乘法角度判断一个整数能除尽另一个整数? 我们知道,乘法与除法是互逆的两种运算.要判断一个整数能否除尽另一个整数,只 需考察被除数能否写成除数和某个整数的乘积.只有当被除数可以表示为除数和某个整数 的乘积时,除数恰好能除尽被除数.此时,我们就说除数整除被除数,或者说被除数能被 除数整除 一般地,设a,b为整数,且b≠0.如果存在整数q,使得a=例,那么称b整除a 或者a能被b整除,记作b|a.井且称b是a的因数,a是b的倍数.如果这样的整数q 不存在,就称b不整除a,记作b{a 例如,61-24,-4156,-414,80 由此可知,能被非零整数n整除的整数是n的倍数,其一般形式为m,这里q为任意 格数.能除尽n的整数是n的因数,例如,能除尽6的整数为1,-1,2,-2,3,-3 6,-6 2