不可约多项式的性质和判定 论文

不可约多项式的性质和判定摘要数论中许多有关整数的概念和结论可以推广到多项式上去。本文首先将整数的算术基本定理推广到多项式理论中，得到多项式的基本定理；然后将素数的一些性质推广得到不可约多项式的一些性质；最后介绍素性检验常用方法，相应地，论述了不可约多项式的常用判别法。关键词：素数，多项式，算术基本定理。AbstractManyconceptsandconclusionsaboutintegersinnumbertheorycanbeextendedtopolynomials.Wefirstdeducethefundamentaltheoremofarithmetictopolynomialtheory,andobtainthefundamentaltheoremofpolynomials.Thenweextendsomepropertiesofprimenumberstosomepropertiesofirreduciblepolynomials.Finally,thecommonmethodsofprimalitytestareintroduced.Accordingly,thecommondiscriminantmethodsofirreduciblepolynomialsarediscussed.Keywords:Primes,Polynomials,FundamentalTheoremsofArithmetic.目录引言3第二章算术基本定理及其在多项式情形下的推广6第三章素数的性质及其在多项式情形下的推广10第四章素性检验以及不可约多项式的判定13参考文献19第一章引言整数和多项式是数论的主要研究对象之一。在数论研究中，一个常用的研究方法就是把有关整数成立的结论推广到多项式中去，我们发现，大多数情形下，结论惊人的类似。例如将整数的带余除法、辗转相除法、中国剩余定理推广到多项式中去（[2]、[7]等中都有具体的介绍），当然，也有不同的结论。如整数环是主理想整环（它的每个理想都是主理想），而多项式环一般不是主理想整环。例如整系数多项式环中(2,x)就不是一个主理想（详细证明见[19]），所以不是主理想整环。本文将从算术基本定理（定理2.1.1）出发，介绍算术基本定理的内容及其证明过程，并将其推广到多项式中得到类似的结论。整数的研究重点是素数，素数十分有趣，有许多关于素数的问题表述它们都很简单，但证明却十分困难。有许多关于素数的猜想至今还没能得到解决。古希腊数学家埃拉托斯特尼（Eratosthenes）发明了一种寻找素数的筛法，通过筛掉剩下的数的倍数得到给定范围的素数（详见4.1），通过筛法我们能够得到许多素数，但素数是否有无穷多个？这个问题在2000多年前由欧几里得（Euclid）证明：素数确实有无穷多个（详见3.1）。容易证明除了2和3以外，任意两个相邻素数（我们称两个素数为相邻的，如果它们之间不存在其它的素数）的差都是2的倍数，我们称相差为2的两个素数为孪生素数。随意给出一小列素数：13、17、19、23、29、31，我们可以发现（17，19）、（29，31）每一对中的两个素数的差都是2，因此它们都是孪生素数。那么是否有无穷多对这样的数呢？这就是著名的孪生素数猜想，但这个猜想如何证明是一大难题，甚至是它的“弱形式”都不知道是否成立，但在2013年数学家张益唐运用筛法证明了“存在无穷多个之差小于7000万的素数对”（[8]），使得对孪生素数猜想的研究取得了重大突破。与孪生素数猜想有着密切联系的是哥德巴赫猜想：“任意大于2的偶数都可以写成两个素数之和。”1742年哥德巴赫（Goldbach）写信请教欧拉（Euler）该如何证明这个猜想，遗憾的是欧拉（Euler）也没能证明出来。在20世纪之前，人们处在验证这个猜想阶段，没人能够证明它。1900年，希尔伯特（Hilbert）在国际数学家大会的报告中将这个猜想列入他的23个数学问题之中。1938年华罗庚证明了：“几乎所有的偶数都能表示成两个素数之和。”如果把命题“任一充分大的偶数都可以表示成为一个素因子个数不超过个的数与另一个素因子不超过b个的数之和”记作“”，1957年，王元证明了“2+3”。潘承洞在1962年证明了“1+5”。1963年，潘承洞、巴尔巴恩（BapoaH）与王元又都证明了“1+4”（[13]）。1973年陈景润用新的加权筛法证明了“1+2”（陈氏定理[3]）。除了上述猜想以外，应用科学中也有很多有关素数的难题：在对信息进行加密的过程中，会应用到大素数，然而高效率的判断一个很大的数（例如一个十进制下一百位的数）是否为素数是一个难题，一方面，人们试图去寻找能够表示所有素数的素数通项公式，因为只要能找到这样的通项公式，那么寻找素数、判断素数将不再是难事，例如如下的素数公式：,A对于任意的自然数m、n都是素数（公式的原理及详细证明见[15]），但是利用这个公式来寻找素数效率很低,因为经常取不同的m、n会得到相同的素数A，且在一定条件下m、n并不是独立的。另一方面，人们通过寻找素性检验算法来判断给定的数是否为素数（详见4.1），在2004年Agrawal、Kayal和Saxena做出了具有划时代意义的贡献，他们给出了一个多项式时间复杂度的确定性算法来测试一个数是否为素数（[1]）。在在多项式理论中，类似的问题就是判断一个给定的多项式是否是不可约多项式。由于不可约性与多项式所在数域有关，所以要分数域进行讨论。在有限域中，因为小于给定次数的多项式是有限多个，所以我们可以通过一个个试除的方式，判定一个多项式的不可约性，更高效的方法见[16]。由代数基本定理，复数域中的不可约多项式均是一次多项式，实数域中的不可约多项式均是一次或二次多项式。因此研究重点落在了有理数域和整数环上。艾森斯坦（Eisenstein）判别法算是一座里程碑，奠定了不可约判别法的基础，它还有许多衍生的判别法（[17]）。另一种常用方法是进行模p约化处理，多项式经模p约化得到对应的模p约化多项式（详见4.2），模p约化多项式所在域为有限域，因此能够简化判断的难度。虽然对于不可约多项式的研究已经有很多，但至今都没有一个可适应所有多项式判定的方法。在本文中，我们所讨论的多项式都是一元多项式，判断的是一元多项式的不可约性，但是我们对于一元多项式中的许多定义，不可约性判定方法都可以推广到多元多项式中，例如[4]中详细介绍了如何将一元多项式不可约性判定方法推广到二元多项式中。

本文的主要内容是：定理2.2.1：（多项式的算术基本定理）：对任意域F上的多项式，其中，均有（**），由唯一确定。其中取遍域F上所有的首一不可约多项式，c是的首项系数，是一个从域F上所有不可约多项式集合映到自然数集合的函数，且只在有限多个处取值不为0（因此（**）式右端的乘积为有限乘积）。本文的主要结构是：第二章阐述数论中算术基本定理的证明过程，将其推广到多项式理论中，得到域上的一元多项式的算术基本定理。第三章阐述素数的一些重要性质，以及在不可约多项式情形下的推广。例如证明了不可约多项式有无穷多个。

第四章介绍了几种素性检验方法，并论述了相应的不可约多项式判定的研究背景和具有代表性的判别方法。算术基本定理及其在多项式情形下的推广2.1算术基本定理算术基本定理又称为素数唯一分解定理，是数论中最重要的定理之一，由它的名称也可窥得一二，顾名思义关于算术的基本定理，能被称为是基本定理的定理对于整个数论来说肯定至关重要。在介绍算术基本定理之前，我们先来回顾一下什么是素数，不能被因式分解的正整数叫素数，换句话说就是若一个大于1的正整数p，1和p自身是p的所有正因数（、b是整数，且b不为0，如果存在整数c使得，则称b整除，同时称b是的一个因数。如果b大于0，称b为的一个正因数。由定义，我们容易得出，对任意正整数，1和自身都是的正因数。如果整数,b除了外无其它相同的因数，则称,b互素。），则称p是素数。例如：29、31、37这样的数都是素数，因为它们除了1和它本身之外没有其它正因数。而像6、21、35这样的数它们可以进行因式分解：6=23、21=37、35=57，所以6有正因数2，21有正因数3，35有正因数5，所以它们不是素数，称之为合数，另外，1既不是素数也不是合数。定理2.1.1（算术基本定理）：任意正整数都可以唯一表示为素数的乘积（其中1看作零个素数的乘积）。我们通过例子来理解这个定理，例如：考虑450，我们可以将450进行因式分解450=23355，唯一性是指只有素数2、3、5可将450进行分解，无其他素数，且指数1、2、2由450唯一决定。如果我们使用符号：（*），其中p取遍所有素数；为非负整数，是一个从所有素数组成的集合映射到自然数集合的函数，且只在有限多个p处取值不为0（因此（*）右端为有限乘积）。因此定理2.1.1表述为：任意正整数n可表示为，其中指数由n唯一确定。那么具体是什么呢？我们定义函数：如果，则。另外，若，则例如：则。之后我们可以证明。定理2.1.1看上去表述的很简单明了，但证明却不简单。我们需要介绍一些结论来作为证明的工具（以下证明思路参考了文[6]第一章的内容）。以下引理证明了定理2.1.1中表示的存在性。引理2.1.2：任意正整数n都可以写成素数的乘积（其中1看作零个素数的乘积）证明：我们通过对n归纳来证明：当n=1时，1看作零个素数的乘积，成立。当n=2时，2本身是素数，成立。假设我们已经证明的命题，则当n=k+1时，若n为素数，命题成立。若n为合数，则n可因式分解为，且，则，由归纳假设可写成素数的乘积，所以n可写为素数的乘积。综上命题得证。证明定理2.1.1的唯一性不像存在性那么简单，我们需要如下结论，这些结论看似显然，但对这样“显然的结论”的证明却是并不可少的。有关这些结论的证明可参见[5]引理2.1.3（整数的带余除法）：设,b是整数，且b大于0,则存在整数q,r，使得=qb+r,0r<b,且q,r是唯一的。引理2.1.4：如果整除bc，且,b互素，则整除c。由引理2.1.4我们得到两个推论，这两个推论是证明定理2.1.1唯一性的关键。推论2.1.5：若p是素数，p整除b，则p整除或p整除b。（注：在抽象代数中，这相当于说不可约元是素元，这等价于说相应的整环是唯一因子分解整环[19]）。推论2.1.6：若p是素数，,b是整数，则。有了以上内容作为工具，我们就可以证明定理2.1.1的唯一性了：使用函数作用于等式两边，由推论2.1.6函数的性质可得：，又，因此等式右边=，也就是说，因此唯一性得到证明，且。综合以上，定理2.1.1的存在性和唯一性都得到证明。例1：将194040化为（*）式的形式。解：将194040进行因式分解：，因此，其中p取遍所有素数，且。2.2（一元）多项式的情形我们可以将算术基本定理平行推广到（一元）多项式理论中，得到（一元）多项式的基本定理。在讨论此定理之前，同样的，我们先回顾一下什么是不可约多项式。域F上不能被因式分解的非常数多项式叫做不可约多项式，换句话说对于域F上的非常数多项式p(x)，常数或常数倍的p(x)是p(x)的所有因式，（域F上的多项式f(x)、g(x)，且g(x)不为零多项式，如果存在域F上的多项式q(x)，使得f(x)=q(x)g(x)，则称g(x)整除f(x)，且g(x)是f(x)的一个因式。如果f(x)、g(x)除了域F中的常数外无其他相同的因式，则称f(x)、g(x)互素。）则称p(x)为域F上的不可约多项式。例如：是实数域上的不可约多项式，因为它们除了实数或实数倍的自身，无其他因式。而像它们可以因式分解为、，所以、有因式，所以它们不是实数域上的不可约多项式。我们称首项系数为1的多项式为首一多项式，任意非零多项式可写成常数倍的首一多项式。例如：我们可以写成，其中是首一多项式。设p(x)是域F上的不可约多项式，定义数：如果则（注：若）定理2.2.1：（多项式的算术基本定理）：对任意域F上的多项式，其中，均有（**），由唯一确定。其中取遍域F上所有的首一不可约多项式，c是的首项系数，是一个从域F上所有不可约多项式集合映到自然数集合的函数，且只在有限多个处取值不为0（因此（**）式右端的乘积为有限乘积）。我们沿用整数算术基本定理的证明途径来证明上述定理，以下引理证明了定理2.2.1中（**）式的存在性。引理2.2.2：域F上的非常数多项式可以写成不可约多项式的乘积。证明：任取域F上的非常数多项式，设，则由是非常数多项式，。下面对n作数学归纳法：首先当n=1，为不可约多项式，命题成立。现设对的任意次数为n的多项式，都可以写成不可约多项式的乘积。则n=k+1时：当k+1次多项式为不可约多项式时，命题成立。当k+1次多项式为可约多项式时，，且，所以，可写成不可约多项式的乘积，因此可写成不可约多项式的乘积。综上，命题得证。为了证明定理2.2.1的唯一性，我们需要如下结论：（以下引理2.2.3、2.2.4分别是引理2.1.2、2.1.3的推广）引理2.2.3（多项式的带余除法）：设f(x),g(x)是域F上的两个多项式，且g(x)不为零多项式，则存在域F上的两个多项式q(x)、r(x)，使得f(x)=q(x)g(x)+r(x)，r(x)=0或deg(r(x))<deg(g(x))，且q(x),r(x)由f(x),g(x)唯一确定。引理2.2.4：如果f(x)整除g(x)h(x)，且f(x)、g(x)互素，则f(x)整除h(x)。由引理2.2.4我们得到两个推论，这两个推论是证明定理2.2.1唯一性的关键。推论2.2.5：若p(x)为域F上的不可约多项式，且p(x)整除f(x)g(x)，则p(x)整除f(x)或p(x)整除g(x)。推论2.2.6：设p(x)为域F上的首一不可约多项式，f(x)、g(x)是域F上的多项式，则。有了以上内容作为工具，我们就可以证明定理2.2.1的唯一性了：用作用于两边，由推论2.2.6我们能够得到：，因为c为常数，所以，，所以，因此指数唯一确定。因为为域F上的首一不可约多项式，所以c为的首项系数，因此c也由唯一确定。定理2.2.1的唯一性得到证明。例2：在有理数域上分解多项式。解：首先易知、因此、为的因式且是有理数域上的不可约多项式，所以可由、表示为，又在有理数域上是不可约多项式，因此可表示为，其中。第三章素数的性质及其在多项式情形下的推广定理3.1：素数有无穷多个。素有“几何之父”之称的古希腊学者欧几里得（Euclid）在《几何原本》中给出了该定理的证明，因此该定理又称为欧几里得定理（Euclidtheorem）。这个定理虽然表述很简单，但却魅力无穷，吸引了很多数学家，在欧几里得（Euclid）后给出了数以百计的证明方法。卢昌海在文章[9]中总结了九种比较具有代表性的证明方法。由于欧几里得（Euclid）的证明方法简单而历久弥新，可以说是反证法的范例，欧拉（Euler）的证明则是一个美妙的证明。因此，以下我们只引述欧几里得（Euclid）和欧拉（Euler）的证明。欧几里得（Euclid）的证明：反证：设只有有限多个素数，记作，，,,令，显然，所以N不是素数，又N不为1，所以N是合数，由算数基本定理可知，存在素数整除N，然而，矛盾，所以有无穷多个素数。下面这个证明由欧拉（Euler）给出，它展示了用分析的工具来解决数论中的问题，被视为解析数论的开端：设，，,是所有小于等于n的素数，定义。因为=1++++，所以=（3.1）。由算数基本定理，任意m小于等于n，m可以写成，，,的乘积，即中必然会出现在（3.1）右边的某一项中，（），所以素数有无穷多个。又==2，所以。于是通过欧拉的证明我们不仅能够得到有无穷多个素数且所有素数的倒数和发散。我们知道了素数有无穷多个，那么这些素数是如何分布的？素数的分布规律一直困扰着数学家们，一个一个的看，素数在自然数中出现没有什么规律，但如果总体的看，素数竟是有规律的。如果令是1到x之间的所有素数，许多数学家通过实验发现：当x越大越趋向于，这就是著名的素数定理。素数定理描述的是素数在自然数中的分布的渐进情况，被认为是素数的渐进分布定律。定理3.3：（素数定理）(),亦即：。(定理的详细内容及不同证明方法参见[11])这一定理是1800年左右法国数学家勒让德（Legendre）提出的，数学王子高斯(Gauss)也未能证明，经过100多年时间，在1896年法国数学家阿达马（Hadamard）和比利时数学家普森（Poussin）先后给出独立的证明。证明用到了复分析和黎曼ζ函数。此后，许多数学家都期望找到尽可能简单的证明或它的初等证明。在1949年，两位年轻的数学家——赛尔伯格(Selberg)和爱多士(Erdös)分别独立地证明了素数定理，并且他们给出的是一个完全“初等”的证明，当然证明是复杂的。这一结果轰动了整个数学界，赛尔伯格由于这项成就及其他工作而获得了菲尔兹奖，爱多士则与陈省身一起获得了沃尔夫数学奖。通过素数定理我们也能够得到素数有无穷多个，虽然有点大材小用，而且通过素数定理我们可以给出关于第n个素数的渐进估计：，同时，该定理也给出了从自然数中抽取素数的概率：从小于等于n的自然数中随机的抽取一个数，它是素数的概率是。与第二章相同，我们可以将素数的性质推广到多项式环境中，得到不可约多项式的性质。定理3.4：域F上的不可约多项式有无穷多个。证明：若p(x)为域F上的不可约多项式，任取c为域F中的非零常数，则cp(x)也为不可约多项式，因此我们可以讨论首一不可约多项式。设只有有限多个首一不可约多项式，记为，令，因为整除但是不整除1，所以不整除则，所以不是不可约多项式，又，则是可约多项式，由多项式的算数基本定理，存在整除，矛盾。所以，域F上的首一不可约多项式有无穷多个。素数定理告诉我们素数的渐进分布规律，那么在有限域上的不可约多项式有没有什么分布规律呢？我们在寻找有限域上的m次首一不可约多项式时，需要考虑随机选取的多项式是不可约多项式的可能性有多大：设为中的m次首一不可约多项式的个数，则（详见[12]）而为m次首一多项式的总数，故当m充分大时，随机给出一个m次首一多项式是不可约多项式的概率大致为。第四章素性检验及不可约多项式的判定4.1几种素性检验方法1.埃拉托斯特尼（Eratosthenes）筛法：将从1开始的给定范围内的正整数按从小到大的顺序排列，逐步筛掉非素数，直到筛子为空时结束，则留下的数为素数。我们通过一个例子来具体说明筛法的使用过程。例3：任意给定一个正整数30，如图4-1按从小到大的顺序列出1到30的所有的数；第一步：因为1不是素数，所以把1划掉，即划去图4-1中绿色的数字；第二步：1后面的第一个数是2，2是素数，保留2，划掉所有2的倍数：4、6、8、10、12、14、16、18、20、22、24、26、28、30，即划去图4-1中红色的数字；第三步：从2往后找，找到第一个未被划去的数是3，保留3，划掉所有3的倍数：9、15、21、27，即划去图4-1中黄色的数字；第四步：从3往后找，找到第一个未被划去的数是5，保留5，划掉所有5的倍数：25，即划去图4-1中蓝色的数字；第五步：从5往后找，找到第一个未被划去的数是7，保留7，划掉所有7的倍数，可以看到，已经没有这样的数了，筛子为空；第六步：结束筛选，将所有保留的数列出：2、3、5、7、11、13、17、19、23、29，即图4-1中灰色底的数字即为30以内的所有素数。2357111317192329（图4-1）在我们用此筛法过程中，筛除某个素数n的倍数时，已经被作为小于该素数的数的倍数筛掉了，因此，倍数应从开始筛除，所以在之前的这些数中已经没有任何可以被小于或等于n的数整除的数了，这就保证了之前剩下的数都为素数。所以当我们用筛法来寻找1到n的所有素数时，只需要尝试筛除2到之间的所有整数的倍数即可。由此我们得到了以下的试除法。2.试除法：主要是尝试从2到的整数是否整除n来检验n是否为素数，若通过检验，则n是素数，这是一种确定性检验。这里需要试除([]-1)次，当n特别大时，需要试除的次数非常多，且其中有些数不需要挨个试除，因此，此算法效率非常低。例4：检验53是否为素数。解：首先，所以我们只需尝试从2到7是否整除53来检验53是否为素数，又2不整除53，3不整除53，4不整除53，5不整除53，6不整除53，7不整除53，因此，53通过检验，所以53是素数。3.费马素性检验：根据费马小定理：任意的素数p,任意的,(,p)=1,有，如果我们想知道n是否为素数，我们从中间选取小于等于n-1的正整数,看看是否满足等式，若存在不成立，则n是合数，若对于很多个都能使等式成立，则n很有可能是素数。（Carmichael数除外，最小的Carmichael数是561，Carmichael数有无穷多个）这是一种概率性检验。例5：利用费马素性检验，检测17是否为素数。解：任意选取小于等于16的正整数,不妨取=2，（2，17）=1，；=3，（3，17）=1，；=4，（4，17）=1，；=6，（6，17）=1，；=8，（8，17）=1，；存在很多个使得等式成立，因此17极有可能是素数。4.AKS素性测试：以下算法引自[1]算法如下：输入正整数n>1；如果n能够表示成，则n不是素数；寻找最小的r，使得（这里是以2为底的对数）；如果对于一些，有1<(a,n)<n，则n是合数；如果，则n是素数；当,如果则n是合数，否则n是素数。流程图如下：输入n(>1)n=YESNO输出n不是素数寻找最小的r,，有1<(a,n)<nYESNO输出n不是素数NOYES到输出n是素数YES输出n不是素数输出n是素数例6：用ASK素性测试算法来证明7是素数。(这个例子并没有涉及AKS算法的核心部分)证明：因为，所以不存在使得；接下来我们需要寻找最小的r，使得，又，所以。当r=1时，（7，1）=1，不存在正整数k使得（舍去），当r=2时，（7，2）=1，（舍去），当r=3时，（7，3）=1，（舍去），当r=4时，（7，4）=1，（舍去），当r=5时，（7，5）=1，（舍去），当r=6时，（7，6）=1，（舍去），当r=7时，（7，7）=7（舍去），当r=8时，（7，8）=1，（舍去），当r=9时，（7，9）=1，（舍去），当r=10时，（7，10）=1，（舍去），当r=11时，（7，11）=1，（成立），所以r=11;任意的正整数；又，所以7是素数。在多项式中，我们也在寻找有理数域和整数环上的不可约多项式的判定方法。如果是有理数域Q上的非零多项式，我们取整数c,使得为整数，取,则是整数环上的本原多项式（关于本原多项式的定义及证明参见[5]）。因此，有理数域上的任意非零多项式都对应整数环上的一个本原多项式。如果，其中为非零有理数，为对应的本原多项式，则。又为本原多项式，则。因此从本质上来说，此对应是唯一的。所以，对于有理数域上多项式的不可约问题，我们可以简化为讨论整数环上的多项式的不可约问题。判断一个整系数多项式是否可约是很困难的，其中最为经典的判别法是艾森斯坦（Eisenstein）判别法，另一个著名手法是模p约化法，通过模p约化简化多项式，使我们能容易的判断其不可约性。当然，还有许多其他的判别方法，以及一些对于特殊形式的多项式的判别法，但是到目前为止，还没能找到一个通用的判别方法适应所有的多项式。4.2整系数多项式不可约性常用判别法1.艾森斯坦（Eisenstein）判别法：设是整系数多项式，若存在素数p，使得：①p，②，③，则在整数环Z上不可约（有理数域Q上也不可约）。下面我们通过举例来运用此判别方法，在实际问题中有时需要通过转化来间接运用此判别法，而文章[18]告诉我们一类不能运用此判别法的多项式，表明此判别法并不适应所有的多项式。例7：证明，在有理数域Q上不可约。证明：取p=3,则，由艾森斯坦判别法在Q上不可约。2.模p约化法：设为整系数多项式，将模p（p是素数），得到对应的，即将它们的系数对应所属的模p同余类，称为的模p约化多项式。我们有结论：若整系数多项式的模p约化多项式在上为不可约多项式，则在整数环上不可约（在有理数域也不可约）。反之不成立。例8：证明为有理数域上的不可约多项式。证明：取p=5，得的模5约化多项式，易知为上的不可约多项式，所以由模p判别法知为有理数域上的不可约多项式。4.3在有限域上寻找不可约多项式通过筛法我们可以找到给定范围内的素数，那么在有限域中我们能否寻找给定次数的不可约多项式？设是一个有限域，若在有限