2019年自考公共课数论初步章节讲义

2019年自考公共课数论初步章节讲义【同余】一、主要内容同余的定义、性质、剩余类和完全剩余系、欧拉函数、简化剩余系、欧拉定理、费尔马小定理、循环小数、特殊数2，3，4，5，6，7，8，9，11，13的整除规律二、基本要求通过本章的学习，能够掌握同余的定义和性质，区别符号：三和=之间的差异。能利用同余的一些基本性质实行一些计算，深刻理解完全剩余系，简化剩余系的定义、性质及构造。能判断一组数是否构成模m的一个完全剩余系或一个简化剩余系。能计算欧拉函数的值，掌握欧拉定理、费尔马小定理的内容以及证明方法。能应用这二个定理证明相关的整除问题和求余数问题。能实行循环小数与分数的互化。三、难点和重点(1)同余的概念及基本性质(2)完全剩余系和简化剩余系的构造、判别(3)欧拉函数计算、欧拉定理、费尔马小定理的证明及应用(4)循环小数与分数的互化(5)特殊数的整除规律。四、自学指导同余理论是初等数论中最核心的内容之一，由同余定义可知，若a≡b(modm)，则a和b被m除后有相同的余数。这里m为正整数，一般要求m大于1，称为模，同余这个思想本质上是将整数按模m分类，然后讨论每一个类中整数所具有的共性及不同类之间的差异。第一章中用带余除法定理将整数分类解决一些问题的方法只不过是同余理论中的一个特殊例子。从同余的定理上看，同余和整除实际上是同一回事，故同余还有二个等价的定义：①用整除来定义即m∣a-b。②用等号来定义a=b+mt。值得注意a和b关于m同余是个相对概念。即它是相对于模m来讲，二个整数a和b关于一个整数模m同余。则对于另一个整数模m，a和b未必会同余。从定义上看，同余和整除是同一个事情，但引进了新的符号三后，无论从问题的叙述上，还是解决问题的方法上都有了显著的变化，同时也带来了一些新的知识和方法。在引进了同余的代数性质和自身性质后，同余符号三和等号=相比，在形式上有几乎一致的性质，这便于我们记忆。事实上在所有等号成立的运算中，只有除法运算是个例外，即除法的消去律不成立。为此对于同余的除法运算我们有二种除法：(i)模不改变的除法，若ak≡bk(modm)，(k,m)=1，则a≡b(modm)(ii)模改变的除法,若ak≡bk(modm)(k,m)=d,则a≡b这个点读者要特别注意。完全剩余系和简化剩余系是二个全新的概念，读者只要搞清引成这些概念的过程。因为同余关系是一个等价关系，利用等价关系能够实行将全体整数实行分类，弄清来胧去脉，对于更深刻理解其本质是很有好处的。完全剩余系或简化剩余系是一个以整数为元素的集合，在每个剩余类各取一个数组成的m个不同数的集合，故一组完全剩余系包含m个整数，因为二个不同的剩余类中的数关于m两两不同余，故可得判别一组数是否为模m的一个完全剩余系的条件有二条为(1)个数=m(2)关于m两两不同余另外要能用已知完全剩余系构造新的完全剩余系。即有定理设(a，m)=1，x为m的完全剩余系，则ax+b也是m的完全剩余系。当时，能由的完全剩余系和的完全剩余系，构造完全剩余系。为讨论简化剩余系，需要引进欧拉函数φ(m)，欧拉函数φ(m)定义为不超过m且与m互素的正整数的个数，记为φ(m)，要掌握φ(m)的计算公式，了解它的性质。这些性质最主要的是当(a,b)=1时，φ(ab)=φ(a)φ(b)，和现在在剩余类中把与m互素的集合分出来，从中可在各个集合中任取一个数即可构造模m的一个简化剩余系。另一方面，简化剩余数也可从模m的一个完全剩余系中得到简化剩余系，一组完全剩余系中与m互素的的数组成的φ(m)个不同数的集合称为m简化剩余系。同样简化剩余系也有一个判别条件。判别一组整数是否为模m的简化剩余系的条件为(1)个数=φ(m)(2)关于m两两不同余(3)每个数与m互素关于m的简化剩余系也能用已知完全剩余系构造新的简化剩余系。设(a，m)=1，x为m的简化剩余系，则ax也是m的简化剩余系。当时，能由的简化剩余系和的简化剩余系，构造简化剩余系。欧拉定理、费尔马小定理是同余理论非常重要的定理之一。要注意欧拉定理和费尔马定理的条件和结论。欧拉定理：设m为大于1的整数，(a，m)=1，则有费尔马小定理：若p是素数，则有除此以外，欧拉定理的证明的思想是非常好的，在各个地方都有应用。就欧拉定理、费尔马小定理来讲，它在某些形如a数的整除问题应用起来显得非常方便。同余方法也是解决整除问题的方法之一。另外同余方法在证明不定方程时也非常有用，即要掌握同余三和相等=的关系：相等必同余，同余未必相等，不同余肯定不相等。对于特殊数的整除规律要求能掌握其一般定理的证明，并熟记一些特殊数的整除规律1、一个整数被2整除的充要条件是它的末位为偶数。2、一个整数被3整除的充要条件是它的各位数字之和能被3整除。3、一个整数被9整除的充要条件是它的各位数字之和能被9整除。4、一个整数被5整除的充要条件是它的末位为0或5。5、一个整数被4，25整除的充要条件是它的末二位能被4，25整除。6、一个整数被8，125整除的充要条件是它的末三位能被8，125整除。7、设，则7或11或13整除a的充要条件是7或11或13整除五、例子选讲例1：求3406的末二位数。解：∵(3，100)=1，∴3≡1(mod100)(100)=(22·52)=40,∴340≡1(mol100)∴3406=(340)10·36≡(32)2·32≡-19×9≡-171≡29(mod100)∴末二位数为29。例2：证明(a+b)p≡ap+bp(modp)证：由费尔马小定理知对一切整数有：ap≡a(p)，bp≡b(P)，由同余性质知有：ap+bp≡a+b(p)又由费尔马小定理有(a+b)p≡a+b(p)(a+b)p≡ap+bp(p)【不定方程】一、主要内容一次不定方程有解的条件、解数、解法、通解表示，不定方程x2+y2=z2通解公式、无穷递降法、费尔马大定理。二、基本要求1、了解不定方程的概念，理解对解的理解，掌握一次不定方程有解的条件，能熟练求解一次不定方程的特解，正整数解及通解。了解多元一次不定方程有解的条件，在有解的条件下的解法。2、掌握不定方程x2+y2=z2在一定条件下的通解公式，并使用这个通解公式作简单的应用。3、对费尔马大定理应有在常识性的了解，掌握无穷递降法求证不定方程x4+y4=z2无解的方法。4、掌握证明不定方程无解的若干方法。三、难点和重点(1)重点为求解一次不定方程的方法(2)掌握第二节中引证的应用。(1)费尔马无穷递降法。四、自学指导不定方程主要讲解以下几个问题(i)给定一类不定方程，判别在什么条件下有解。(ii)在有解的条件下，有多少解(iii)在有解的条件下，求出所给的不定方程的所有解。二元一次不定方程的一般形式为ax+by=c。若(a,b)∣c，则该二元一次不定方程一定有解，若已知一个特解，则一切解能够用公式表示出来，所以求它的通解只要求出一个特解即可。求解二元一次不定方程的一个通解有好多种方法。读者应该总结一下，各种方法都有独到之处。特别要指出用公因数的方法。它的根据是求(a,b)时所得的结果。因为注意通解公式x=x0-b1t，y=y0+a1t中a1，b1的意义和位置。以免出错。多元一次不定方程也有类似的结果，但在求解的过程中将它转化二元一次不定方程组，从最后一个二元一次不定方程解起，可逐一解出x1,x2,……xn。所用的方法一般选择公因数的方法。因为n元一次不定方程可转化为n-1个二元一次不定方程组，故在通解中依赖于n-1个任意常数。但不象二元一次不定方程那样有公式来表示。x2+y2=z2的正整数解称为勾股数，在考虑这个方程时，我们对(x,y)作了一些限制，而这些限制并不影响其一般性。在条件x0，y0，z0，(x，y)=1，2∣x的条件能够给出x2+y2=z2的通解公式，x=2ab，y=a2-b2，z2=a2+b2，ab0,(a,b)=1，a,b一奇一偶。若将2∣x限为2∣y，则也有相对应的一个通解公式。在证明这个通解公式的过程中，用到了引理uv=w2，u0，v0，(u,v)=1，则u=a2，v=b2，w=ab。a0，b0，(a,b)=1。利用这个结论能够求解某些不定方程。特别当w=1或素数p。则由uv=1或uv=P可将原不定方程转化为不定方程组。从而获得一些不定方程的解。上述解不定方程的方法叫因子分解法。希望读者能掌握这种方法。为了解决的费尔马大定理：xn+yn=zn，n≥3无正整数解时，当n=4时能够用较初等的方法给出证明。证明由费尔马本人给出的，一般称为费尔马无穷递降法。其基本思想为由一组解出发通过构造得出另一组解，使得两组解之间有某种特定的关系，而且这种构造能够无限重复的。从而可得到矛盾。所以无穷递降法常用来证明某些不定方程无整数解。证明一类不定方程无解是研究不定方程邻域中常见的形式，一般的要求解不定方程比证明不定方程无解要容易些。证明不定方程无解的证明方法常采用以下形式：(反证法)若A有解A1有解A2有解……An有解，而An本身无解，这样来构造矛盾。从而说明原不定方程无解。对于证明不定方程的无解性通常在几种方法，一般是总的几种方法交替使用。特别要求掌握：简单同余法、因子分解法、不等式法，以及中学数学中所涉及的判别式法。五、例子选讲例1：利用整数分离系数法求得不定方程15x+10y+6z=61。解：注意到z的系数最小，把原方程化为z=令t1=，即-3x+2y-6t1+1=0此时y系数最小，令t2=,即,反推依次可解得y=x+3t1+t2=2t2+1+3t1+t2=1+3t1+3t2z=-2x-2y+10+t1=6-5t1+10t2∴原不定方程解为t1t2∈z.例2：证明是无理数证：假设是有理数，则存有自数数a,b使得满足即，容易知道a是偶数，设a=2a1，代入得，又得到b为偶数，，设，则,这里这样能够进一步求得a2，b2…且有aba1b1a2b2…但是自然数无穷递降是不可能的，于是产生了矛盾，∴为无理数。例3：证明：整数勾股形的勾股中至少一个是3的倍数。证：设N=3m±1(m为整数)，∴N2=9m2±6m+1=3(3m2±2m)+1即一个整数若不是3的倍数，则其平方为3k+1,或者说3k+2不可能是平方数，设x,y为勾股整数，且x,y都不是3的倍数，则x2,y2都是3k+1，但z2=x2+y2=3k+2形，这是不可能，∴勾股数中至少有一个是3的倍数。【整除】一、主要内容整除的定义、带余除法定理、余数、公因数、最小公倍数、辗转相除法、互素、两两互素、素数、合数、算术基本定理、Eratosthesen筛法、[x]和{x}的性质、n!的标准分解式。二、基本要求通过本章的学习，能了解引进整除概念的意义，熟练掌握整除整除的定义以及它的基本性质，并能应用这些性质，了解解决整除问题的若干方法，熟练掌握本章中二个的定理：带余除法定理和算术基本定理。认真体会求二个数的公因数的求法的理论依据，掌握素数的定义以及证明素数有无穷多个的方法。能熟练求出二个整数的公因数和最小公倍数，掌握高斯函数[x]的性质及其应用。三、重点和难点(1)素数以及它相关的性质，判别正整数a为素数的方法，算术基本定理及其应用。(2)素数有无穷多个的证明方法。(3)整除性问题的若干解决方法。(4)[x]的性质及其应用，n!的标准分解式。四、自学指导整除是初等数论中最基本的概念之一，b∣a的意思是存有一个整数q，使得等式a=bq成立。所以这个标准作为我们讨论整除性质的基础。也为我们提供了解决整除问题的方法。即当我们无法用整除语言来叙述或讨论整除问题时，能够将其转化为我们很熟悉的等号问题。对于整除的若干性质，最主要的性质为传递性和线性组合性，即(1)a∣b,b∣c,则有a∣c(2)a∣b,a∣c,则有a∣mb+nc读者要熟练掌握并能灵活应用。特别要注意，数论的研究对象是整数集合，比小学数学中非负整数集合要大。本章中最重要的定理之一为带余除法定理，即为设a是整数，b是非零整数，则存有两个整数q，r，使得a=bq+r(0)它能够重作是整除的推广。同时也能够用带余除法定理来定义整除性