经金国中小学教材审定委员会 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
第一讲整数的整除 第一拼 /编 日里BB 由整除的概念,你能否推出下列整除的基本性质? (1)若a|b,b|a,则a=b,或a=-b. (2)若a|b,bc,则alc. (3)若a|b,alc,则对任意整数x,y,恒有albx+cy. 如何判断一个非零整数整除给定的正整数?对某些特殊的非零整数,我们可以通过观 察发现一些简单的判别方法 给定两组正整数: 第一组6,18, 第二组5,17, 2 54,81,96,108,243 80,85, ,121,212 第一组数有什么规律?它们能被什么整数整除?第二组数呢?计算每组数的各位 数字之和,你能发现什么特征? 观察发现,第一组数能被3整除,并且其中每一个数的各位数字之和都能被3整除; 第二组数不能被3整除,并且其中每一个数的各位数字之和也不能被3整除 由此,我们猜想: (1)一个正整数的各位数字之和能被3整除,那么这个正整数能被3整除 这个命题是否正确?我们证明一下 下面仅对4位正整数情形给出证明,同学们可以类比证明一般的情形. 证明:设N为4位正整数,且它的个、十、百和千位数字依次为a,b,c,d,则 N=d×103+c×102+b×10+a =d×(999+1)+cX(99+1)+b×(9+1)+a =999d+99c+9b+d+c+b+a. 因为3|9994+99+9,所以,当3|d+c+b+a时,3|N 请用类似的方法证明能被9,11,7整除的正整数的下列特征; (2)一个正整数的各位数字之和能被9整除,那么这个正整数能被9整除; (3)一个正整数的奇数位数字之和与偶数位数字之和的差能被11整除,那么这 个正整数能被11整除; (4)一个正整数的末三位数字组成的数与末三位数字之前的数字组成的数之差能 被7(或11)整除,那么这个正整数能被7(或11)整除 aaenaneene.aaaa.a.a果多 ■■3
CHAPTER 逝高中课程标准实验教科书数学(选修46)初等数论沦初步 例1判断710316能否被9,11整除 解:因为7+1+0+3+1+6=18能被9整除,所以710316能被9整除 又因为710316的奇数位数字之和为6+3+1=10,偶数位数字之和为1+0+7=8,而 1ω一8=2不能被11整除,所以710316不能被11整除 2.带余除法 我们知道,14÷3的商为4,余数为2,即14= 3×↓+2,这种表示法在整数集中仍然成立,我们把 它叫做带余除法(或欧氏除法算式) 一般地,设a,b为整数,且b≠0,则存在惟 一的一对整数q和r,使得 a=+r,0≤r0的情形), 古希腊的数论成就集中 由于b的倍数在数轴上是等距分布的,而且相邻两个 反映在欧几里得的几何《原 本》一书中,全书共13卷, 倍数之间的距离为b,而a是数轴上的一点,那 其中5卷讲数论,主要包括 么它一定落在b的两个相邻倍数之间.此时,将紧邻欧氏除法算式,算术基本定 a的左侧b的倍数记作加,选取r为a与的距离, 理、素数有无限多个等 此时a=例+r(从数轴上可以直观地看出).这就说 明了满足上述等式的整数q和r是存在的 gb a(g+IM 图1-1 下面说明q和r是惟一的,如果整数对q和r也满足 a=q+r,0≤r<|b|, 那么a=b+r=b(+r,即r-r=b(q- 于是b|(x-r),而一1b<r-r<1b 因此,r-P=0,即r=r,从而q=q 所以,q和r是惟一的 我们把带余除法中惟一的q和r分别叫做a除以b的商和余数.显然,a能被b整除当 且仅当余数r=0 例22004除以某个整数,其商为74,求除数和余数 解:设除数为b,余数为r,则 2004=74b+r,0≤r<b
第一讲整数的除 第一 由此可得 74≤20041,所以p为合数,那么p必然有1,p以外的正因数q,使得q1p.因为 0[x]通常叫做取整函数(或高斯函数),它是数论中一个常见的函数,具有许多有趣的性质 5
CHAPTER 菩通高中课程标准实验教科书数学(选修46)初等数论初步 p|n,所以q|n,于是q是n的除1,p以外且小于p的正因数,这与已知矛盾,故最小 正因数p是一个素数.一般地,任何大于1的整数,总存在一个素数因数.通常,把一个 正整数的素数因数叫做它的素因数 是否总可将任何大于1的整数n分解为一些素数的乘积? 对大于1的整数n,如果n不是素数,我们可以将n分解为一个素数和某个大于1的整 数a的乘积,如果a是一个素数,则过程停止.否则,又可将a分解为一个素数和某个大于 1的整数b的乘积对b又分两种情形:若b为素数,则过程停止;若b不是素数,则将b继 续分解为一个素数和某个大于1的整数c的乘积如此进行下去,直到过程停止,最后总可 将n分解为一些素数的乘积.例如,12=2×2×3,78=2×3×13. 既然任何大于1的整数n总可分解为一些素数的乘积,那么素数有多少个?有限还是 无限?为什么? 我们不妨假设素数有有限个,即m,m2,m,…,m,记这 k个素数的乘积为N,即 欧几里得证 N=mm2m… 明素数有无穷多 个这个命题时使 由此可知,任意一个素数m(i=1,2,…k)都整除N,但不能整m了反证法,这 除N+1.又由于N+1为大于1的正整数,所以它一定能被某个素是数学上第一批 数整除,这就产生了矛盾.因此,假设素数有有限个是错误的,素 使用反证法的命 题 数有无穷多个 对给定的大于1的正整数,如何判断它是不是素数呢?例如,要判断61 是不是素数,是否需要用2~60之间的数一一试除61呢? s,.·.·,,,,,···,·····.········.···.,·······,,·,··· 没有必要.因为2不是61的因数,那么2的倍数也不是61的因数.同样地,若3不 是6的因数,那么3的倍数也不是6的因数.这就是说只需用2~60之间的素数试除61 即可 另一方面,如果61是合数,那么它一定可以表示成两个大于1的正因数的乘积,其 中较小的一个正因数一定不超过√61,并且它的素因数也是61的素因数.这就是说,如果 61是合数,那么它一定存在不超过√61的素因数 因此只需用2~60之间不超过√61的素数试除6即可 不超过√61的素数为2,3,5,7,由于它们都不整除61,所以6是素数
第一讲整数的整除 算一拼 般地,我们有下面的判别法: 如果大于1的整数a不能被所有不超过a的素数整除,那么a一定是素数 这个判别法实际上给出了一种寻找素数的有效方法 例3找出1-100中的全部素数 解:只需把1与1~100之间的合数去掉即可.而对于1~100之间的每个合数a,它 定能被某个不超过a的素数整除,从而能被不超过√100=10的素数整除。我们知道, 不超过10的素数为2,3,5,7.在1-100中首先去掉1,然后分别去掉2.3.5,7除自 身以外的倍数,最后剩下的数就是不超过100的全部素数.具体做法如下表: 2 9 T0 tR 19 点26 3132333437389 43本 4526 47 5525354555585960 61 46 676867Q 7177K7双787980 83 5868788900 9头 97 Q 因此不超过100的素数为2,3,5,7,11,13,17,19,23,29,31,37.41.43, 47,3,59,61,67,7,73,79,83,89.97,共25个.这种寻找素数的方法叫做埃 拉托斯特尼( Eratosthenes)筛法 1.判断下列整数中哪些能分别被3,7,9,11整除 45,98,120,189,1001,1331,56382. 2.探究并证明能被11整除的5住正整数的特征 3.已知1626除以某个整数,其商为81,求除数与余数 4.判断343,2027是素数还是合数