“初等数论初步”简介.doc

“初等数论初步”简介 初等数论是研究整数的性质和不定方程（组）的整数解的一门学问，它与几何学是最古老的两个数学分支。初等数论中至今仍有许多没有解决的问题，如哥德巴赫（Goldbach）问题，孪生素数猜想，奇完全数的存在性问题等，它们对人类智慧产生了极大挑战。人们在解决一些初等数论问题的过程中所作的贡献，对数论乃至整个数学的发展起了重要的推动作用，产生了一些直接与数学有关的新的重要数学分支。初等数论在计算机科学和信息工程中有许多重大的实际应用。在本专题中，同学们将通过具体的问题，学习初等数论的一些基本知识，如有关整数和整除的知识，用辗转相除法求解一次同余方程（组）和简单的一次不定方程等，初等数论中蕴含的一些思想方法，以及我国古代数学在初等数论的研究方面取得的一些重要成就。一、内容与课程学习目标本专题的学习初等数论的一些基本知识，具体包括：整数的整除、同余与同余方程、一次不定方程和数论在密码中的应用四部分内容。通过本专题的学习，要引导学生：1通过实例，认识带余除法，理解同余和剩余类的概念及意义，探索剩余类的运算性质（加法和乘法），并且理解它的实际意义。体会剩余类运算与传统数的运算的异同（会出现零因子）。2理解整除、因数和素数的概念，了解确定素数的方法,如埃拉托斯特尼（Eratoshenes）筛法，知道素数有无穷多个。3了解十进制表示的整数的整除判别法，探索整数能被3，9，11，7等整除的判别法。会检查整数加法、乘法运算错误的一种方法,如弃九验算法。4通过实例，探索利用辗转相除法求两个整数的最大公约数的方法，理解互素的概念，并能用辗转相除法证明：若a能整除bc，且a,b互素，则a能整除c。探索公因数和公倍数的性质。了解算术基本定理。5通过实例，理解一次不定方程的模型，利用辗转相除法求解简单的一次不定方程。并尝试写出算法的程序框图，在条件允许的情况下上机实现。6通过实例（如物不知其数问题），理解一次同余方程组的模型。7理解大衍求一术和孙子定理的证明。8理解费马小定理（当m是素数时，am-11(mod m)）和欧拉定理（a(m)1(mod m),其中(m)是1，2，m-1中与m互素的数的个数）及其证明。9了解数论在密码中的应用公开密钥。二、内容安排本专题共安排了四讲，其中最后一讲“数论在密码中的应用”可根据教学时间的实际情况机动安排，可由教师讲授，也可作为学生课后的阅读材料。本专题教学时间约需18课时，具体分配如下（仅供参考）：第一讲 整数的整除 约5课时一、整除的概念和性质 约2课时二、最大公因数与最小公倍数 约2课时三、算术基本定理 约1课时第二讲同余与同余方程 约7课时一、同余 约1课时二、剩余类及其运算约2课时三、费马小定理和欧拉定理约1.5课时四、一次同余方程 约1课时五、拉格朗日插值法和孙子定理 约1课时六、弃九验算法约0.5课时第三讲一次不定方程 约3课时一、二元一次不定方程约1课时二、二元一次不定方程的特解 约1课时三、多元一次不定方程 约1课时第四讲数论在密码中的应用 约2课时一、信息的加密与去密 约1课时二、大数分解和公开密约约1课时学习总结报告 约1课时本专题的知识结构如下：1初等数论中有许多知识和问题是比较通俗易懂的。许多学生在小学就学习了整数的分解、素数和整除性的简单知识。少数学生在中学阶段为参加数学竞赛的需要，通过课外活动进一步学习了同余和不定方程的初步知识。但是，初等数论中不少问题，说起来容易，做起来很难。因此，有些教师和学生可能认为本专题的学习太难，不愿意去教和学。事实上，本专题学习的目的不是训练学生去做初等数论的难题，为数学竞赛服务，而是介绍初等数论中最基本的概念、方法和思想，使学生对初等数论及其应用有一个初步的认识，通过介绍初等数论的一些历史背景知识（如历史人物和历史名题），开阔学生的眼界，同时了解我国古代数学家在初等数学研究方面取得的一些重要成就，增强民族自豪感。2整数的整除理论是初等数论的基础，其中心内容是最大公因数与最小公倍数理论，最基本、最重要的结果是算术基本定理。带余除法是建立整数的整除理论的一个重要工具。辗转相除法（也称Euclid算法）是初等数论中最重要的方法之一，它由有限次带余除法构成，利用它不仅可以证明最大公因数的如下重要性质： （a, b）= ax + by， 还可以给出最大公因数（a, b）和x, y的有效算法。利用上式，我们可以证明整除的许多重要性质。在本专题后面求解一次同余方程和简单的一次不定方程时，我们经常要用到辗转相除法。算术基本定理是初等数论的基石，它表明素数是正整数最基本的构成单位。利用算术基本定理，我们可以研究整数的许多重要性质。多项式整除的方法和性质与整数整除的方法和性质完全平行，我们将这部分内容在附录中列出，供学生了解。3同余理论是初等数论的核心内容，它是由德国数学家高斯（Gauss）首先提出并系统地进行研究的。同余理论中蕴含大量的数论所特有的思想、概念和方法，它的出现是数论成为一个独立的数学分支的标志。同余、剩余类的概念与性质，以及一次同余方程式同余理论的基本知识，费马（Fermat）小定理和欧拉（Euler）定理是同余理论的两个重要结果，在简化计算和密码学等方面有重要的应用。我国古代数学家在一次同余方程求解方面取得了许多重要成就，比较典型问题如“物不知其数问题”、“韩信点兵问题”，重要方法和结论有“大衍求一术”和“孙子定理”（也称中国剩余定理），这些历史背景知识是学生应当了解的，并且有助于增强学生的民族自豪感和自信心。建立孙子定理的先特解而后求通解的想法与建立拉格郎日（Lagrange）插值公式是一样的，所以在教材中列入了建立朗格朗日插值公式的内容，有助于学生加强有关内容联系的意识。事实上，在学生的后续学习中，经常会用到这种思想方法。作为同余性质的简单应用，我们以乘法为例介绍了检查整数运算错误的一种方法，即弃九验算法。在同余理论中，剩余类的概念和运算是非常抽象的，但它是近世代数中一个很重要的数学模型。剩余类的运算与传统数的运算有许多类似的地方，但也要注意它们之间的区别，我们在教材中通过一些具体的例子来说明这一点。欧拉函数(m)是初等数论中的重要函数之一，在欧拉定理的证明和本专题最后一部分“数论在密码中的应用”要用到欧拉函数的表达式，由于其推导较复杂，要用到剩余系的知识，而正文中其它地方并不涉及，我们将相关内容在附录中列出。5不定方程是初等数论最古老的一个分支，我国古代数学家对不定方程进行了大量的研究。在公元前1100多年，我国古代数学家商高就提出了“勾广三、股修四、径隅五”的著名论断，它实际上给出了一个三边的长均为整数的直角三角形。大约1500年以前，我国古代的另一位数学家张丘建在他编写的张丘建算经里提出并求解了“百钱买百鸡”问题。教材中只讨论了最简单的不定方程一次不定方程（组），这类不定方程（组）可以用前面介绍的整数的整除理论（辗转向除法）和同余理论（大衍求一术）来求解。教材上首先介绍二元一次不定方程的求解，用的也是先特解而后通解的想法，然后将三元和四元一次不定方程的求解问题转化为多次求解二元一次不定方程的问题。为了得到较复杂的二元一次不定方程的特解，教材介绍了一种有效算法，即辗转相除法，并给出了相应的算法程序框图，供有条件的学校选用。需要注意的是，一次同余方程（组）也可以转化为一次不定方程（组）进行求解，如著名的“物不知其数问题”，为此教材安排了一道这方面的习题，有助于学生加强有关知识的联系。6初等数论的应用非常广泛，现实生活和生产实践中的许多问题的变量是整数甚至是正整数。有些问题归结为求不定方程的整数解或正整数解，有些问题归结为求一些方程或不等式的整数解，并且在所有的整数解中找出最佳解，等等。特别是20世纪后期计算机科学和通信技术的飞速发展，数论已经成为密码学的重要工具之一。作为数论在密码学中的一个应用，教材主要介绍了信息加密传送的一些简单模型和基本原理，以及欧拉定理在公开密钥体制中的应用。安排本节内容的目的是要让学生体验初等数论与日常生活和其他学科的联系，体会初等数论的价值和作用，增强应用意识，同时还可以加深学生对有关知识的理解。三、编写中考虑的几个问题1内容简明扼要，避免过多的符号推演本专题选取了初等数论中最基本、最重要的内容进行介绍，如整除的概念与性质，带余除法，最大公因数与最小公倍数，辗转相除法，算术基本定理，同余的概念与性质，费马小定理和欧拉定理，一次同余方程（组）的求解，一次不定方程（组）等，它们在初等数论中的地位与重要性，我们在前面已经阐述。一般来说，这些内容是学生学习初等数论时必须掌握或了解的。在具体内容的安排上，我们也做了细致的处理。如最大公因数与最小公倍数的性质与计算，我们只考虑两个整数的情形。对于三个整数的最大公因数与最小公倍数的计算问题，通过探究问题总结出结论。对于多于三个整数的情形，教材只是指出类似结果成立，不做叙述和推证。最大公因数的性质众多，教材只介绍其中几个最基本的性质。对于后面的一次不定方程，我们也作了类似的处理，以二元一次不定方程的求解为主，至于多元一次不定方程以三元和四元一次不定方程为例进行说明。算术基本定理的证明分解成了两部分，一部分（分解式的存在性）在素数及其判定部分给出，另一部分（分解式的惟一性）在叙述完算术基本定理后直接给出。在费马小定理和欧拉定理的证明中，没有涉及到剩余系的概念及其性质，降低学生认知的难度。内容的表达尽可能地采用文字语言的形式，尽可能地避免抽象的符号运算与推理。2穿插有关历史背景知识，开阔学生视野本专题无论是在引言中还是在后面各讲中，我们结合教材的具体内容，在正文或旁注中介绍初等数论发展史上一些重要的历史事件、人物和他们的重要成就。例如，费马猜想的提出与解决、欧几里得与几何原本、欧几里德算法、高斯与同余、费马和欧拉的数学成就、秦九韶和大衍求一术、程大位与“物不知其数问题”的算法口诀、张丘建与“百钱买百鸡”问题、丢番图方程等，这些内容不仅可以开阔学生视野，还有助于学生了解我国古代数学家在初等数论研究方面取得的重要成就，增强学生的民族自豪感和自信心。同时，这些内容可增加教材的可读性和亲和力。3强调从特殊到一般地引入新知识本专题在介绍新概念、新结论和新方法之前，通常先让学生观察、思考、探究具体的实例，让学生获得一些感性认识后，再逐步上升到理性认识，最后通过例题和练习进行巩固，而不是像许多大学初等数论教材那样定义、定理的罗列和不加分析的给出定理的证明。这样有助于降低学生的认知难度，提高学生自主学习的积极性。例如，通过考察正整数正因数的个数引入素数的概念；通过观察月历表中同一列整数被7除后的余数的特征，引出同余的概念。又如，通过考察一些特殊的模n（n为素数）的剩余类环中乘法运算的规律，归纳、猜想出费马小定理的结论，然后给出证明。这种由特殊到一般的认识引入方式，既符合知识产生的历程，也符合学生的认识规律，对于培养学生提出问题的意识和归纳概括的能力都是有益的。4通过问题引导学生主动思维为了引导学生主动思考，本专题利用“观察”“思考”“探究”等栏目设置了大量的问题。有些问题在内容上起着承上启下的作用。例如，在获得“任何大于1的整数，总存在一个素数因数”的结论后，提出“是否总可将每个大于1的整数分解为一些素数的乘积？”；在介绍了同余的概念后，提出同余和整除的关系；在获得二元一次不定方程ax+by=c有解的必要条件为“(a, b) | c”后，该条件是否充分的问题，等等。有些问题是可以直接类比或经过简单推理就可以得出的结论。例如，在证明了能被3整除的正整数的特征后，将能被9，11，7整除的正整数的特征留给学生探究。在得到三元一次不定方程有整数解的充分必要条件后，将四元一次不定方程有解的充分必要条件留给学生探究等。总之，本专题通过知识的发生发展过程来自然地提出问题，引导学生层层深入地进行思考，可以使学生得到思维方法上的训练。5多种数学研究方法合理使用。结合教材的具体内容，我们灵活运用从特殊到一般、类比、联系、推广等多种数学研究的常用方法。如引入新概念、新方法、新结论时，教材经常运用从特殊到一般的思想方法；在考察同余的性质时，运用类比的思想方法（与等式进行类比、联系）；在推导孙子定理时，我们既运用了从特殊到一般的思想方法，又运用了类比的思想方法（与拉格朗日插值公式建立过程类比、联系）；剩余类的运算与数的运算进行类比。另外，教材中的许多结论可以推广到一般情形，如最大公因数与最小公倍数的性质，拉格郎日插值公式与孙子定理，二元一次不定方程的可解条件和解法等，但教材主要考虑最基本的情形，目的是让学生更好的体验问题解决的过程，以及问题解决过程中所蕴含的数学思想方法，所以这些推广情形有的直接指出，有的留作学生探究。5适当使用信息技术根据新课标的要求，本专题可适当地运用信息技术。事实上，在初等数论中，许多问题都可以借助信息技术工具处理，如素数的判定，辗转相除法的应用等。教材中主要选取了如下两个方面：一是运用辗转相除法求两个整数的最大公因数，二是运用辗转相除法求二元一次不定方程的特解。这是因为，它们的操作过程非常明确、具体，具有鲜明的算法特点，而且又可以突出信息技术处理这类初等数论问题的优势。但是，考虑到我国各地在教学中使用信息技术的不平衡性，大多数学校实现起来有一定难度，所以教材上在信息技术的使用上作了弹性处理，如教材中已经用近似于计算机程序的语言写出了算法程序框图，对编写程序并上计算机实现列入学生的探究活动。四、对教学的几个建议1准确地把握教学要求初等数论中有些问题看起来很容易，但要真正地解决它们很难。所以教师在教学时一定要根据新课标准确地把握好教学要求，不要把本专题的学习视为对数学竞赛中数论相关知识的培训。新课标中许多地方是要求学生通过实例了解的，如剩余类及其运算的内容，有的是通过实例进行探索的，如辗转相除法求两个整数的最大公因数，有的是要求学生通过实例理解的，如一次不定方程和一次同余方程组的模型。在这些地方，新知识的介绍是通过具体的例子来实现的。确定素数方法以及素数有无穷多个的证明有很多种，其中许多技巧性很强，但本专题的学习目标只是了解和知道基本事实即可，还有算术基本定理和数论在密码中的应用都是属于学生了解的内容。拉格朗日插值公式和孙子定理的教学，不必追求结论的一般形式（教材上仅考虑三个插值点和三个同余方程构成的方程组的情形），应把教学重点放在体会“先特解而后通解”的思想方法以及定理的内容和证明的理解上。类似的还有，最大公因数和最小公倍数的性质与一次不定方程的求解。2合理安排教学计划许多学生在小学就学习了整数的整除的一些初步知识。对带余除法、辗转相除法计算最大公因数、素因数分解式等操作上的内容比较熟悉，但对带