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

2018-09-30 14:52 来源:网络综合
自考网权威发布2018年自考公共课数论初步章节讲义,更多2018年自考公共课数论初步章节讲义相关信息请访问自考网。

【导语】让时间在知识的枝条上、智慧的绿叶上、成熟的果实上留下它勤奋的印痕!以下是无忧考网为大家整理的《2018年自考公共课数论初步章节讲义》供您查阅。




【同余】

  一、 主要内容


  同余的定义、性质、剩余类和完全剩余系、欧拉函数、简化剩余系、欧拉定理、费尔马小定理、循环小数、特殊数2,3,4,5,6,7,8,9,11,13的整除规律


  二、 基本要求


  通过本章的学习,能够掌握同余的定义和性质,区别符号:“三”和=”之间的差异。能利用同余的一些基本性质进行一些计算,深刻理解完全剩余系,简化剩余系的定义、性质及构造。能判断一组数是否构成模m的一个完全剩余系或一个简化剩余系。能计算欧拉函数的值,掌握欧拉定理、费尔马小定理的内容以及证明方法。能应用这二个定理证明有关的整除问题和求余数问题。能进行循环小数与分数的互化。


  三、难点和重点


  (1)同余的概念及基本性质


  (2)完全剩余系和简化剩余系的构造、判别


  (3)欧拉函数计算、欧拉定理、费尔马小定理的证明及应用


  (4)循环小数与分数的互化


  (5)特殊数的整除规律。


  四、自学指导


  同余理论是初等数论中最核心的内容之一,由同余定义可知,若a≡b(mod m),则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(mod m) ,(k,m)=1,则a≡b(mod m)


  (ii)模改变的除法, 若ak≡bk(mod m) (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(mod 100)


  (100)=


  (22·52)=40, ∴ 340≡1(mol 100)


  ∴ 3406=(340)10·36≡(32)2·32≡-19×9≡-171≡29(mod 100)


  ∴ 末二位数为29。


  例2:证明(a+b)p≡ap+bp(mod p)


  证:由费尔马小定理知对一切整数有: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)作了一些限制,而这些限制并不影响其一般性。在条件x>0,y>0,z>0,(x,y)=1,2∣x的条件可以给出x2+y2=z2的通解公式,x=2ab,y=a2-b2,z2=a2+b2,a>b>0 , (a ,b)=1,a ,b一奇一偶。若将2∣x限为2∣y,则也有相应的一个通解公式。在证明这个通解公式的过程中,用到了引理 uv=w2,u>0,v>0,(u ,v)=1,则u=a2,v=b2,w=ab 。a>0,b>0,(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+3t2


  z=-2x-2y+10+t1=6-5t1+10t2


  ∴原不定方程解为


  t1t2∈z. 例2:证明


  是无理数证:假设


  是有理数,则存在自数数a,b使得满足


  即


  ,容易知道a是偶数,设a=2a1,代入得


  ,又得到b为偶数,


  ,设


  ,则


  ,这里


  这样可以进一步求得a2,b2…且有a>b>a1>b1> a2>b2>…


  但是自然数无穷递降是不可能的,于是产生了矛盾,∴


  为无理数。


  例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)


  它可以重作是整除的推广。同时也可以用带余除法定理来定义整除性,(即当余数r=0时)。带余除法可以将全体整数进行分类,从而可将无限的问题转化为有限的问题。这是一种很重要的思想方法,它为我们解决整除问题提供了又一条常用的方法。同时也为我们建立同余理论建立了基础。读者应熟知常用的分类方法,例如把整数可分成奇数和偶数,特别对素数的分类方法。例全体奇素数可以分成4k+1,4k+3;或6k+1,6k+5等类型。


  和整除性一样,二个数的公约数实质上也是用等号来定义的,因此在解决此类问题时若有必要可化为等式问题,公因数的性质中最重要的性质之一为 a=bq+c,则一定有(a,b)=(b,c),就是求二个整数的公约数的理论根据。也是解决关于公约数问题的常用方法之一。读者应有尽有认真体会该定理的证明过程。


  互素与两两互素是二个不同的概念,既有联系,又有区别。要认真体会这些相关的性质,例如,对于任意a ,b∈Z,可设(a ,b)=d,则a=da1 ,b=db1,则(a1 ,b1)=1,于是可对a1 ,b1使用相应的定理,要注意,相关定理及推论中互素的条件是经常出现的。读者必须注意定理成立的条件,也可以例举反例来进行说明以加深影响。顺便指出,若a∣c,b∣c,(a ,b)=1,则ab∣c是我们解决当除数为合数时的一种方法。好处是不言而喻的。


  最小公倍数实际上与公因数为对偶命题。特别要指出的是a和b的公倍数是有无穷多个。所以一般地在无穷多个数中寻找一个最小数是很困难的,为此在定义中所有公倍数中的最小的正整数。这一点实际上是应用自然数的最小自然数原理,即自然数的任何一个子集一定有一个最小自然数有在。最小公倍数的问题一般都可以通过以下式子转化为公因数的问题。两者的关系为


  a ,b∈N, [a ,b]=ab/(a,b)


  上述仅对二个正整数时成立。当个数大于2时,上述式子不再成立。证明这一式子的关键是寻找a , b的所有公倍数的形式,然后从中找一个最小的正整数。


  解决了两个数的最小公倍数与公因数问题后,就可以求出n个数的最小公倍数与公因数问题,可以两个两个地求。即有下面定理


  设a1,a2,a3...ax


  是n个整数,(a1,a2)=d2;


  (d2,a3)=d3,...


  (dn-q,an)=dn,


  则(a1,a2,...ax)=dx


  a1,a2,...an]=mn


  素数是数论研究的核心,许多中外闻名的题目都与素数有关。除1外任何正整数不是质数即为合数。判断一个已知的正整数是否为质数可用判别定理去实现。判别定理又是证明素数无穷的关键。实际上,对于任何正整数n>1,由判别定理一定知存在素数p,使得p∣n 。即任何大于1的整数一定存在一个素因数p 。素数有几个属于内在本身的性质,这些性质是在独有的,读者可以用反例来证明:素数这一条件必不可少。以加深对它们的理解。其中p∣ab


  →p∣a或p∣b也是常用的性质之一。也是证明算术基本定理的基础。


  算术基本定理是整数理论中最重要的定理之一,即任何整数一定能分解成一些素数的乘积,而且分解是的,不是任何数集都能满足算术基本定理的,算术基本定理为我们提供了解决其它问题的理论保障。它有许多应用,由算术基本定理我们可以得到自然数的标准分解问题。


  设a=


  ,b=


  ,


  则有 (a,b)=


  [a,b]=


  例如可求公约数,正整数正约数的个数等方面问题,对具体的n,真正去分解是件不容易的事。对于较特殊的n,例如n!分解还是容易的。应用[x]的性质,n!的标准分解式可由一个具体的公式表示出来,这一公式结合[x]的性质又提供了解决带有乘除符号的整除问题的方法。


  本章的许多问题都围绕着整除而展开,读者应对整除问题的解决方法作一简单的小结。


  五、例子选讲


  补充知识


  ①最小自然数原理:自然数的任意非空子集中一定存在最小自然数。


  ②抽屉原理:


  (1)设n是一个自然数,有n个盒子,n+1个物体,把n+1个物体放进n个盒子,至少有一个盒子放了两个或两个以上物体;


  (2)km+1个元素,分成k组,至少有一组元素其个数大于或等于m+1;


  (3)无限个元素分成有限组,至少有一组其元素个数为无限。


  ③梅森数:形如2n-1的数叫梅森数,记成Mn=2n-1。


  ④费尔马数:n为非负整数,形如


  的数叫费尔马数,记成Fn=


  。 ⑤设n=


  ,设n的正因子个数为d(n),所有正因子之和为


  ,则有


  ⑥有关技巧


  1. 整数表示a=a0×10n+a1×10n-1+…+an,


  a=2kb(b为奇数)


  2.整除的常用方法


  a. 用定义


  b. 对整数按被n除的余数分类讨论


  c. 连续n个整数的积一定是n的倍数


  d. 因式分解


  an-bn=(a-b)M1,


  an+bn=(a+b)M2, 2


  n


  e. 用数学归纳法


  f. 要证明a|b,只要证明对任意素数p,a中p的幂指数不超过b中p的幂指数即可,用p(a)表示a中p的幂指数,则a|b


  p(a)


  p(b)


  例题选讲


  例1.请写出10个连续正整数都是合数.


  解: 11!+2,11!+3,……,11!+11。


  例2. 证明连续三个整数中,必有一个被3整除。


  证:设三个连续正数为a,a+1,a+2,而a只有3k,3k+1,3k+2三种情况,令a=3k,显然成立,a=3k+1时,a+2=3(k+1),a=3k+2时,a+1=3(k+1)。