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

　　Ø 第一章 整除

　　一、主要内容

　　整除的定义、带余除法定理、余数、最大公因数、最小公倍数、辗转相除法、互素、两两互素、素数、合数、算术基本定理、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)。