计算机代数基础 69页

计算机代数基础———代数与符号计算的基本原理张树功雷娜刘停战编北京\n内容简介随着计算机技术的飞速发展，计算机代数系统已经被广泛地应用于科研、教学以及工程技术，其中比较有名的有Maple，Mathematica等．本书主要介绍这些系统中基本问题的数学原理和基本算法，即计算机代数的基本知识．本书是为数学、计算数学和计算机科学专业的高年级本科生和低年级研究生编写的教材，也可供相关专业的学生、教师以及科技工作者参考．图书在版编目（CIP）数据计算机代数基础：代数与符号计算的基本原理／张树功等编．—北京：科学出版社，２００５（面向２１世纪高等院校计算机系列规划教材）ISBN７唱０３唱０１５３２５唱１Ⅰ畅计⋯Ⅱ畅张⋯Ⅲ畅电子计算机数值计算Ⅳ畅TP３０１畅６中国版本图书馆CIP数据核字（２００５）第０２８８５４号责任编辑：李娜丁波／责任校对：刘彦妮责任印制：吕春珉／封面设计：三函设计科学出版社发行各地新华书店经销倡２００５年５月第一版开本：７８７×１０９２１／１６２００５年５月第四次印刷印张：１４１／２印数：１—３０００字数：３４００００定价：19畅00元（如有印装质量问题，我社负责调换枙新欣枛）销售部电话：０１０唱６２１３６１３１编辑部电话：０１０唱６２１３８９７８唱８００４（HI０２）\n前言在人类生活、经济建设和科技发展过程中，“计算”始终都扮演着非常重要的角色．在对自然界和人类社会各种事物发展规律的研究中，当从定性分析过渡到定量分析时，就必然涉及计算．例如每天的天气预报，就是根据当前的气温、气压数据按某种方法和程序计算出明、后天的天气甚至以后更长时间的各种气象指标；至于人造飞船上天、原子能的开发和利用以及各种矿藏的勘探与开采等高科技活动就更离不开计算。因此，计算能力的强弱直接制约着一个国家的经济和科技发展速度．人类的计算能力与计算工具密切相关，早期的计算主要是靠人的大脑再加上一些简单的计算工具来完成，计算效率低，可靠性也很差．电子计算机的出现大大地提高了人类的计算能力，从而也促进了科学技术的迅猛发展．最初的电子计算机多用于一般规模的数值计算，因此计算机的出现也催生了计算数学———研究在计算机上实现数值计算的理论与算法的数学分支．实际上，对科学与工程技术以及数学研究本身的发展需要而言，不仅需要数值计算，还需要公式推导、表达式的化简、函数的微分及积分、精确地解各种方程等计算．这种计算的特点是对一些符号按确定的规则进行的演算，并且计算过程都是精确的，人们称这种计算为符号计算、公式推演或者代数计算．这种计算的需求在实践中是大量存在的，例如，１８４７年法国天文学家Delaunay花了１０年的时间推导出了月球的轨道公式，又花了另外１０年来检查他的结果，并于１８６７年将其公布于世．其结果是非数值的，主要部分都是以公式的形式给出，全部结果长达１２８页之多．另一个有名的例子是１９世纪海王星的发现．人们发现天王星的实际运行轨道与当时的理论不符，猜想它可能受到其他未知行星的干扰．经过计算，当然包含大量的公式推导，并在计算结果的指导下进行观测，终于发现了海王星．这些计算的特点都是将计算对象代数化，然后利用代数中的理论及算法进行计算．人们把这种研究可代数化的数学对象的计算理论与方法的学科，或者说符号计算与代数计算的学科称为计算机代数，或者数学机械化．简而言之，计算机代数是计算机科学与数学交叉融合的产物，是符号、代数算法的设计、分析、实现和应用的学科．作为代数算法，它有简单的形式界定（formalspecification），有建立在相应数学理论基础之上的正确性证明和渐进时间界限的估计（即所谓计算的复杂性）．而且代数对象可在计算机的内存中准确地表现出来，因而代数计算可以精确地进行；因为计算是精确的，所以可用的代数算法都必定在有限步内完成运算．由于代数算法都是建立在数学基础之上的，所以代数及代数几何的发展为代数计算提供了广泛的数学理论基础，同时代数计算的研究也促进了代数理论，特别是构造性代数及代数几何理论的发展．近年来产生了计算交换代数与计算代数几何等新的研究领域，或者可以说是更为一般的数学机械化的新的研究领域．·i·\n如果我们把计算数学理解为研究在计算机上进行计算的数学理论与算法的学科分支，那么以往的计算数学主要研究数值算法的设计、分析、实现和应用及相应的数学理论，而计算机代数则研究符号计算的相关理论，是计算数学发展的新阶段．与数值计算相比，代数计算要求计算机有高速度与大存储量，所以它与计算机技术发展的联系更为密切．计算机代数作为新的计算工具，在理论物理、高能物理、天体力学、化学化工、机械学、机器人设计以及计算机的各种应用领域都有广泛的应用，同时也成为数学教学与数学研究的重要工具．在实际应用中，符号计算、公式推演或者说代数计算的问题很多，而且门类繁杂，在理论基础方面几乎涉及数学的各个分支，在应用方面涉及各个行业领域．然而由于计算机的计算速度、存储空间限制等诸多原因，这类计算的自动化过程进展十分缓慢，直到１９５３年，Kahrimanian与Nolan才分别在他们的论文中给出第一个计算形式微分的计算机程序，其后这类计算的自动化进程一直徘徊不前．随着计算机技术的迅速发展，高性能计算机的普及，以及科技工程等实际问题对符号计算的迫切需要，人们开始重视这类计算的理论与算法的研究．经过近３０年的发展，符号计算的研究与应用才算真正得到长足的进步．计算机代数是从２０世纪６０年代中期发展起来的，与此同时，一些学术机构和团体也相继成立．比较有名的如ACM（theassociationforcomputingmachinary）的SIGSAM（specialinterestgrouponsymbolicandalgebraicmanipulation），该团体还出版了季刊“SIGSAMBulletin”；此外还有欧洲的SAME（symbolicandalgebraicmanipulationinEu唱rope），日本与前苏联也成立了相应的研究机构；我国也在中国科学院建立了数学机械化中心，简称MMRC．世界各国对符号计算的研究都非常重视，相继设立了一些大型的研究项目，如原欧共体（现称欧盟）的POSSO计划及其后继FRISCO，我国“八五”期间的攀登计划项目“机器证明及其应用”，“九五”期间的９７３项目“数学机械化与自动推理平台”等．这些项目在理论与应用方面，例如几何定理证明与发现、代数方程、微分方程求解、实多项式系统问题以及诸多计算机应用领域都取得了丰硕的成果．国际上有关计算机代数的学术交流活动也十分活跃，比如定期举行的综合性系列国际学术会议有ISSAC（internationalsymposiumonsymbolicandalgebraiccomputation），ASCM（asiansymposiumoncomputermathematics），此外还有许多其他比较专门的系列国际会议，在互联网上用Symbolic，Algebraic，Geometric，Computation等关键词搜索，就可以获得相应的信息，这里不再赘述．计算机代数方向已出版了专门的国际学术刊物“JournalofSymbolicComputation”，此外，“SIAMJournalonComputer”，“ACMTransactionsonMathematicalSoftware”也刊登了这方面的论文；Springer的丛书“LectureNotesinComputerScience”中陆续出版了不少计算机代数的专集；自２０世纪９０年代起，已陆续出版了计算交换代数、计算代数几何、算法代数等方面的专著．与数值计算不同，代数算法的研究与计算机代数的软件系统的研制几乎是同时的．随着理论研究的深入，一些多层次、多用途的计算机代数软件，例如比较早期的·ii·\nμ唱Math（Derive），Reduce，后起之秀Mathematica，Maple，我国自行开发的MMP以及比较专业的CoCoA等，也相继开发出来．有些计算机代数软件还允许用户定义抽象的代数结构（例如环和代数），并对其元素进行操作，具有这一功能的软件有Axiom等．经３０余年的发展，许多计算机代数系统已投入使用，这些系统的功能日益强大，效率不断提高．这些代数系统的主要功能如下。１）提供一基本命令集，可使机器做许多复杂的计算，包括数值的和符号的计算．这个特点使得代数系统具有可用性．２）提供一种能定义高层命令或扩展原始命令的程序语言，使得系统具有可开发性．现有的代数系统可处理的问题如下．１）数的计算，包括整数、有理数、实数和复数的计算，且既可进行浮点计算又可进行精确计算．２）多项式、有理式的各种计算．３）矩阵的计算，且其元素可为符号的．４）数学分析中微分、积分、级数和微分方程等计算．５）其他各种代数问题的计算．利用这些计算机代数系统，已经基本上可以解决实际中出现的绝大部分问题。当然对某些问题其效能还不是很高，尚有待于进一步的研究和完善．这些软件已经发挥了很大的作用，例如，美国西雅图波音科学研究实验室为利用Delaunay的结果推导人造卫星的运行轨道，使用计算机代数系统重新推导，结果发现了３处错误．又如，人们利用计算机代数系统验算了早期的不定积分表，发现错误高达１／５～１／４．在数学教育中，已经可以使用计算机证明与发现几何定理．由于计算机代数在科学研究与工程技术中越来越广泛的应用，每个科研工作者，包括数学、计算数学、计算机科学以及其他领域的研究人员，必须掌握计算机代数的基本知识与熟练使用相关的计算机代数软件．为适应形势发展的需要，我们从１９９２年开始为吉林大学计算专业的研究生和本科生开设计算机代数课程，并在１９９７年由吉林大学出版社出版了计算机代数教材，讲述计算机代数的基本原理与算法．经过几年的教学实践，发现原书有很多错误与疏漏之处，实感确有修订之必要，在吉林大学教材科和科学出版社的支持下，我们进行了修订工作．本次修订主要是修正原书的错误，补充疏漏和一些不完善的地方．考虑到作为计算机代数的入门教材，不宜过多地引入新的内容，因此本次修订未对结构做调整．在学习计算机代数的过程中，对计算数学、抽象代数以及交换代数等有关基本知识有一些必要的了解是大有裨益的．考虑到一般学生可能没有学过抽象代数，我们在第１章及附录中介绍了必要的抽象代数与交换代数的基本内容．此外，因为计算机代数中有些算法理论涉及比较深刻的专门知识，我们感到要想做到教材内容的自包含是比较困难的，在有些情况下不得不放弃某些算法所依据的理论而仅仅描述算法本身．虽然计算机代数所包含的内容十分广泛，但由于篇幅所限，本书仅仅选取了与多项式问题紧密相关的那些内容的基本部分．·iii·\n张树功对第１～６章及附录A进行修订；附录B由雷娜和刘停战编写．冯果忱教授一直对本书的编写给予了关心和鼓励，在此表示感谢．本书是作者在计算机代数教学方面的一个尝试，由于作者水平有限，不可避免地存在这样或那样的错误和不足，殷切希望各位专家和同行们提出宝贵意见和建议．·iv·\n目录第1章代数基本知识与大整数的处理⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１１．１代数基本知识⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１１．１．１基本概念⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１１．１．２可除性与整环中的分解⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯３１．２大整数的表示与比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯７１．２．１大整数的表示⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯７１．２．２大整数的比较⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯９１．３大整数的运算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１０１．３．１大整数的加减法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１０１．３．２乘法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１１１．３．３大整数的快速乘法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１３１．３．４除法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１４１．３．５最大公因子与最小公倍式的计算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１８１．３．６有理数的表示及计算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１９１．４有限域上的运算与孙子剩余定理⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２１１．４．１有限域上的运算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２１１．４．２整数的p唱adic表示⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２２１．４．３孙子剩余定理⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２４练习⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２５第2章多项式代数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２７２．１一元多项式环⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２７２．１．１基本概念与结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２７２．１．２域上的一元多项式环⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２８２．１．３环上的一元多项式环⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯３３２．２多元多项式环⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯３８２．２．１基本概念与结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯３８２．２．２单项序与多项式的约化⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯３８２．３Groebner基⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯４４２．３．１Groebner基的定义与基本性质⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯４４２．３．２Buchberger算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯４８２．３．３Groebner基的应用⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯５１２．３．４多项式的理想唱adic表示⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯５５２．４吴方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯５６２．４．１升列、基列与特征列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯５７２．４．２多项式方程组求解⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯６２·v·\n２．４．３定理机械化证明⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯６４练习⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯６６第3章多项式最大公因子的计算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯６８３．１多项式的余式序列与结式⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯６８３．１．１多项式余式序列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯６８３．１．２结式⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯７１３．２模方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯７４３．３多元多项式的最大公因子⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯８０３．３．１Euclid方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯８０３．３．２模方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯８２３．４试探方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯８７３．４．１算法的描述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯８７３．４．２赋值点的选取⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯８８３．５实一元多项式系统的化简⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯９４练习⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯９８第4章多项式的因式分解⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１００４．１无平方分解⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１００４．２Berlekamp算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１０２４．３Hensel提升方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１０８４．４多元多项式的因式分解⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１１３４．５３L方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１１８４．５．１格与约化基⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１１８４．５．２格与整除关系⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１２４４．５．３分解算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１２８４．６有理式部分分式展开⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１３１练习⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１３３第5章形式积分⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１３５５．１引言⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１３５５．２有理函数的形式积分⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１３６５．２．１有理函数积分的存在性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１３６５．２．２Hermite与Horowitz方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１３６５．２．３对数部分的计算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１３９５．３初等函数的积分⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１４２５．３．１对数函数的积分⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１４３５．３．２指数函数的积分⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１５０５．３．３混合函数的积分⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１５４练习⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１５７第6章常微分方程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１５８６．１一阶常微分方程的Risch方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１５８·vi·\n６．２二阶齐次常微分方程的Kovacic方法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１６２６．２．１基本概念与结果⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１６２６．２．２情形１算法的描述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１６４６．２．３情形２算法的描述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１６７６．２．４情形３算法的描述⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１６９６．２．５任意阶常微分方程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１７１６．３常微分方程的渐进解⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１７２６．３．１奇异性分类⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１７２６．３．２Frobenius算法⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１７４练习⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１７５附录A代数基础知识⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１７７A．１理想、环同态与商环⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１７７A．１．１理想⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１７７A．１．２环同态与商环⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１７８A．２域的扩张⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１７９A．３一些相关不等式⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１８２A．３．１Hadamard不等式⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１８２A．３．２Cauchy不等式⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１８２A．３．３Landau不等式⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１８３A．３．４Landau唱Mignotte不等式⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１８３附录BMaple9使用简介⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１８５B．１工作环境⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１８５B．２基本代数运算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１８７B畅２畅１整数和有理数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１８７B畅２畅２无理数和浮点数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１８９B畅２畅３代数数和复数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１８９B畅２畅４变量和常量⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１９１B畅２畅５函数和表达式⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１９３B畅２畅６Groebner工具包⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１９５B．３微积分运算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１９７B畅３畅１极限和连续性⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１９７B畅３畅２导数和微分⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１９７B畅３畅３积分运算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１９８B．４复合数据类型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１９９B畅４畅１序列⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１９９B畅４畅２集合⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯１９９B畅４畅３有序表⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２００B．５线性代数⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２０１B畅５畅１矩阵基本运算⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２０１B畅５畅２矩阵的初等变换⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２０３·vii·\nB畅５畅３特征值、特征向量和相似标准型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２０５B．６Maple绘图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２０６B畅６畅１二维图形绘制⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２０６B畅６畅２三维图形绘制⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２０９B畅６畅３图形动画的制作⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２１３B．７方程求解⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２１４B畅７畅１代数方程求解⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２１４B畅７畅２微分方程求解⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２１６B．８编程初步⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２１７B畅８畅１箭头操作符⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２１７B畅８畅２简单子程序⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２１７B畅８畅３基本程序结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２１８参考文献⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯２２２·viii·\n第2章多项式代数本书的内容基本上都是围绕着计算机代数中多项式问题展开讨论的，因此我们首先应该对有关多项式的各种问题，如多项式的表示、运算性质等有必要的了解．在本章我们先介绍多项式代数的基本内容，然后对当前计算机代数领域中最流行的两种基本研究工具，或者说是研究方法———Groebner基方法与吴方法———进行简要的介绍．２畅１一元多项式环2畅1畅1基本概念与结果设R为一交换环，x为一未定元，用R［x］表示R上的一元多项式全体，即R［x］中元素都具有形式mi钞aix，i＝０其中ai∈R，m为非负整数．对于给定的多项式miA＝钞aix，i＝０其次数定义为非零系数的下标最大者，记作deg（A）．每个非零多项式都可以写成规范形式miA＝钞aix，am≠０．i＝０如果一个多项式的所有系数都是零，则称其为零多项式，且记之为０．零多项式不定义次数．如果一多项式的次数为０，则称该多项式为常数多项式．若一多项式A的次数为nnndeg（A）＝n，A中的乘幂x的系数为an，则称anx为A的领式，记为lm（A）＝anx．nnan称为A的领项系数，记作lc（A）＝an．x称为A的领项，记为lt（A）＝x．如果对一多项式A，有lc（A）＝１，则称A为首一的．交换环R中的加法运算和乘法运算可以自然地扩展为R［x］上的加法和乘法，如下所示．mnii若A＝钞aix，B＝钞bix，则多项式加法定义为i＝０i＝０max（m，n）iC（x）＝A（x）＋B（x）＝钞cix，i＝０其中ci＝ai＋bi，i＝０，１，⋯，max（m，n）．当式中的i大于m或n时，相应的ai或bi取为０．类似地，多项式的乘法则定义为m＋nkD（x）＝A（x）B（x）＝钞dkx，k＝０其中dk＝钞aibj．关于R［x］的代数结构，有如下定理．i＋j＝k·２７·\n定理2畅1畅1１）若R为交换环，则R［x］亦为交换环，且以零多项式与常数多项式１为加法与乘法单位元．２）若D为整环，则D［x］亦为整环，其可逆元恰为D中的可逆元．３）若D为唯一分解整环，则D［x］也是唯一分解整环，其不可约元就是那些相对于D不能分解的多项式．４）如果D是Euclid整环，则D［x］为唯一分解整环，但未必是Euclid整环．５）若K是一域，则在赋值v（A）＝deg（A）之下，K［x］是一Euclid整环．整环上非零多项式的次数函数关于多项式运算有下列关系．１）deg（A＋B）≤maxdeg（A），deg（B）．２）deg（AB）＝deg（A）＋deg（B）．2畅1畅2域上的一元多项式环设K为一域，则由定理２畅１畅１，K［x］是Euclid整环．对于任意给定的多项式A，B∈K［x］，B≠０，存在多项式Q，R，使得A＝QB＋R，（２畅１畅１）其中deg（R）＜deg（B），或R＝０，式（２畅１畅１）也称为带余除法或Euclid除法．Q称为A除以B的商，记作Q＝quo（A，B），R称为A除以B的余式，记作R＝rem（A，B）．如果在带余除法中余式R＝０，则称B整除A，记作B|A．命题2畅1畅1带余除法中的Q和R是唯一的．证明设有R１，Q１以及R２，Q２，使得A＝QiB＋Ri，Ri＝０或deg（Ri）＜deg（B），i＝１，２畅两式相减则有（Q１－Q２）B＝R２－R１畅我们断言上式中Q１－Q２与R２－R１都是零多项式．不然计算次数得deg（Q１－Q２）＋deg（B）＝deg（R２－R１）．因为deg（Ri）＜deg（B），i＝１，２，且次数函数是非负的，于是deg（B）＞maxdeg（R１），deg（R２）≥deg（R２－R１）＝deg（Q１－Q２）＋deg（B）≥deg（B）．这个矛盾说明只能有Q１＝Q２，R１＝R２，即带余除法的商和余式都是唯一的．当给定多项式nmiiA（x）＝∑aix，B（x）＝∑bix，an≠０，bm≠０，i＝０i＝０则A除以B的商Q与余式R可用下列算法求得．算法2畅1畅1带余除法：·２８·\nnmiiInputA＝钞aix，B＝钞bix；i＝0i＝0OutputQ，RsuchthatA＝QB＋R；ifn＜mthenreturnQ＝0，R＝A；elseR：＝A；Q：＝0；N：＝deg（R）－m；whileN≥0doNR：＝R－lc（R）／lc（B）xB；NQ：＝Q＋lc（R）／lc（B）x；N：＝deg（R）－m；returnQ，R；３２２例2畅1畅1设A＝３x＋x＋x＋５，B＝５x－３x＋１，求quo（A，B），rem（A，B）．因为deg（A）＝３＞deg（B）＝２，按照算法２畅１畅１有３１４２２R１＝A－xB＝x＋x＋５，５５５３３Q１＝０＋x＝x，５５１４０５２１１１R２＝R１－xB＝x＋，２５２５２５１４３１４Q２＝Q１＋＝x＋，２５５２５即有A＝QB＋R，３１４５２１１１其中Q＝x＋，R＝x＋．５２５２５２５我们知道，当K为域时，K［x］是Euclid整环，但对一般的整环D，哪怕是Euclid整环，D［x］也未必是Euclid整环．例2畅1畅2整数环ZZ［x］却不是Euclid整环．取例２畅１畅１中的A，B，如果我们试图求Q＝q１x＋q０，R＝r１x＋r０∈Z［x］，使得３２２３x＋x＋x＋５＝（５x－３x＋１）（q１x＋q０）＋（r１x＋r０）．则可导出３＝５q１，１＝５q０－３q１，１＝q１－３q０＋r１，５＝q０＋r０．显然上方程组并没有整数解．本例说明Z［x］不是Euclid整环．而且本例也表明，要想进行多项式的除法，系数的运算必须在域里进行．·２９·\n例2畅1畅3在域K上的多项式整环K［x］中，多项式x没有乘法逆．因为如果它有乘法逆，比如说Q（x），则有xQ（x）＝１畅取次数则有deg（x）＋deg（Q）＝１＋deg（Q）＝deg（１）＝０．由此得deg（Q）＝－１，这是不可能的．故x没有乘法逆．设A∈K［x］为非零多项式，则lc（A）≠０，令n（A）＝A／lc（A），则n（A）是首一多项式．我们称其为A的正规部分．设A，B∈K［x］，C，D∈K［x］均为A，B的最大公因子，则C，D可以相差域K中的一个常数倍．但是如果我们取其正规部分，则最大公因子是唯一的．若D为A，B的最大公因子，由定理１畅１畅３，存在W，V∈K［x］使得WA＋VB＝D，（２畅１畅２）上述方程称为多项式Diophantos方程．我们感兴趣的是，对于哪些多项式C∈K［x］，存在W，V∈K［x］，使得WA＋VB＝C（２畅１畅３）成立．这种方程求解问题在后面的许多算法中要遇到．显然若上述方程有解，则必有D|C．定理2畅1畅2设K为域，A，B∈K［x］为给定的非零多项式，D＝gcd（A，B）∈K［x］，则对任何满足D|C的多项式C∈K［x］，存在唯一的W，V∈K［x］，使得WA＋VB＝C，（２畅１畅４）且deg（W）＜deg（B）－deg（D）．（２畅１畅５）此外，如果还有deg（C）＜deg（A）＋deg（B）－deg（D），则deg（V）＜deg（A）－deg（D）．（２畅１畅６）～～证明因为D＝gcd（A，B），则存在W，W∈K［x］使得～～WA＋BV＝D．因为D|C，记U＝quo（C，D），则有～～WUA＋VUB＝C．（２畅１畅７）～将WU除以B关于D的余因子B／D，得～WU＝QB／D＋R，（２畅１畅８）其中deg（R）＜deg（B／D）＝deg（B）－deg（D）．将式（２畅１畅８）代入式（２畅１畅７）得～RA＋（VU＋QA／D）B＝C，（２畅１畅９）～于是W＝R，V＝VU＋QA／D为所求．下面证其唯一性．设有Wi，Vi，i＝１，２，满足WiA＋ViB＝C，且deg（Wi）＜deg（B）－deg（D）．（２畅１畅１０）两式相减得（W１－W２）A＝－（V１－V２）B，（２畅１畅１１）·３０·\n记B１＝B／D，A１＝A／D，则A１，B１互素，于是B１|（W１－W２）．但是deg（B１）＝deg（B）－deg（D），再注意式（２畅１畅１０）可知必有W１－W２＝０，于是由式（２畅１畅１１）又得V１－V２＝０．现在假设C还满足deg（C）＜deg（A）＋deg（B）－deg（D），我们来证式（２畅１畅６）成立．将式（２畅１畅４）写成V＝（C－WA）／B，则有deg（V）＝deg（C－WA）－deg（B）．（２畅１畅１２）如果deg（C）≥deg（WA），则由式（２畅１畅１２）及假设知deg（V）≤deg（C）－deg（B）＜deg（A）－deg（D）．如果deg（C）＜deg（WA），则由式（２畅１畅１２）及式（２畅１畅５）知deg（V）≤deg（WA）－deg（B）＝deg（W）＋deg（A）－deg（B）＜deg（A）－deg（D）．以上定理说明，如果D|C，则Diophantos方程肯定有解，且可以要求deg（W）＜deg（B／D）或者deg（V）＜deg（A／D）之一成立；如果进一步要求deg（C）＜deg（lcm（A，B）），则deg（W）＜deg（B／D）与deg（V）＜deg（A／D）同时成立．前面的定理讨论的Diophantos方程是两项的，我们自然要问，对多项的情形是否也有类似结果．这个问题和孙子剩余定理有关，我们先来看简单情形．设a１，a２，⋯，an是K中两两互异的点，考虑这些点上的Lagrange插值问题，则可得n个插值基函数x－ajLi（x）＝∏，i＝１，⋯，n．j≠iai－aj由计算数学中的结论可知：次数小于n的多项式A在n个互异点上的插值都是精确的，而且对任一多项式B，其插值多项式为A当且仅当B（ai）＝A（ai）．上面的话可以转述成：若A∈K［x］且deg（A）＜n，则有A（x）＝A（a１）L１（x）＋⋯＋A（an）Ln（x）．（２畅１畅１３）式（２畅１畅１３）可以看成是Diophantos方程的推广．对于每个次数小于n的多项式A，由式（２畅１畅１３）可知其唯一地对应着一组数｛A（a１），⋯，A（an）｝，而每个A（ai）又可表示成A（ai）＝rem（A，x－ai），或者写成A≡A（ai）mod（x－ai）．n对于任意给定的多项式B∈K［x］，如果B关于函数F＝∏（x－ai）的余式RB＝A，i＝１则B（ak）＝quo（B，F）F（ak）＋RB（ak）＝RB（ak）＝A（ak）．·３１·\n即B≡A（ak）mod（x－ak），k＝１，⋯，n．（２畅１畅１４）反之，如果某一多项式B满足（２畅１畅１４），且R＝rem（B，F），则R（ak）＝B（ak）＝A（ak），k＝１，⋯，n．因为R，A的次数都小于n，故必有R＝A．这个事实用代数的语言叙述出来就是：对于任意给定的多项式B，B≡AmodF当且仅当B≡A（ak）mod（x－ak），k＝１，⋯，n．这个结果更一般的形式如下。定理2畅1畅3（孙子剩余定理的多项式形式）设A１，A２，⋯，An为两两互素的多项式，｛B１，B２，⋯，Bn｝为给定的多项式组，则存在一多项式A，使对任意的多项式B，B满足nB≡Amod∏Ai，（２畅１畅１５）i＝１当且仅当B≡BimodAi，i＝１，⋯，n．（２畅１畅１６）证明先构造多项式A．记Li＝∏Aj，则因Ai两两互素可知Li，Ai互素．由定理j≠i２畅１畅２知，存在Wi，Vi使得１＝WiLi＋ViAi，deg（Wi）＜deg（Ai），deg（Vi）＜deg（Li）．（２畅１畅１７）对式（２畅１畅１７），关于Ai取同余得WiLi≡１modAi，（２畅１畅１８）n而显然有WiLi≡０modAj，i≠j．取A＝∑BiWiLi，则易见有i＝１A≡BimodAi，i＝１，⋯，n．（２畅１畅１９）n先证必要性．若有B使得式（２畅１畅１５）成立，则B－A可被∏Ai整除，当然也可i＝１被Ai整除，亦即B≡AmodAi成立．结合式（２畅１畅１９）则得式（２畅１畅１６）．再证充分性．反之，设式（２畅１畅１６）成立，则由式（２畅１畅１９）可知B≡AmodAi，ni＝１，⋯，n．亦即B－A可被Ai整除，但Ai是两两互素的，故B－A可被∏Ai整除，i＝１即式（２畅１畅１５）成立．若A１，A２，⋯，An为两两互素的给定多项式，B１，⋯，Bn为另一组给定多项式，我们n来求一个次数不超过deg（∏Ai）的多项式B，使得B≡BimodAi，i＝１，⋯，n．由孙i＝１子剩余定理的证明，易见B可取为nB＝∑BiWiLi，（２畅１畅２０）i＝１但是这样构造的多项式未必满足次数的要求，类似于式（２畅１畅１７）的处理，令Ci＝rem（BiWi，Ai），则deg（Ci）＜deg（Ai），于是可取·３２·\nnB＝∑CiLi．（２畅１畅２１）i＝１再注意到Li的定义，则有deg（B）＜deg∏Aj．j上述问题实际上是一个广义的多项式插值问题．在孙子剩余定理中，要求Ai两两互素的目的是为了保证存在Wi，使得式（２畅１畅１８）成立，这样对任何Bi，都有BimodAi，BiWiLi≡０modAj，j≠i．当Ai不是两两互素时，只要能求得W珨i使其满足BimodAi，W珨iLi≡０modAj，j≠i，n取B＝∑W珨iLi，则仍有B≡BimodAi成立．i＝１2畅1畅3环上的一元多项式环２畅１畅２节我们讨论了域上的一元多项式环，这样的环是Euclid整环．而在Euclid整环上是可以进行带余除法运算的，这使得我们能够容易地处理一些给定的问题．但是有时很多研究对象不是Euclid整环，比如说整数环上的一元多项式环．又如对某一多元多项式，当把它看成某一个未定元的多项式时，它的系数是其他未定元的多项式，这种观点下的多元多项式全体就是一个环上的多项式环．基于问题的需要，我们必须讨论环上的多项式环．设D为一整环，由定理２畅１畅１，D［x］仍为一整环．有时为了使D［x］成为UFD，我们也要求D为UFD．下面我们来研究这种环上的多项式及其运算．先来看一个例子．例2畅1畅4设A，B∈Z［x］，其中３２A（x）＝４８x－８４x＋４２x－３６，３２B（x）＝－４x－１０x＋４４x－３０．它们可分解为２A（x）＝２×３×（２x－３）（４x－x＋２），B（x）＝（－１）×２×（２x－３）（x－１）（x＋５）．于是gcd（A，B）＝２（２x－３）＝４x－６畅但是在Q［x］中考虑问题时，A，B的最大公因子则为３gcd（A，B）＝x－．２造成这个差别的原因是：在域Q数的公因子；而在Z对A∈D［x］，如果lc（A）为D中规范元，则称A为规范多项式，可取规范多项式－１为D［x］中的规范元．对一般A∈D［x］，易见u（lc（A））A为规范多项式，为方便计，·３３·\n简记u（lc（A））为u（A）．ki定义2畅1畅1设D为UFD，A＝∑aix∈D［x］．A的容度（content），记作i＝０cont（A），定义为cont（A）＝gcd（a０，⋯，ak）．若cont（A）＝１，且lc（A）为规范元，则称A是本原的（primitive）．A的本原部分（primitivepart）记作pp（A），定义为pp（A）＝－１u（A）A／cont（A）．为方便计，定义cont（０）＝pp（０）＝０．定理2畅1畅4（Gauss引理）设D为UFD，A，B∈D［x］，则cont（AB）＝cont（A）cont（B），（２畅１畅２２）pp（AB）＝pp（A）pp（B）．证明先证若cont（A）＝cont（B）＝１，则cont（AB）＝１畅不然，则应有不可约元dnm整除cont（AB）．又设A＝anx＋⋯＋a０，B＝bmx＋⋯＋b０，且有r≤n，s≤m，使得d|a０，⋯，d|ar－１，d嘲ar，d|b０，⋯，d|bs－１，d嘲bs．考虑AB的r＋s次项系数，则有cr＋s＝⋯＋ar－１bs＋１＋arbs＋ar＋１bs－１＋ar＋２bs－２＋⋯由d|bs－１，⋯，d|b０及d|cr＋s可推知d|arbs．因为d是不可约元，必有d|ar或d|bs，矛盾．对一般情形，可将AB表示成AB＝u（A）u（B）cont（A）cont（B）pp（A）pp（B），由前段证明知pp（A）pp（B）是本原的，从而cont（AB）＝cont（A）cont（B），再由本原部分的定义即知pp（AB）＝pp（A）pp（B）．推论2畅1畅1设D为UFD，A，B∈D［x］，则cont（gcd（A，B））＝gcd（cont（A），cont（B）），（２畅１畅２３）pp（gcd（A，B））＝gcd（pp（A），pp（B））．证明设D＝gcd（A，B），A＝DB１，B＝DB２，由定理２畅１畅４cont（A）＝cont（D）cont（B１），cont（B）＝cont（D）cont（B２）．～～～令d＝gcd（cont（A），cont（B）），于是cont（D）|d．另一方面，若有珔d使得d＝cont（D）珔d，则珔d同时整除cont（B１）和cont（B２），从而珔dD|A，珔dD|B，～～故珔dD|D，说明珔d为可逆元，但d为规范元，故必d＝cont（D）．类似地，可证另一结果．定理２畅１畅４与推论２畅１畅１无非是说本原多项式的乘积与最大公因子仍为本原的．这些结果无论对一元问题还是对多元问题都十分重要．例2畅1畅5对例２畅１畅４中的多项式３２A（x）＝４８x－８４x＋４２x－３６，３２B（x）＝－４x－１０x＋４４x－３０，有cont（A）＝６，·３４·\n３２pp（A）＝８x－１４x＋７x－６２＝（２x－３）（４x－x＋２）；cont（B）＝２，３２pp（B）＝２x＋５x－２２x＋１５＝（２x－３）（x－１）（x＋５）．容易看出，有gcd（A，B）＝gcd（cont（A），cont（B））gcd（pp（A），pp（B））．因为我们这里讨论的环不是Euclid整环，而带余除法在非Euclid整环内不能进行，可是很多问题又需要进行除法计算，这就要求我们将除法推广，下面介绍的伪除就是这样一种运算．我们还是先来看一个具体的例子，这对问题的理解是有帮助的．例2畅1畅6设３２A（x）＝３x＋x＋x＋５，２B（x）＝５x－３x＋１畅它们在Q［x］中的带余除法为３２３１４２５２１１１３x＋x＋x＋５＝x＋５x－３x＋１＋x＋．５２５２５２５２如果在等式两端都乘以５，则两端都变成整系数多项式．如果在Z［x］中考虑问题，则除法不能进行．但考虑５A除以B，计算一步则有２５A＝３xB＋（１４x＋２x＋２５）扯３xB＋R１，又lc（R１）不能被lc（B）整除，再考虑５R１除以B，计算一步得５R１＝１４B＋（５２x＋１１１）扯１４B＋R２畅注意R２的次数已经小于B的次数，于是２５A＝５（３xB＋R１）＝１５xB＋１４B＋R２＝（１５x＋１４）B＋R２畅mnii现在我们来考虑一般情形．设A（x）＝∑aix，B（x）＝∑bix∈D［x］，m≥n且i＝０i＝０bn≠０．令m－nR１（x）＝bnA（x）－amxB（x）m－１＝（bnam－１－ambn－１）x＋⋯（２畅１畅２４）m－１（１）i则显然R１∈D［x］．记R１（x）＝∑rix，再令i＝０（１）m－n－１R２（x）＝bnR１（x）－rm－１xB（x）（１）（１）m－２＝（bnrm－２－rm－１bn－１）x＋⋯（２畅１畅２５）m－k（k）i可见仍然有R２∈D［x］．这样继续下去，记Rk（x）＝∑rix，在进行m－n步以i＝０·３５·\n后，得（m－n－１）Rm－n（x）＝bnRm－n－１（x）－rn＋１xB（x）（m－n－１）（m－n－１）n＝（bnrn－rn＋１bn－１）x＋⋯（２畅１畅２６）（m－n）Rm－n＋１（x）＝bnRm－n（x）－rnB（x）（m－n）（m－n）n－１＝（bnrn－１－rnbn－１）x＋⋯（２畅１．２６）′m－nm－n－１m－n－（m－n－１）将第一式乘以bn，第二式乘以bn，⋯⋯，第m－n式乘以bn＝bn，最０后一式乘以bn＝１畅再将所有的式子相加并消去相同的项，得m－nm－n＋１m－n－i（i）m－n－iRm－n＋１＝bnA－B钞bnrm－ix．（２畅１畅２７）i＝０m－nm－n－i（i）m－n－i由前述推导可知，若记R＝Rm－n＋１，Q＝钞bnrm－ix，则有以下定理．i＝０定理2畅1畅5设A，B∈D［x］，deg（A）≥deg（B）且lc（B）＝b≠０，则存在Q，R∈D［x］满足deg（R）＜deg（B）或R＝０，使得lbA＝QB＋R，（２畅１畅２８）其中l＝deg（A）－deg（B）＋１畅上述定理中所叙述的这种性质称为伪除（pseudo唱division）性质．我们称定理中的Q为A除以B的伪商，记作Q＝pquo（A，B）．称定理中的R为A除以B的伪余，记作R＝prem（A，B）．分析定理证明可知，式（２畅１畅２８）中的l有时可以取得小于（deg（A）－deg（B）＋１），（k）（k）这是因为在证明中我们始终假定bnrm－k－１－rm－kbn－１≠０．倘若这些系数有等于０的，则整个计算步数就会减少，因此最终bn的方次也可以降低，当然相应的伪商和伪余也会随之变化．在这种意义上说，伪商和伪余是不唯一的．但是对使式（２畅１畅２８）成立的最小的l来说，伪商和伪余是唯一的．因为倘若有Q１，Q２，R１，R２，使式（２畅１畅２８）成立，则两式相减得（Q１－Q２）B＝R２－R１，比较两端的次数就会得到Q１＝Q２，R２＝R１畅有了上述的伪除概念，我们就可以讨论D［x］中的最大公因子的计算问题了．定理2畅1畅6设D为UFD．A，B∈D［x］为本原多项式，且deg（A）≥deg（B），lc（B）＝b≠０．又设Q，R为定理２畅１畅５所述的伪商和伪余，则有gcd（A，B）＝gcd（B，pp（R））．（２畅１畅２９）证明由伪除性质有lbA＝QB＋R．容易证得lgcd（bA，B）＝gcd（B，R）．（２畅１畅３０）由Gauss引理llgcd（bA，B）＝gcd（b，１）gcd（A，B）＝gcd（A，B）．（２畅１畅３１）这里我们利用了A，B为本原多项式的假设．再由Gauss引理又有gcd（B，R）＝gcd（１，cont（R））gcd（B，pp（R））＝gcd（B，pp（R））．（２畅１畅３２）·３６·\n综合式（２畅１畅３０）～式（２畅１畅３２）即得定理结论．根据上述定理的结论，对给定的本原多项式A，B，deg（A）≥deg（B），为求其最大公因子，可构造如下的伪余多项式序列R０＝A，R１＝B，Rk＝pp（prem（Rk－２，Rk－１）），k＝２，３，⋯注意到序列deg（R１）＞deg（R２）＞⋯＞deg（Rk）＞⋯，故序列R０，R１，⋯，Rk，⋯必终止于某Rl，于是由定理２畅１畅６可知，有Rl＝gcd（A，B）．例2畅1畅7设３２A（x）＝４８x－８４x＋４２x－３６，３２B（x）＝－４x－１０x＋４４x－３０．３２３２令R０＝pp（A）＝８x－１４x＋７x－６，R１＝pp（B）＝２x＋５x－２２x＋１５，其余计算结果为２R２＝３４x－９５x＋６６，R３＝２x－３，R４＝０．最终得gcd（A，B）＝gcd（cont（A），cont（B））gcd（pp（A），pp（B））＝２（２x－３）＝４x－６畅对于具体的多项式环Z［x］，会不会存在这样的问题：给定多项式A，B∈Z［x］，它们在Z［x］与Q［x］上有不同次数的最大公因子？这种担心是不必要的．下面就来说明这个问题．设A，B在Q［x］的最大公因子为D，则有A１，B１∈Q［x］使得A＝DA１，B＝DB１畅去分母得d１A＝D珚A珚１，d２B＝D珚B珚１畅由Gauss引理知pp（A）＝pp（D珚）pp（A珚１），pp（B）＝pp（D珚）pp（B珚１）．～即pp（D珚）是pp（A），pp（B）的因子，因为pp（D珚）的次数和D的次数相同，且若D为～～A，B在Z［x］上的最大公因子，则pp（D珚）|D，故可知D的次数不超过D的次数．反之，～～易见D在Q［x］上整除D，即D的次数又不超过D的次数，从而二者相等．并且由上～面的推导可以看出，D和D实际只相差一Q综上所述，有如下定理．定理2畅1畅7多项式A，B在Z［x］中有非平凡公因子当且仅当它们在Q［x］中有非平凡的公因子．·３７·\n２畅２多元多项式环2畅2畅1基本概念与结果在符号计算中，人们最感兴趣并且实际问题涉及最多的多项式环是整数环、有理数域以及有限域上的多元多项式环，因此设计多元多项式问题的有效算法是符号计算的中心课题之一．在讨论各种算法之前，先对多元多项式环的基本概念以及基本结果有一些了解是十分必要的．设R为一交换环，x１，x２，⋯，xn为n个未定元．有如下形式的有限和iiiA（x１２n１，⋯，xn）＝钞ai１，i２，⋯，inx１x２⋯xn，（２畅２畅１）i，i，⋯，i１２n其中ai，i，⋯，i∈R，称为R上的n元多项式，其中每个和项称为一个单项式．特别地，１２n如果每个ai，i，⋯，i都等于０，则称其为零多项式；而R上的每个元都是一个常数多项１２n式．R上的所有n元多项式全体记为R［x１，⋯，xn］，或者简记作R［X］，其中X＝（x１，⋯，xn）．iii因为每个单项x１２n１x２⋯xn都唯一地对应一个n元有序非负整数组i＝（i１，i２，⋯，in），因此我们可以简单地记其为iiiiX＝x１２n１x２⋯xn，（２畅２畅２）ii并称i＝（i１，i２，⋯，in）为单项X的多重次数，简记为md（X）＝i．因此式（２畅２畅１）可以简记为iA（X）＝钞aiX．（２畅２畅３）iniiii对单项X，记deg（X）＝|i|＝∑ij，称为X的全次数．而对多项式A（X）＝钞aiX，j＝１i则定义其全次数为ideg（A）＝max｛deg（X）|ai≠０｝．对于A∈R［X］，当视其为某未定元xr的一元多项式时，其关于xr的次数记为degx（A）或deg（A，xr）．r关于R［X］，在适当定义多项式的加法和乘法后，有下列基本结果．定理2畅2畅1１）如果R为交换环，则R［X］仍为交换环．R［X］中的零元就是零多项式０，而单位元即为常数多项式１畅２）如果D为整环，则D［X］仍为整环，且其可逆元为D中作为常数多项式的那些可逆元．３）如果D是UFD，则D［X］也为UFD．４）如果D为Euclid整环，则D［X］为UFD，但不是Euclid整环．５）如果K是域，则K［X］是UFD，且当未定元的个数大于１时不再是Euclid整环．2畅2畅2单项序与多项式的约化对于一元多项式情形，我们可以将多项式的项按未定元的方次由大到小排列，再利·３８·\n用带余除法就可以研究和计算一元多项式的问题了．对多元情形，也应该对所有的单项排出一个次序，并将除法的定义推广．现在考虑所有单项的集合ii１i２innT＝X＝x１x２⋯xn|i＝（i１，i２，⋯，in）∈N，n其中N是所有分量为非负整数的n元组的集合．定义2畅2畅1集合T上的一个全序＜T称为一个容许的单项序，如果１）对所有t∈T，成立１＜Tt．２）如果s，t∈T且s＜Tt，则对任意u∈T，su＜Ttu成立．单项序还有另外一种等价定义：１）＜T是T上的全序．２）如果s，t∈T且s＜Tt，则对任意u∈T，su＜Ttu成立．３）每个非空子集都有极小元．条件３）称为良序性质．上述定义中的条件３）还可等价地叙述为：３）′每个严格下降的单项序列都是有限终止的．n一般地，给定T上一单项序，因为单项与n元组是一一对应的，从而也诱导了N上jij的一个序，以后我们也用i＜T来表示X＜TX．满足上述条件的单项序有很多，但最常用的有如下三种．定义2畅2畅2＜l称为T上的（纯）字典序，如果ijX＜lX当且仅当（j１－i１，⋯，jn－in）的左数第一个非零元为正．容易验证上面定义的＜l确实满足定义２畅２畅１的两个条件，所以它是一单项序．注意，在上述定义中已蕴含了xn＜lxn－１＜l⋯＜lx１畅例2畅2畅1对三个未定元x＞y＞z的情形，单项按字典序由小到大的排列次序为２２１＜lz＜lz＜l⋯＜ly＜lyz＜lyz＜l⋯２２＜ly＜lyz＜l⋯＜lx＜lxz＜l⋯＜lxy＜l⋯定义2畅2畅3＜t称为T上的全幂序或称分次字典序，如果ijX＜tX，当且仅当（|j|－|i|，j１－i１，⋯，jn－in）的左数第一个非零元为正．定义2畅2畅4＜r称为T上的分次反字典序，如果ijX＜rX，当且仅当（j１－i１，⋯，jn－in，|i|－|j|）的右数第一个非零元为负．·３９·\n例2畅2畅2对三个未定元x＞y＞z的情形，单项按分次反字典序由小到大的排列次序为２２１＜rz＜ry＜rx＜rz＜ryz＜rxz＜ry＜rxy２３２２２＜rx＜rz＜ryz＜rxz＜ryz＜rxyz＜r⋯如果规定z＜ry＜rx，再将３个未定元的单项按分次字典序由小到大排列，则有２２１＜tz＜ty＜tx＜tz＜tyz＜ty＜txz２３２２＜txy＜tx＜tz＜tyz＜ryz＜txyz＜t⋯一般情况下，当不至于产生混淆时，我们常略去序＜T的下标，而简记作＜．定义2畅2畅5多项式P∈D［X］（相对于单项序＜）的领式是P中出现的单项式（按序＜）的最大者，记作lm（P）．而领式中出现的幂积称为P的领项，记作lt（P）．领项的多重次数记作md（P）．领项的系数记作lc（P）．显然对任何多项式P总成立lm（P）＝lc（P）lt（P）．以后我们总假定多项式都是按其单项式的次序由大到小递降排列的．对多项式的加法和乘法，有lt（PQ）＝lt（P）·lt（Q），lt（P＋Q）≤max｛lt（P），lt（Q）｝．例2畅2畅3下列多项式是按x＞y＞z的分次字典序递降排列的．２２３２２２２２P＝２xyz－３xyz＋xy－２xyz＋xz２２＋xy－xy＋yz＋z＋５，且有２２２２lm（P）＝２xyz，lt（P）＝xyz，lc（P）＝２畅但是如果按字典序排列，则有２２２２２２２２P＝xy－xyz＋xy＋xz＋２xyz３２－３xyz－xy＋yz＋z＋５畅相应的领项、领式及领项系数分别为２２lm（P）＝lt（P）＝xy，lc（P）＝１畅对域上的一元多项式环情形，因其为Euclid整环，我们可以用Euclid除法来计算最大公因子以及其他问题．但对多元多项式环的情形，它不再是Euclid整环，无法定义Euclid除法．因此我们需要引进一种与一元情形的除法求余运算有相同作用的运算，即多项式的约化．下面我们讨论多项式的约化问题，并假定考虑的是域K上的多项式．定义2畅2畅6设P，Q∈K［X］，如果P中有某个单项可被lt（Q）整除，P称为（相对于某固定单项序＜）是模Q可约的．如果P模Q可约，且P可以表示成P＝at＋R，其中a为非零常数，t∈T，R∈tK［X］为某一多项式，又＝u∈K［X］，记lt（Q）珚P＝P－auQ，（２畅２畅４）lc（Q）则称P模Q约化到珚P，记作PQ珚P．（２畅２畅５）·４０·\n如果Q∈G＝｛Q１，⋯，Qm｝，我们也称P模G可约，并记之为PG珚P．（２畅２畅６）如果在G中不存在多项式Qi使得P模Qi可约，则称P模G不可约或P相对于G是约化的．我们约定０相对于任何多项式或多项式组总是不可约的．例2畅2畅4对多项式４３２P＝６x＋１３x－６x＋１，Q＝３x＋５x－１畅如果约化P的领项，则有２３２PQP－２xQ＝３x＋２x－６x＋１畅３２注意，３x＋２x－６x＋１仍然是模Q可约的．事实上，P可以模Q约化到０，这是因为Q|P．在一元情形，约化等价于多项式的除法求余．例2畅2畅5考虑多项式２２P＝－xz＋２yz，２Q＝７y＋yz－４，R＝２yz－３x＋１畅２在分次字典序（x＞y＞z）下，它们都已表示成依单项递降排列的形式．P的项２yz既可以被lt（Q）整除，也可以被lt（R）整除．先用Q约化得２２２２８PQP－zQ＝－xz－yz＋z，７７７２２２８此时，珚P＝－xz－yz＋z模Q不可约但模R可约，且７７珚P珚P＋１zR＝－xz２－３xz＋９z．R７７７最后这个多项式既不是模Q可约的也不是模R可约的．倘若我们一开始不用Q而用R去约化，则有２PRP－yR＝－xz＋３xy－y．２－xz＋３xy－y模Q，R都不是可约的．由此例可以看出，对于给定的一多项式P与一多项式组G＝｛Q１，⋯，Qm｝，P模G约化的结果是不唯一的，它依赖于约化的次序．但是对上例而言，不管约化的次序如何，最终总可得一多项式，它相对于G＝｛Q，R｝是不可约的．事实上，这是约化的一个重要性质．命题2畅2畅1设G为给定的多项式组，P为任意一多项式，如果相对于某单项序＜有PGQ，则有lt（P）≥lt（Q）．证明按照约化的定义，存在G∈G与P的某项at以及u，使得t＝lt（G）u，且aQ＝P－uG．lc（G）记P＝lc（P）lt（P）＋at＋珚P，G＝lc（G）lt（G）＋（G－lm（G）），则有lt（P）＞lt（珚P），lt（G）＞lt（G－lm（G））．当lt（P）＝t时，因·４１·\naQ＝珚P－u（G－lm（G）），lc（G）故lt（Q）≤max｛lt（珚P），lt（u（G－lm（G）））｝＜t＝lt（P）．当lt（P）＞t时，因lt（u（G－lm（G）））＜ult（G）＝taQ＝lc（P）lt（P）＋珚P－u（G－lm（G）），lc（G）从而lt（Q）＝lt（P）．对固定的单项序＜，我们在多项式之间定义一偏序．对于任意两个多项式kl（１）（２）P１＝∑aiti，P２＝∑biti，i＝１i＝１我们称P１小于P２，记作P１＜P２，如果它们满足下列条件之一：（１）（２）（１）（２）１）存在s≤min｛k，l｝，使得ti＝ti，i＝１，⋯，s－１，ts＜ts．（１）（２）２）l＞k，且对任意i＝１，⋯，k，ti＝ti．否则，称P１，P２是不可比较的．引理2畅2畅1任何严格单调下降的多项式序列都是有限的．证明设P０＞P１＞⋯＞Pk＞⋯是严格单调下降的多项式序列，且每个多项式的项都是按序由大到小排列的．记每个Pk（k）的第j项为tj，k＝０，１，⋯考虑集合｛Pk｝的每个多项式的第１项构成的单项序列，则其为单调不增的序列（１）（２）（k）t１≥t１≥⋯≥t１≥⋯（k）（N）由单项序定义的条件３），存在正整数N１，使得当k＞N１时，有t１＝t１１畅如果仍有Pk，使得Pk＜PN，再考虑多项式序列｛Pk｝k＞N，则由多项式偏序的定１１（k）义，每个Pk都存在第２项t２，k＝N１＋１，⋯于是又得一单调不增的单项序列（N＋１）（N＋２）（k）t２１≥t２１≥⋯≥t２≥⋯（k）（N）再由单项序定义的条件３），存在正整数N２＞N１，使得当k＞N２时，t２＝t２２畅如此下去，则或者在某一步已得｛Pk｝的有限性；或者得一严格下降的单项序列（N）（N）（N）t１１＞t２２＞⋯＞tkk＞⋯（N）再由单项序定义的条件３），知该序列是有限的，即有tss，使得（N）（N）（N）（N）t１１＞t２２＞⋯＞tkk＞⋯＞tss．（N）（N）此时｛Pk｝必终止于PN，不然，若还有k＞Ns使得Pk＜PN，则由序列t１１，t２２，⋯，ss（Nk）（Ns＋１）tk，⋯的构造方法知，该序列又含有某多项式PN（Ns＋１＞Ns）的某项ts＋１，使得s＋１（N）（N）（N）（N）（N）（N）tsts＋１，这与序列t１２kss＞s＋１１，t２，⋯，tk，⋯终止于ts矛盾，故序列｛Pk｝必终止于PN．s定理2畅2畅2对于给定的多项式集合G与固定的单项序＜，任何P０的模G约化序列P０GP１GP２G⋯·４２·\n都是有限的，且P０可以在有限步内约化为一模G不可约的多项式．证明先证在约化序列中，Pk是严格单调下降多项式序列．若Pk模G约化到Pk＋１，则有Q∈G以及Pk的某项ct使得t＝lt（Q）u且cPk＋１＝Pk－uQ，（２畅２畅７）lc（Q）不妨设Pk＝R１＋ct＋R２，其中R１的任何一项都严格大于t，R２的任何一项都严格小于t．同理，将Q表示成Q＝lc（Q）lt（Q）＋S，则因t＝lt（Q）u，对S的任何项s∈T，都有su＜t．由式（２畅２畅７）有cPk＋１＝R１＋R２－uS．lc（Q）ccc若R２－uS≠０，则lt（R２－uS）＜t；若R２－uS＝０，则Pk＋１＝R１，lc（Q）lc（Q）lc（Q）再由多项式的偏序的定义知，Pk＞Pk＋１，从而引理２畅２畅２保证约化序列是有限的．如果在上述约化过程中，当Pk模G可约时，继续约化其到Pk＋１，则可得一约化序列，设该序列终止于Pl，此时Pl必为模G不可约的，不然Pl又可模G约化到Pl＋１，这与序列终止于Pl矛盾，故P０可以在有限步内约化为模G不可约多项式．如果存在一约化序列PGP１GP２GPm＝Q，倡·记PGQ．如果Q还是不可约的，则记PGQ，并记之为Q＝Reduce（P，G）．例2畅2畅6采用分次反字典序，考虑多项式组G＝｛P１，P２，P３｝，其中３２P１＝xyz－xz，２P２＝xyz－xyz，２２２P３＝xy－z畅又设２２３２２２Q＝xyz－z，R＝－xyz＋xyz．则２２３２２２QPxyz－z－z（xy－z）＝０．３２３同理有RP０．但Q＋R＝xyz－z却不再是模G可约的．２倡命题2畅2畅2设P∈K［X］，G＝｛G１，G２，⋯，Gs｝炒K［X］，且PGQ，则存在多项式Hj，使得sP＝钞HjGj＋Q，j＝１且lt（Q）≤lt（P），md（HjGj）≤md（P）．证明留作练习．·４３·\n２畅３Groebner基2畅3畅1Groebner基的定义与基本性质设I炒K［X］为一多项式集合，如果其满足下述性质，则称为一理想（见附录A）．１）０∈I．２）若A，B∈I，则A＋B∈I．３）若A∈I，则对任何B∈K［X］，AB∈I．称G炒K［X］为I的一组生成元，如果G＝｛G１，G２，⋯，Gm｝，且对任意A∈I都m可表示成A＝∑BiGi，其中Bi∈K［X］．我们也称G为I的一个理想基，记作I＝i＝１枙G枛．易知理想基不是唯一的．设K为域，考虑一元多项式环K［x］上的理想I．由于I中的多项式的次数构成非负整数全体的一个子集，故其有极小元，即I中次数极小的多项式是存在的．设A∈I为一次数极小的多项式，则对任何B∈I，由带余除法，有Q，R∈K［x］，使得B＝QA＋R，deg（R）＜deg（A）．如果R≠０，则有R＝B－QA∈I，这与A的定义矛盾，故必有R＝０．上述分析说明，I＝＜A＞，即A是I的理想基，I中的任何多项式除以A的余式为０，或者说可以被A约化到０，具有这种性质的理想基称为Groebner基，是符号计算中一种强有力的工具．Groebner基的概念是B．Buchberger于１９６５年在其博士论文中提出来的，为纪念其导师W．Groebner而将这种特殊的理想基命名为Groebner基．下面我们来介绍有关Groebner基的一些基本内容．定义2畅3畅1理想基G炒K［X］称为（关于某固定单项序＜的）Groebner基，如果·P∈枙G枛当且仅当PG０．（２畅３畅１）由上述定义可以看出，给定理想I炒K［X］的Groebner基G与任意一多项式P∈K［X］，则可判断是否有P∈I，即所谓理想成员问题是可以计算地判别的．下面研究Groebner基的性质．命题2畅3畅1理想基G为理想I的Groebner基的充分必要条件是：对任何P∈I，存在Gj∈G，使得lt（Gj）|lt（P）．证明必要性．设G为Groebner基，则对任何P∈I，有·PG０．我们断言，若lt（P）≠０，则其必被G中某多项式Gj的领项整除．不然设有有限约化过程PGP１GP２G⋯GPkG⋯G０，但lt（P）不被G中任何多项式的领项整除，则由命题２畅２畅１的证明可知，有lt（P）＝lt（P１）＝⋯＝lt（Pk）＝⋯＝lt（０）＝０，这与lt（P）≠０矛盾．充分性．设对任意的P∈I，存在Gj∈G及单项u使得lt（P）＝lt（Gj）u．令lc（P）P１＝P－uGj，lc（Gj）·４４·\n则由命题２畅２畅１，lt（P１）＜lt（P）．注意P１∈I，重复上述过程，再由引理２畅２畅１，可知P可在有限步内约化为０．n设S炒N为一（有限或无穷）子集，则ααI＝＜X|α∈S＞＝｛有限和∑CαX，Cα∈K［X］｝α为一理想，称之为单项理想．α单项理想的一个性质是：如果t∈T且t∈I＝＜X|α∈S＞，则存在α０∈S，ααα使得X０|t．这是因为t∈I＝＜X|α∈S＞意味着存在有限和∑CαX，Cα∈αααK［X］使得t＝∑CαX．将右端展开，则展开式的每一项都含有形如X，α∈S的因αα子；又左端为单项，故右端的项除一项外其他项必相互消去，即有aα∈K，X０，α０∈S与０ααu∈T，使得t＝aαuX０，这说明X０整除t．０定义如下的单项理想枙lt（I）枛＝枙lt（P）|P∈I枛，枙lt（G）枛＝枙lt（G）|G∈G枛，则命题２畅３畅１可以等价地叙述为如下．命题2畅3畅1′理想基G为理想I的Groebner基的充分必要条件是枙lt（I）枛＝枙lt（G）枛．（２畅３畅２）例2畅3畅1对于例２畅２畅６中的P１，P２，P３与Q，R，则２３３２G＝｛P１，P２，P３，xyz－z，xz－xz，３３２２２２４５４yz－z，xyz－xz，xz－z，z－z｝··是关于分次反字典序的Groebner基．我们已知QG０，RG０．计算可知，也有·Q＋RG０．定义2畅3畅2对固定的单项序，任何两个多项式P，Q∈K［X］的S唱多项式定义为PQSpoly（P，Q）＝lcm（lt（P），lt（Q））－．（２畅３畅３）lm（P）lm（Q）例2畅3畅2对于分次反字典序，多项式２３３２P＝３xy－y－４，Q＝xy＋x－９的S唱多项式为２３P－QSpoly（P，Q）＝（xy）３x２yxy３１２２３３２＝y（３xy－y－４）－x（xy＋x－９）３１５３４２＝－y－x－y＋９x．３３rα（i）α（i）引理2畅3畅1设有和式∑ciXGi，其中ci为常数，X为单项，Gi为多项式，i＝１n且对任意i，α（i）＋md（Gi）＝δ∈N．如果rα（i）md钞ciXGi＜δ，（２畅３畅４）i＝１·４５·\n则存在常数cj，j＋１，使得rr－１α（i）δ－γ钞ciXGi＝钞cj，j＋１Xj，j＋１Spoly（Gj，Gj＋１），（２畅３畅５）i＝１j＝１γ其中Xj，j＋１＝lcm（lt（Gj），lt（Gj＋１））．此外对每个j，有δ－γmd（Xj，j＋１Spoly（Gj，Gj＋１））＜δ．（２畅３畅６）rα（i）证明令di＝lc（Gi），则lc（ciXGi）＝cidi．由式（２畅３畅４），钞cidi＝０．i＝１α（i）定义Pi＝XGi／di，则Pi是首一的．于是rrα（i）钞ciXGi＝钞cidiPii＝１i＝１＝c１d１（P１－P２）＋（c１d１＋c２d２）（P２－P３）＋⋯＋（c１d１＋⋯＋cr－１dr－１）（Pr－１－Pr）＋（c１d１＋⋯＋crdr）Pr．β（i）注意最后一项等于０．现在设lm（Gi）＝diX，则有α（i）＋β（i）＝δ，由此可推出γδXjk|X，且有γγδ－γδ－γXjkXjkXjkSpoly（Gj，Gk）＝XjkGj－Gklm（Gj）lm（Gk）δδXX＝Gj－Gkβ（j）β（k）djXdkXα（j）α（k）XX＝Gj－Gkdjdk＝Pj－Pk．定义cj，j＋１＝c１d１＋⋯＋cjdj，j＝１，⋯，r－１，则有rr－１α（i）δ－γ钞ciXGi＝钞cj，j＋１Xj，j＋１Spoly（Gj，Gj＋１）．i＝１j＝１δ－γ注意Pi是首一的，且md（Pi）＝δ，故md（Pj－Pj＋１）＜δ．由此得md（Xj，j＋１Spoly（Gj，Gj＋１））＜δ．定理2畅3畅1理想基G是Groebner基的充分必要条件是对任何P，Q∈G，·Spoly（P，Q）G０．证明必要性是显然的，只需证明充分性．而按定义，又只需证对任何P∈枙G枛，存在Gj∈G，使得lt（Gj）|lt（P）．因为P∈枙G枛，故P有表示P＝钞HiGi，（２畅３畅７）i且md（P）≤max｛md（HiGi）｝＝δ．因这种表示可能不唯一，对每种表示存在一个相应的δ．因单项序是良序，每个非空子集有极小元，故这样的δ有极小元，假定所取的表示所对应的δ是极小的．我们将证明md（P）＝δ，因为一旦如此，则有HjGj使得md（P）＝md（HjGj），即lt（Gj）|lt（P），从而完成证明．·４６·\n用反证法．设md（P）＜δ，将式（２畅３畅７）改写成P＝钞HiGi＋钞HiGimd（HG）＝δmd（HG）＜δiiii＝钞lm（Hi）Gi＋钞（Hi－lm（Hi））Gimd（HG）＝δmd（HG）＝δiiii＋钞HiGi．md（HG）＜δii因为第二、第三个和式的领项的多重次数都小于δ，又md（P）＜δ，故必有md钞lm（HiGi）＜δ．md（HG）＝δii由引理２畅３畅１，在对Gi重新排序后，存在常数cj，j＋１，使得δ－γ钞lm（Hi）Gi＝钞cj，j＋１Xj，j＋１Spoly（Gj，Gj＋１），md（HG）＝δjiiδ－γ且有md（Xj，j＋１Spoly（Gj，Gj＋１））＜δ．由假设知，每个Spoly（Gj，Gj＋１）都可以被约化为０，由命题２畅２畅２知，Spoly（Gj，Gj＋１）可表示成Spoly（Gj，Gj＋１）＝钞Hj，kGk．k且有md（Hj，kGi）≤md（Spoly（Gj，Gj＋１））．于是δ－γ钞lm（Hi）Gi＝钞cj，j＋１Xj，j＋１Spoly（Gj，Gj＋１）md（HG）＝δjiiδ－γ＝钞cj，j＋１Xj，j＋１（钞Hj，kGk）jkδ－γ＝钞钞（cj，j＋１Xj，j＋１Hj，k）Gk，kj且δ－γmd（Xj，j＋１Hj，kGk）δ－γ＜md（Xj，j＋１）＋md（Spoly（Gj，Gj＋１）δ－γ＝md（Xj，j＋１Spoly（Gj，Gj＋１））＜δ．这表明存在P的表示δ－γP＝钞钞（cj，j＋１Xj，j＋１Hj，k）Gkkj＋钞（Hi－lm（Hi））Gi＋钞HiGi．md（HG）＝δmd（HG）＜δiiii此时右端的每个和式中的项都满足md（HGi）＜δ，这与δ的定义矛盾，从而必有md（P）＝δ．推论2畅3畅1如果G为Groebner基，P∈K［X］，则Reduce（P，G）是唯一的．证明设R＝Reduce（P，G）．若另有R′使得R′＝Reduce（P，G），则R′－R∈枙G枛．若R－R′≠０，则R′－R的某项可被G中某多项式G的领项整除，但是该项必为R或R′的某项，这说明R或R′关于G不是约化的，与R，R′的定义矛盾，故必有R＝R′．推论２畅３畅１说明，若G为Groebner基，则R＝Reduce（P，G）与约化次序无关．·４７·\n2畅3畅2Buchberger算法假设I炒K［X］为一多项式理想，S炒I为给定的理想基，一个自然的问题就是如何由S出发构造I的Groebner基G．定理２畅３畅１表明，一个理想基S为Groebner基当且仅当S中的任何两个多项式的S唱多项式可以模S约化为０．该定理一方面告诉我们如何判断一个理想基是否为Groebner基，另一方面也提示我们怎样由一个理想基构造Groebner基．当给定一理想基S以后，任意取两个多项式P，Q∈S，然后模S约化Spoly（P，Q），当R＝Reduce（Spoly（P，Q），S）≠０时，令S１＝S∪｛R｝，则显然S１仍为I的理想基，且有·Spoly（P，Q）S０．１再对S１重复上述过程，又可得一新多项式组S２．继续下去，则可得到一多项式集合序列S，S１，⋯，Sk，⋯这种算法就是所谓的Buchberger算法．需要证明的是：①这个序列是有限的；②最后得到的多项式集合，比如说，Sl，即为Groebner基．先来看一个例子．例2畅3畅3设S＝｛G１，G２，G３｝，其中２G１＝x＋yz－２，２G２＝y＋xz－３，２G３＝xy＋z－５畅依照分次反字典序，先取G１，G２计算，得２２２２Spoly（G１，G２）＝y（x＋yz－２）－x（y＋xz－３）３３２２＝－xz＋yz＋３x－２y３２２２Gyz＋xyz＋３x－２y－２xz１２２G３x－２y－２xz＋３yz２２G－２y－２xz＋６１G０．２再取G１，G３计算，得２２Spoly（G１，G３）＝yz－xz＋５x－２y２G－２xz＋５x－２y＋３z．２２令G４＝－２xz＋５x－２y＋３z，S１＝S∪｛G４｝，继续计算：２Spoly（G２，G３）GG５＝－２yz－３x＋５y＋２z，１S２＝S１∪｛G５｝，·Spoly（G１，G４）S０，１·Spoly（G２，G４）S０，１·Spoly（G３，G４）SG６，１４２G６＝－２z－２xz－３yz＋１５z－１９畅·４８·\n再令S３＝S２∪｛G６｝，经计算可知，对S３中任何两个多项式，其S唱多项式都可模S３约化为０，因此S３为Groebner基．算法2畅3畅1Buchberger算法．InputS＝｛G1，G2，⋯，Gk｝；OutputGroebnerbasisGsuchthat枙G枛＝枙S枛；G：＝S；B：＝｛（i，j）｜1≤i＜j≤k｝；whileB≠除doSelect（i，j）∈B；B：＝B－｛（i，j）｝；H＝Reduce（Spoly（Gi，Gj），G）；ifH≠0then；G：＝G∪｛H｝；k：＝k＋1；B：＝B∪｛（i，k）｜1≤i＜k｝；定理2畅3畅2算法２畅３畅１是正确的．证明１）终止性．记初始的多项式集合为G０．一般地，若在算法进入while之前的多项式集合为Gk，则在每次循环之后所得的多项式集合记为Gk＋１．考虑理想链Ik＝枙lt（G）|G∈Gk枛．因Gk＋１是由Gk加入多项式H而得，而H关于Gk是约化的，故必有lt（H）臭Ik，即有I０碸I１碸⋯碸Ik碸．由理想的升链条件，即任何单调不减的理想链只能由有限个理想组成（见附录A），必存在N，使得当k≥N时Ik＝IN．成立．于是在k＞N以后不再向指标集B加入新的指标对，但是B是有限集，因此在有限步内B变为空集．算法终止．２）正确性．设算法终止时的多项式集合为G，则对任意一对Gi，Gj∈G，由算法可知有Reduce（Spoly（Gi，Gj），G）＝０．再由定理２畅３畅１，即知G为Groebner基．事实上，在Buchberger算法中，并非每对多项式的S唱多项式都需要约化，利用下面的结果，可以找出那些S唱多项式必定可以约化为零的多项式对．在算法中去掉这些多项式对的约化，则可大大提高计算效能．定理2畅3畅3（Buchberger算法的第一判别准则）设F为有限多项式集合，P，Q∈F且lt（P）lt（Q）＝lcm（lt（P），lt（Q）），即lt（P），lt（Q）互素，则·Spoly（P，Q）F０．证明留作练习．为了介绍Buchberger算法的的第二判别准则，需要引进一个定义．定义2畅3畅3设F炒K［X］为一多项式的有限集合，P∈K［X］，t∈T，如果·４９·\nkP＝钞miGi，（２畅３畅８）i＝１其中mi为非零单项式，Gi∈F未必两两互异，且max｛lt（miGi）|１≤i≤k｝≤t，（２畅３畅９）则称其为P关于F的一个t唱表示．如果t＝lt（P），则称P关于F有一标准表示．下面先来介绍Groebner基的一些重要性质．定理2畅3畅4设G为有限多项式集合且０臭G，则G为Groebner基当且仅当每个０≠P∈枙G枛关于G有一标准表示．证明留作练习．定理2畅3畅5设G为有限多项式集合且０臭G，如果对所有的多项式对G１，G２∈G，Spoly（G１，G２）或者为零或者对某t＜lcm（lt（G１），lt（G２）），它关于G有一t唱表示，则G为一Groebner基．证明我们来证每个０≠P∈枙G枛关于G有一标准表示，再由定理２畅３畅４，即可知本定理成立．设０≠P∈枙G枛关于G有一表示kP＝钞miGi，（２畅３畅９）′i＝１其中mi＝aiti为非零单项式，Gi∈G未必两两互异．设s＝max｛lt（miGi）|１≤i≤k｝为所有这样的表示中的最小者，需要证明s＝lt（P）．如果s＞lt（P），我们将用归纳法证明存在P关于G的一s′唱表示，而s＞s′，这将与s的极小性相矛盾．对式（２畅３畅９）′中使得lt（miGi）＝s的指标i的个数l做归纳法．当l＝１时，显然结论正确．设l＝２，不失一般性，假设lt（m１G１）＝lt（m２G２）＝s．这意味着s＝t１lt（G１）＝t２lt（G２），因而lcm（lt（G１），lt（G２））|s．设s＝u·lcm（lt（G１），lt（G２）），因为式（２畅３畅９）′右端的最高项必须消去，故有lm（m１G１）＝－lm（m２G２），从而a１lc（G１）＝－a２lc（G２）．令a＝a１lc（G１）＝－a２lc（G２），不难证明m１G１＋m２G２＝auSpoly（G１，G２）．（２畅３畅１０）由假设，Spoly（G１，G２）＝０或者对某t＜lcm（lt（G１），lt（G２））有t唱表示k′Spoly（G１，G２）＝钞mi′Gi′，Gi′∈G．（２畅３畅１１）i＝１将式（２畅３畅１０）代入式（２畅３畅９）′得kk′P＝钞miGi＋au钞mi′Gi′，（２畅３畅１２）i＝３i＝１由s的定义有·５０·\nmax｛lt（miGi）|３≤i≤k｝＜s，max｛lt（umi′Gi′）|１≤i≤k′｝＝ut＜ulcm（G１，G２）＝s，这说明式（２畅３畅１２）为P的一个s′唱表示，且有s′＜s．现在假设结论对l－１＞２成立，则当lt（miGi）＝s的指标i的个数为l时，不妨假定仍有lt（m１G１）＝lt（m２G２）＝s，则kP＝钞miGii＝１klc（m１G１）lc（m１G１）＝m１G１－m２G２＋＋１m２G２＋钞miGi．（２畅３畅１３）lc（m２G２）lc（m２G２）i＝３前两项中的s显然被消掉，由引理２畅３畅１以及l＝２情形的证明，前两项可以表示为钞mi′Gi′，lt（mi′Gi′）＜s的形式．因此式（２畅３畅１３）中使得lt（miGi）＝s的指标i的个i数为l－１，由归纳假定，存在P的关于G的一s′唱表示，而s＞s′．定理2畅3畅6（Buchberger算法第二判别准则）设F为有限多项式集合，G１，G２，P∈K［X］使得下列条件成立１）lt（P）|lcm（lt（G１），lt（G２））．２）对i＝１，２，Spoly（Gi，P）关于F有ti唱表示，并且ti＜lcm（lt（Gi），lt（P））．则对某t＜lcm（lt（G１），lt（G２）），多项式Spoly（G１，G２）关于F有t唱表示．证明留作练习．利用Buchberger算法的两个判别准则，可以将算法２畅３畅１加以改进，请读者自己完成这个工作．2畅3畅3Groebner基的应用在符号计算领域，特别是在多项式代数的理论研究与计算中，Groebner基方法扮演着十分重要的角色，而且它在诸多理论研究与实际问题中也都起着重要作用．我们这里仅举几个简单的例子．１畅商环中的计算对给定的多项式理想I炒K［X］，可以定义K［X］上的等价关系～如下：对任何A，B∈K［X］，A～B当且仅当A－B∈I，此时我们也称A与B是模I同余的，记作A≡BmodI．K［X］中这种等价类全体构成的集合在定义恰当的运算后可得一交换环，称为K［X］对I的商环（见附录A），记作K［X］／I．我们期望能够实现商环中的各种计算，而Groebner基恰好就是一种有效的工具．对于全体单项的集合T，利用Groebner基可以将其分为两部分，一部分是Groebner基中多项式的领项的倍式全体｛t∈T|存在P∈G，使得lt（P）|t｝，另一部分是它关于T的补集N＝T－｛t|存在P∈G使得lt（P）|t｝．对于任何P∈K［X］，若记R＝Reduce（P，G），则易见有R＝钞cuu，u∈N·５１·\n且若记［P］为P的模I同余类，则有R∈［P］．因此有可能用Span｛N｝中的运算来表示商环中的运算．定理2畅3畅7设I炒K［X］为多项式理想，G炒I为I的关于某个单项序的Groeb唱ner基，定义U＝｛［u］|u∈N｝，其中［u］表示u的模I的同余类，则U是商环K［X］／I的一组向量空间基．证明只需证明U中元是线性无关的，且任何［P］∈K［X］／I都可由U中元线性表示．对于任何P∈K［X］，由推论２畅３畅１知，存在唯一的R，使得R＝Reduce（P，G），R∈Span｛N｝且［P］＝［R］．由此可知商环中任何元素都可以表示成U中元素的线性组合．其次，如果在U中有线性关系a１［u１］＋⋯＋am［um］＝０，其中ai∈K，ui∈N，i＝１，⋯，m，则有P＝a１u１＋⋯＋amum∈I．倘若存在ai≠０，则P必可模G约化为０．由此推得存在某ui可被G中某多项式的领项整除，这与ui的定义矛盾，故必ai＝０，i＝１，⋯，m，即N中元是线性无关的．定理２畅３畅７表明，商环K［X］／I与Span｛N｝作为向量空间是同构的，因此商环中［P］，［Q］的加减法可以用R＝Reduce（P，G），S＝Reduce（Q，G）的加减法来表示，这是因为仍然有R＋S∈Span｛N｝．但是［P］［Q］却不能再用RS来表示，因为未必有RS∈Span｛N｝．例2畅3畅4对例２畅３畅３中计算所得的Groebner基２２２G＝｛x＋yz－２，y＋xz－３，xy＋z－５，２２－２xz＋５x－２y＋３z，－２yz－３x＋５y＋２z，４２－２z－２xz－３yz＋１５z－１９｝，商环Q［x，y，z］／枙G枛的向量空间基为U＝｛［１］，［x］，［y］，［z］，２３［xz］，［yz］，［z］，［z］｝．２虽然xz，yz∈Span｛N｝，但是xyz臭Span｛N｝．因此要计算［xz］［yz］，还需要计算２３５２１９Reduce（xyz，G）＝xz＋yz－z＋，２２２从而３５２１９［xz］［yz］＝［xz］＋［yz］－［z］＋［１］．２２２一般说来，对于给定的理想，相应的商环未必是一域．但是当商环是有限维向量空间时，利用Groebner基可以判断商环中某一元素是否可逆，并在其可逆时求得其逆元素．例2畅3畅5考虑例２畅３畅４中的［x］，如果其可逆，则其逆元也必为商环中的元，设其逆元为２３［Q］＝a０［１］＋a１［x］＋a２［y］＋a３［z］＋a４［xz］＋a５［yz］＋a６［z］＋a７［z］，则其应满足［x］［Q］＝［１］．由此可得P＝x（a０＋a１x＋a２y＋a３z＋a４xz·５２·\n２３＋a５yz＋a６z＋a７z）－１∈枙G枛．约化得Reduce（P，G）＝（－１＋２a１＋５a２）＋（a０＋３／２a４＋５／２a６）x＋（－５／２a４－a６）y＋（a４＋５a５＋３／２a６）z＋（－a１－a７）yz＋（a３＋５／２a７）xz２３＋（－a２＋３／２a７）z－a５z畅因为P∈枙G枛，故必Reduce（P，G）＝０．由此推得所有系数为０，于是得一关于a０，⋯，a７的线性方程组，解之得２３５２a０＝a４＝a５＝a６＝０，a１＝－，a２＝，a３＝－，a７＝．１１１１１１１１最终有－１２３２３５［x］＝［z］－［x］＋［y］－［z］．１１１１１１１１２畅多项式方程组求解设Pi（x１，⋯，xn）＝０，i＝１，⋯，m，为域K上的多项式方程组．要求解这样一方程组，自然应该解决以下几个问题：该方程组是否有解，有多少解，怎样求解．考虑由该方程组的多项式生成的理想枙P１，⋯，Pm枛炒K［X］，计算其关于某单项序的Groebner基G，那么以上几个问题都可以通过G来解决．在解决所提问题之前，先来介绍一个有关域的概念．设K为一域，以K中元为系数的多项式的根称为K上的代数元．如果K上的任何代数元均属于K，则称K为代数封闭域，简称代数闭域．设K，L为域，且K炒L，如果L中的元都是K上的代数元，且L是代数封闭的，则称L为K的代数闭包．定理2畅3畅8设K为代数闭域，｛P１，⋯，Pm｝炒K［X］，G为枙P１，⋯，Pm枛（关于任何单项序）的Groebner基，则方程组Pi＝０，i＝１，⋯，m，在K中有解当且仅当１臭G．证明由Hilbert零点定理（见附录A），Pi＝０，i＝１，⋯，m，在K中无解当且仅当１∈枙P１，⋯，Pm枛．而由Groebner基的定义，１∈枙P１，⋯，Pm枛当且仅当１∈G．因此方程组有解当且仅当１臭G．定理２畅３畅８解决了解的存在性问题，只要求出相应的Groebner基，便可以由其是否包含１而断定解的存在性．下面的定理解决了解的有限性问题．定理2畅3畅9设K为代数闭域，G为枙P１，⋯，Pm枛炒K［X］（关于任何单项序）的Groebner基，则方程组Pi＝０，i＝１，⋯，m，在K中仅有有限多解当且仅当对每个j＝m１，⋯，n，存在正整数mj及Gj∈G使得lt（Gj）＝xjj．证明设方程组Pi＝０，i＝１，⋯，m，在K中仅有有限多个解｛a１，⋯，ar｝炒K，（j）记ak为ak的第j个分量，则·５３·\n（j）（j）（j）F＝（xj－a１）（xj－a２）⋯（xj－ar）m在｛a１，⋯，ar｝上取０值，由Hilbert零点定理，存在正整数m使得F∈枙P１，⋯，Pm枛．m由Groebner基的定义，存在Gj∈G使得lt（Gj）|lt（F）．但是F为仅含xj的多项式，m故有m，使得lt（G）＝xj．jjjm反之，若有Gj∈G及mj，使得lt（Gj）＝xjj，则N＝T－｛t|t∈枙lt（G）枛｝炒iii｛x１２n１x２⋯xn|i１＜m１，⋯，in＜mn｝．因后者是有限集，故N也为有限集．由定理２畅３畅７，商环是有限维的向量空间．于是对任何j＝１，⋯，n，存在dj使得［１］，［xj］，２d［xjj］，⋯，［xj］是线性相关的．即有２dQj＝a０＋a１xj＋a２xxjj＋⋯＋adj∈枙P１，⋯，Pm枛．j但是每个Qj＝０的解的个数是有限的，故方程组Pi＝０，i＝１，⋯，m，的解的个数有限．例2畅3畅6在例２畅３畅３中我们给出了一组多项式２G１＝x＋yz－２，２G２＝y＋xz－３，２G３＝xy＋z－５畅例２畅３畅３中计算了枙G１，G２，G３枛的Groebner基２２２G＝｛x＋yz－２，y＋xz－３，xy＋z－５，２２－２xz＋５x－２y＋３z，－２yz－３x＋５y＋２z，４２－２z－２xz－３yz＋１５z－１９｝．２２４其中x，y以及z都出现在某些多项式的领项当中，所以方程组２x＋yz－２＝０，２y＋xz－３＝０，２xy＋z－５＝０，仅有有限多个解．需要注意的是，定理２畅３畅９所叙述的“仅有有限多个解”是指在代数闭域中有限．当２２系数域不是代数闭域时，结论未必正确．例如取P＝x＋y∈Q［X］，则P＝０在Q只有一解（０，０）．注意P本身就是枙P枛的Groebner基，无论取哪种单项序，领项只能２２取x或y之中的一个．实际上在复数域CP＝０有无穷多解．以下假定方程组仅有有限多解，我们来讨论其求解方法．设给定K［X］中的一方程组P１（X）＝０，P２（X）＝０，⋯，Pm（X）＝０．选取字典序（假定未定元之间的排列为x１＞x２＞⋯＞xn）计算理想＜P１，⋯，Pm＞的Groebner基G＝｛G１，G２，⋯，Gr｝．由定理２畅３畅１２，在对G中的多项式适当排序后，存m在Gi∈G与mi使得lt（Gi）＝xii，i＝１，⋯，n．由此可推知必有n≤r．因为所用的m序是字典序，lt（Gn）＝xnn，Gn的其他项也必仅含xn，也就是说，Gn是xn的一元多项式．同理分析可知，Gn－１仅含未定元xn－１，xn．类推下去，可知G包含了如下的多项式组．·５４·\nG１＝G１（x１，x２，⋯，xn），G２＝G２（x２，⋯，xn），⋯⋯Gn－１＝Gn－１（xn－１，xn），Gn＝Gn（xn）．由最后一个方程Gn＝０解出一组xn的解｛an１，⋯，anl｝，再将每个ani，i＝１，⋯，l，代入Gn－１以及其他G中仅包含xn－１，xn的多项式Gj（xn－１，xn），⋯可得一组含xn－１的方程组Gn－１（xn－１，ai）＝０，Gj（xn－１，ani）＝０，⋯这仍然是一个一元多项式方程组，解之又可得一组对应xn－１的解．继续下去即可求得原方程组的全部解．例2畅3畅7对例２畅３畅３中的多项式２G１＝x＋yz－２＝０，２G２＝y＋xz－３＝０，２G３＝xy＋z－５＝０．我们已知它仅有有限多个解．计算＜G１，G２，G３＞的字典序下的Groebner基，得８８７８７２５２６９０３１２５G＝x－z＋z－z＋z，３６１３６１３６１１９８７５２５７４０３７５y＋z＋z－z＋z，３６１３６１３６１１９８２５６２１９４２３６１z－z＋z－９５z＋．２４８从第三个多项式方程８２５６２１９４２３６１z－z＋z－９５z＋＝０２４８可以解出８个根，代入前两个方程即可得全部解．2畅3畅4多项式的理想唱adic表示本节我们讨论多项式的理想唱adic表示．这种表示在符号计算的许多算法中要用到．设A∈K［X］为给定的多项式，I炒K［X］为多项式理想．我们期望将A表示为（０）（１）（m）A＝A＋A＋⋯＋A（i）ii的形式，其中m为充分大的正整数，且A∈I，i＝０，⋯，m，I表示理想的乘幂（见附录A）．多项式的这种表示称为I唱adic表示．我们感兴趣的是I＝枙x２－a２，⋯，xn－an枛的情形．容易看出，在A的I唱adic表示中成立（０）（i－１）iA＝A＋⋯＋AmodI，i＝１，⋯，m＋１畅i（i）（i）因此只要知道了I的Groebner基G，A就可以递推地确定出来（i）（０）（i－１）（i＋１）A＝Reduce（A－（A＋⋯＋A），G）．（i）所以我们只要求出G即可．（１）当i＝１时，容易验证G＝｛x２－a２，⋯，xn－an｝．２当i＝２时，按照理想的乘幂的定义，（xk－ak）（xl－al）∈I，２≤k≤l≤n．并２且可以证明，它们确实构成I的理想基，且为Groebner基．换言之，·５５·\n（２）G＝｛（xk－ak）（xl－al），２≤k≤l≤n｝．（２）容易看出，G中的多项式与齐２次n－１元单项式是一一对应的．应用组合数学的知（２）n－２＋２i识可知，在G中计有个多项式．一般地，对于I，仿i＝２的情形可得n－２（i）G＝｛（xk－ak）（xk－ak）⋯（xk－ak），２≤k１≤k２≤⋯≤ki≤n｝．１１２２ii（i）n－２＋i此时G中的多项式是与齐i次n－１元单项式一一对应的，计有个．为了n－２（i）书写方便，对应每个G，定义n－１重指标集（i）J＝｛（j２，j３，⋯，jn）|０≤jk≤i，j２＋⋯＋jn＝i｝，（i）则G可以表示成（i）（i）（i）G＝｛GS|S∈J｝，（i）jj（i）其中GS＝（x２－a２）２⋯（xn－an）n，S＝（j２，⋯，jn）∈J．利用前面定义的记号，可将每个A∈K［X］表示为d（i）（i）A＝钞钞AS（x１）GS（x２，⋯，xn）i＝０（i）S∈J其中d＝deg（A）．例2畅3畅8对于多项式２４９２３６４５A＝xyz－xyz＋xyz＋２x－yz－２yz，取K＝Z５，I＝枙y－１，z－１枛，则有（１）G＝｛y－１，z－１｝，（２）２２G＝｛（y－１），（y－１）（z－１），（z－１）｝，⋯⋯⋯（i）而相应的系数AS（x）为（０）２（１）２A（０，０）＝x＋２x＋２，A（１，０）＝－（x－１），（１）２（２）２A（０，１）＝x＋x－１，A（２，０）＝x－x，（２）２（２）A（１，１）＝－（x－１），A（０，２）＝２x－１，（３）２（３）２A（３，０）＝－（x－x），A（２，１）＝x－２x，（３）（３）A（１，２）＝－（x＋１），A（０，３）＝x＋１，⋯⋯⋯⋯（１０）（１０）A（１０，０）＝０，A（９，１）＝－２x，（１０）（１０）A（８，２）＝x，A（６，４）＝－１，（１１）A（９，２）＝－x．在上标大于等于１０的系数中，没有写出来的都是０．２畅４吴方法吴方法，又称特征列方法，是吴文俊于２０世纪７０年代提出的处理多项式代数问题·５６·\n的一种方法．与Groebner基方法不同之处在于，它完全采用零点集的观点来处理问题，因此在定理证明、多项式方程组求解以及其他许多方面较Groebner基方法更有效．现在吴方法在数学理论研究、理论物理、机器人制造等诸多领域都得到了广泛的应用．限于篇幅，我们这里不可能对其做详细的介绍，只给出一些基本概念以及解多项式方程组与定理证明的简单例子．2畅4畅1升列、基列与特征列设K为特征为０的域．K［x１，⋯，xn］为多项式环．此后我们总假定所用的单项序为字典序，且未定元的序为x１＜x２＜⋯＜xn．这一点和我们以前定义的字典序实质上是一样的，只不过未定元的次序交换一下而已．iii对于给定的单项式at＝ax１２n１x２⋯xn∈K［x１，⋯，xn］，在t的多重次数中，如果最后一个不为零的是ip，则称t的类（class）为p，并记作cl（t）＝p．非零常数的类定义为０．如果一个单项式的类为p，这个单项必定含未定元xp，且必定不含xp＋１，⋯，xn．例２如，x１x２x３与x３的类都是３畅对任何F∈K［x１，⋯，xn］，可以按单项由大到小的次序排列，将其表示为F＝a１t１＋a２t２＋⋯＋asts，其中ai∈K为常数，ti∈K［x１，⋯，xn］为单项．F的领项的类称为F的类，记作cl（F）．同理，当cl（F）＝p时，F必定不含未定元xp＋１，⋯，xn．设F为一非零多项式，cl（F）＝p，且F的领项关于xp的次数为m，则F可表示为mm－１F＝C０xp＋C１xp＋⋯＋Cm，其中C０≠０，Ci，０≤i≤m，是仅含未定元x１，⋯，xp－１的多项式．C０称为F的初式．m如果C０的领项为C珚０，则F的领项显然为C珚０xp．设有两个多项式F，G，考虑未定元xp，如果degx（F）＜degx（G），则称F相对于ppxp的级别比G低．如果在这二者中，每个相对于xp的级别都不比另一个低，则称二者相对于xp具有相同的级别．注意这个概念与两个多项式的类没有关系．对于两个非零多项式F和G，如果下列两条件之一成立：１）cl（F）＜cl（G）．２）cl（F）＝cl（G）＝p＞０，但degx（F）＜degx（G）．pp我们称F的级别比G低（或者称G的级别比F高），记作F吵G或G巢F．如果在F和G中，每一个都不比另一个级别低，则称它们具有相同的级别，记作F～G．注意在上述定义中，如果条件１）或２）之一成立，则必有lt（F）＜lt（G）（关于２２x１＜⋯＜xn的字典序）；反之不然，例如对F＝x１x２x３与G＝x１x３，二者具有相同２２的级别，但x１x２x３＞x１x３畅设F是一个多项式，cl（F）＝p＞０．对任何一个相对于xp比F级别低的多项式G都称为相对于F是约化的，记为Gred／F．显然任何比F级别低的多项式都是相对于F约化的，特别地，F的初式的类小于F·５７·\n的类，所以它相对于F是约化的，即一个多项式的初式相对于自己来说总是约化的．一２２般说来，相对于F约化的多项式未必比F的级别低．例如，对F＝x１x２＋x１，G＝x１＋x２＋x３，则有Gred／F，但是cl（G）＝３＞cl（F）＝２畅此外，G相对于xp比F的级别低并不意味着Gred／F．Gred／F明确要求cl（F）＝p＞０，而G相对于xp比F的级别低时，cl（F）可以大于p．前面已经提到过，如果一多项式F的类cl（F）＝p，则F可表示为mm－１F＝f０xp＋f１xp＋⋯＋fm，其中f０≠０，fi∈K［x１，⋯，xp－１］，０≤i≤m．对任何多项式G，如果它相对于F不是约化的，那么它总可以写成MM－１G＝g０xp＋g１xp＋⋯＋gM，其中g０≠０，gi∈K［x１，⋯，xp－１，xp＋１，⋯，xn］，０≤i≤M，且M≥m．视F，G为K［x１，⋯，xp－１，xp＋１，⋯，xn］［xp］上的多项式，利用伪除概念，则有非负整数s使得sf０G＝QF＋R．（２畅４畅１）容易看出，当R≠０时，必有degx（R）＜degx（F），即有Rred／F．如果已经有ppGred／F，取s＝０，Q＝０，R＝G，则F和G也可写成式（２畅４畅１）的形式，即对给定的F与任意的G，总有s，Q，R存在，使得式（２畅４畅１）成立．因此我们称多项式R为G相对于F的（伪）余式，这种由G求得余式R的过程称为G相对于F的约化．下面考虑有限多个多项式组成的序列A：A１，A２，⋯，Ar，如果下列两条件之一成立：１）r＝１，A１≠０．２）r＞１，０＜cl（A１）＜cl（A２）＜⋯＜cl（Ar），且对任意j＞i，Ajred／Ai．我们称A为一个升列（ascendingset）．因为未定元的个数为n，多项式的类只有n＋１类．在上述定义中，无论哪一种情形成立，总有r≤n．例如，多项式列８６４２A１＝－x１－４x１＋８x１＋３２x１－１６，４A２＝（４x１）x２＋x１－４，２A３＝－２x３＋x１，就是一个升列．一个升列称为矛盾列，如果r＝１，A１≠０，但cl（A１）＝０．即一个非零常数构成的升列是矛盾列．当把升列看成多项式方程组时，矛盾列总是没有解的．设A为一升列，G为一多项式．如果G相对于升列A中每个多项式都是约化的，则称G相对于升列A是约化的．设另有升列B：B１，B２，⋯，Bs，如果下列两条件之一成立：·５８·\n１）存在j≤min（r，s），使得A１～B１，⋯，Aj－１～Bj－１，但Aj巢Bj．２）s＞r且A１～B１，⋯，Ar～Br．我们称A比B的级别高，或者说B比A的级别低，记为A巢B或B吵A．如果A和B中每个都不比另一个级别低，则称二者有相同的级别，记作A～B．此时必有r＝s，A１～B１，⋯，Ar～Br．容易看出，级别在全体升列集合上定义了一个偏序，因此对任何升列集可以引进极小升列的概念．下面的定理在整个吴特征列理论中起着非常重要的作用．定理2畅4畅1（Ritt引理）设A１，A２，⋯，Aq，⋯为一不增的升列组成的序列，即对任何q，有Aq＋１吵Aq或Aq＋１～Aq成立，则存在指标q′，使得对任意q＞q′恒有Aq～Aq′，即Aq′为上述序列中级别最低的升列．证明我们用rq表示Aq中多项式中的数目，Aq表示Aq的第一个多项式，则A１，A２，⋯，Aq，⋯是一个不增的多项式序列，即对任意q，或有Aq＋１吵Aq或Aq＋１～Aq．因此或有cl（Aq＋１）＜cl（Aq）或cl（Aq＋１）＝cl（Aq）＝p＞０，但是degx（Aq＋１）＜degx（Aq）．由pp于类和次数都是非负整数，存在q１使得当q≥q１时，所有的Aq具有相同的级别．再考（１）虑q≥q１时的Aq中的第二个多项式Aq（１）（１）（１）Aq，Aq＋１，⋯，Aq，⋯１１（１）（１）类似前面的分析，可知存在q２，使得当q≥q２时Aq～Aq．注意在每个升列中多项式２的个数不超过n个，所以上述过程可在n步内找到一q′，使得当q≥q′时，rq＝rq′且Aq～Aq′．由定理２畅４畅１，可推出：推论2畅4畅1若由升列组成的序列严格下降，则该序列必定只由有限个升列构成．现在我们来定义升列集合上的极小元．设PS为有限多个非零多项式组成的多项式集合．一个升列A称为属于PS是指A的每个多项式都属于PS．因为单个多项式本身也构成一个升列，所以属于PS的升列集是非空的．于是属于PS的升列集上的级别是一个偏序．由定理２畅４畅１，按此偏序每个升列的不增序列都有一极小元，该极小元自然属于PS．我们称这种极小元为PS的一个基本列（basicset）．下面的定理不但指出了基本列的存在性，而且也给出了基本列的构造方法．定理2畅4畅2设PS为非零多项式构成的有限集，则PS必有一基本列，而且存在一种方法使得这样的基本列能在有限步内构造出来．证明因为PS有限，其基本列的存在是显然的．我们只需将其构造出来．首先从PS１＝PS中选一级别最低的多项式A１，这是能够办到的．如果cl（A１）＝０，则A１已经是一基本列．假设cl（A１）＞０，检查PS１－｛A１｝中的多项式相对于A１是否都·５９·\n是未约化的，若是，则PS中不可能再有比｛A１｝级别低的升列，因此A１就是PS的基本列．否则令PS２为PS１中相对于A１已约化的多项式全体．由A１的选取，PS２中的多项式的级别都高于A１的级别．再注意到PS２中的多项式相对于A１都是约化的，PS２中多项式的类一定大于cl（A１）．再在PS２中选取一级别最低的多项式A２畅如果PS２－｛A２｝中关于A２都是未约化的，则PS中不可能再有比｛A１，A２｝级别低的升列，故｛A１，A２｝即为PS的基本列．否则再构造PS３，从而得A３畅注意按照构造方法，A１，A２，A３，⋯的类是严格增加的，但是多项式的类只有n个，所以这种列必定在有限步内终止．又由构造方法知，该列中后面的多项式相对于前面的多项式都是约化的，因此我们得到的多项式列是一升列，且由构造原则知其为PS的基本列．定理2畅4畅3设PS为非零多项式构成的有限集A：A１，A２，⋯，Ar是PS的一基本列，cl（A１）＞０．设B为一非零多项式，且Bred／Ai，i＝１，⋯，r，则PS′＝PS∪｛B｝有一比A级别低的基本列．证明如果cl（B）＝０，则B本身即为PS′的基本列，且其级别比A低．如果cl（B）＝p＞０，且存在s，１≤s≤r，使得cl（As－１）＜p≤cl（As），因为Bred／Ai，i＝１，⋯，r，则或p＝cl（As），degx（B）＜degx（As），或者p＜cl（As），在这两种情况下pp都有B吵As，于是A１，A２，⋯，As－１，B（２畅４畅２）是PS′的一升列，且级别低于A．又PS′的基本列的级别必不高于式（２畅４畅２），当然该基本列的级别低于A．如果cl（B）＞cl（Ar），A１，⋯，Ar，B的级别也小于A的级别，当然PS′的基本列的级别低于A的级别．设A：A１，A２，⋯，Ar为一给定的升列，cl（Ai）＝pi，p１＜p２＜⋯＜pr．Ii为Ai的初式．设B为一多项式，如果对A中的每个Ai都有Bred／Ai，则称B相对于A是约化的．如果B相对于A不是约化的，依次对Ar，Ar－１，⋯，A１求余式sIrrB＝QrAr＋Rr，Rrred／Ar，sIr－１r－１Rr＝Qr－１Ar－１＋Rr－１，Rr－１red／Ar－１，（２畅４畅３）⋯⋯sI１１R２＝Q１A１＋R１，R１red／A１畅最后所得的R１相对所有Ai都是约化的，即相对A是约化的．我们称R１为B对A的余式．利用式（２畅４畅３）可推知，存在Qi′使得rsssI１２rQ１I２⋯IrB＝钞i′Ai＋R１畅（２畅４畅４）i＝１该式称为余式公式．·６０·\n下面假设PS为一非零多项式构成的集合，我们来讨论其所谓特征列的构造．对给定的PS１＝PS，由定理２畅４畅３，存在PS１的基本列BS１畅将所有PS１－BS１中的多项式对基本列BS１求余式，则得一余式的集合RS１畅若RS１≠碬，令PS２＝PS１∪RS１，再找出PS２的一基本列BS２畅注意，PS２是由PS１添加所有对BS１的余式而得的，所以BS２的级别比BS１低．再将PS２－BS２中的多项式对BS２求余式，并记该余式集合为RS２畅如果RS２≠碬，令PS３＝PS２∪RS２，并求其基本列BS３，此时有BS１巢BS２巢BS３巢⋯．由推论２畅４畅１，这个基本列构成的序列是有限的，因而必在某一步，比如说m，使得RSm＝碬．此时我们称相应的基本列BSm为PS的特征列（characteristicset），并记之为CS．例2畅4畅1求给定的多项式组２P１＝－x２＋x１x２＋１，２P２＝－２x３＋x１，２P３＝－x３＋x１x２－１的特征列．首先求PS１＝｛P１，P２，P３｝的基本列BS１畅按照定理２畅４畅３的方法，因为cl（P１）＝２，cl（P２）＝cl（P３）＝３，故PS１中级别最低的多项式为P１畅又在PS１－｛P１｝＝｛P２，P３｝中，P２，P３相对于P１都是约化的，故下一个多项式应在｛P２，P３｝中选取．在｛P２，P３｝中，P２的级别最低，故应该选P２畅因剩下的P３相对于P２是未约化的．于是P１，P２构成PS１的基本列．接下来计算RS１畅因PS１－BS１＝｛P３｝，RS１为P３相对于BS１的余式组成．为计算P３相对于BS１的余式，先计算其对P２的余式得s２PI２３＝Q２P２＋R２畅２４其中I２＝－２，s２＝２，Q２＝２x３＋x１，R２＝４（x１x２－１）－x１畅因为cl（R２）＝cl（P１）＝２，且degx（R２）＝１＜degx（P１）＝２，R２相对于P１是约化的，故R２相对于P１的２２余式为其本身，于是RS１＝｛R２｝≠碬．记P４＝R２，令PS２＝PS１∪RS１＝｛P１，P２，P３，P４｝．再找基本列BS２＝｛P４，P２｝．将P１对BS２求余式，得２０I４I２P１＝Q′２P４＋０P２＋R′２，８６４２其中I４＝４x１，R′２＝－x１＋４x１－８x１＋３２x１－１６畅而P３相对于BS２的余式为０，于是RS２＝｛R′２｝≠碬．再令P５＝R′２，PS３＝｛P１，P２，P３，P４，P５｝，求得其基本列为BS３＝｛P５，P４，P２｝．经过计算可知，P１，P３相对于BS３的余式都是０，故最后得PS的特征列CS＝BS３＝｛P５，P４，P２｝，其中８６４２C１＝P５＝－x１＋４x１－８x１＋３２x１－１６，４C２＝P４＝（４x１）x２－x１－４，２C３＝P２＝－２x３＋x１畅对于上例，特征列中第一个多项式仅含未定元x１，第二个仅含x１，x２，第三个含x１，·６１·\nx２，x３畅所以我们又称这种多项式列为三角列．对于给定的多项式组PS，用上述方法求得它的特征列CS的过程与线性方程组的Gauss消元法有同样的效果，故吴特征列方法又称为吴消元法．2畅4畅2多项式方程组求解在线性方程组中，我们总是首先利用Gauss消去法将给定的方程组化为三角形，该三角形方程组与原方程组有相同的解；然后再回代求解这个三角形方程组，以得到原方程组的解．对于多项式方程组的求解，也可以采取同样的思想方法．分析前面特征列的构造过程，恰好是将原方程组化为三角形方程组的过程．将该过程写成下列形式：PS１＝PSPS２＝PS１∪RS１⋯PSm＝PSm－１∪RSm－１BS１BS２⋯BSm＝CSRS１RS２⋯RSm＝碬．分析上述过程，其中每个BSi都是一个三角列，如果对某个i，BSi与原方程组有相同的解集合，当然可以求解该三角列，以得到解．但是一般情况下未必有此结论，不过对最后所得的特征列，这个结论是正确的．下面我们来证明这一点．首先引进记号nzero（PS）＝｛a∈K|对任何P∈PS，成立P（a）＝０｝．引理2畅4畅1在特征列的构造中，以下等式成立：zero（PS１）＝zero（PS２）＝⋯＝zero（PSm）．证明只需证明zero（PS１）＝zero（PS２）即可，其他情形证明是同样的．首先由定义得PS１炒PS２，由此可得zero（PS１）车zero（PS２）．为证反包含关系，注意到PS２的定义，只要证明对任何R∈RS１与a∈zero（PS１），R（a）＝０即可．由RS１的定义，对任何R∈RS１，存在P∈PS１，使得ssIr１r⋯I１P＝Q′rAr＋⋯＋Q′１A１＋R，（２畅４畅５）其中A１，⋯，Ar为PS１的基本列，I１，⋯，Ir分别为A１，⋯，Ar的初式．于是对任何a∈zero（PS１），因P，A１，⋯，Ar∈PS１，有P（a）＝A１（a）＝⋯＝Ar（a）＝０．再由式（２畅４畅５），即知R（a）＝０．对PSm，因为其基本列BSm为特征列CS，所以PSm中的所有多项式相对于CS的余式都是０．设特征列为CS：A１，⋯，Ar，Ai的初式为Ii，并记J＝I１⋯Ir，则有·６２·\n定理2畅4畅4zero（PS）＝zero（CS／J）＋zero（PS，I１）＋⋯＋zero（PS，Ir），其中，zero（CS／J）＝zero（CS）－zero（J），“＋”表示求并集．证明对任何P∈PSm，由特征列的定义，存在整数s１，⋯，sr及多项式Q′１，⋯，Q′r，使得ssIr１r⋯I１P＝Q′rAr＋⋯＋Q′１A１畅（２畅４畅６）由此容易证得zero（PSm）＝zero（CS／J）＋zero（PSm，I１）＋⋯＋zero（PSm，Ir）．再由引理２畅４畅１及zero（PSm，Ii）＝zero（PS，Ii），即可证明本定理．当CS为矛盾列时，zero（CS）＝碬．因为CS炒PSm，zero（CS）车zero（PSm）＝zero（PS），即zero（PS）＝碬．应用上述定理，可将多项式组PS的求解问题转化成若干个简单方程组的求解问题．将（PS，Ii）视为新的方程组，再求其特征列CS′．注意Ii为Ai的初式，它相对于CS必定为约化的（练习）．于是由定理２畅４畅４，CS′的级别低于CS的级别．利用这一点可以证明以下定理．定理2畅4畅5设PS为给定的多项式集合，则存在一系列特征列CSl，l＝１，２⋯，使得zero（PS）＝钞zero（CSl／Jl），l其中Jl为特征列CSl中多项式的初式之积．（０）（０）（１）证明将定理２畅４畅４中的PS记为PS，特征列记为CS，（PS，Ii）记为PSi，（１）（１）（１）i＝１，⋯，r．应用定理２畅４畅６，又得特征列CSi与CSi的初式与PSi组合而成的新（２）（１）多项式组PSi，j＝１，⋯，ri．将CSi那些矛盾列去掉（将剩下的个数仍记为r）．对j（１）PSi，j＝１，⋯，ri，i＝１，⋯，r，再用定理２畅４畅４可得特征列组的序列j（２）CSi，j＝１，⋯，ri，i＝１，⋯，r，j且有（０）（１）（２）CS巢CSi巢CSi．j（２）（２）去掉特征列中的矛盾列，再对PSi与CSi中多项式的初式组成的多项式组利用定理jj２畅４畅４，又可得一组升列与一组多项式组．继续下去，可得一列严格下降的升列序列．由推论２畅４．１，这种严格降的升列序列是有限的，所以这种做法必在有限步内停止．做法停止处的特征列必为矛盾列，因为不然则可继续做下去．已知以矛盾列为特征列的多项式组的零点集是空集，反复应用有限次定理２畅４畅４即得本定理．例2畅4畅2求解多项式方程组２P１＝－x２＋x１x２＋１＝０，２P２＝－２x３＋x１＝０，２P３＝－x３＋x１x２－１＝０．·６３·\n我们在例２畅４畅１中已经求得该多项式组的特征列８６４２C１＝－x１－４x１＋８x１＋３２x１－１６，４C２＝（４x１）x２＋x１－４，２C３＝－２x３＋x１畅显然，各多项式的初式分别为I１＝－１，I２＝４x１，I３＝－２畅由定理２畅４畅４有zero（PS）＝zero（CS／J）＋zero（PS，I１）＋zero（PS，I２）＋zero（PS，I３）．容易看出，对i＝１，３，｛P１，P２，P３，Ii｝的特征列为矛盾列．又J＝I１I２I３＝８x１＝０的解x１＝０不是特征列的零点，即zero（CS／J）＝zero（CS）．又可算出（PS，I２）的特征列亦为矛盾列．于是zero（P１，P２，P３）＝zero（C１，C２，C３）．求解C１＝０，可得８个根x１i，i＝１，⋯，８畅注意，所有这些根都是非零的，分别代入C２＝０，C３＝０，又可解得４x２i＝（４－x１i）／（４x１i），２x３i＝x１i／２，i＝１，⋯，８畅2畅4畅3定理机械化证明假设K为域．一个几何定理在引进适当的坐标系后，就像在解析几何中所做的那样，其假设条件与结论可以用它们点的坐标之间的数量关系来描述．在初等几何中，这些关系一般都是多项式的．这个过程称为几何定理的代数化．因此定理的假设条件可用一组多项式HS炒K［x１，⋯，xn］来表示．而相应的结论也可用一多项式G＝０来描述．因此有定义2畅4畅1一个定理定义为T＝｛HS，G｝，其中HS为假设，G为结论．定理2畅4畅6设HS为一定理的假设，G为结论．CS：A１，⋯，Ar为HS的特征列，J＝I１⋯Ir为Ai的初式之积，则在非退化条件J≠０之下，当G相对于CS的余式为０时，结论G＝０可由Ai＝０，i＝１，⋯，r推出．证明将G对特征列求余，则有ssI１r１⋯IrG＝Q１A１＋⋯＋QrAr＋R．如果余式R＝０，则对任何使得假设条件成立且又满足非退化条件的点a∈zero（CS／J），显然有G（a）＝０．这表示结论成立．为了简单起见，只给出了上面特殊情况的定理．实际上尚有很多情形需要讨论．比如：１）当余式不为零时结论是否成立．２）在退化条件J＝０时结论是否成立．·６４·\n这里不再作介绍，有兴趣的读者请参阅吴文俊编著的枟几何定理机器证明的基本原理枠（科学出版社，１９８４）．例2畅4畅3Desargues定理的证明．假设平面上任意两条直线l１，l２交于点O．在l１上任取两点A１，A２，在l２上任取一点B１，过A２做直线平行于A１B１，设其交l２于B２畅在平面上任取一点C１，过A２，B２分别做直线平行于A１C１，B１C１，两直线交于C２（图２畅４畅１）．图２畅４畅１结论O，C１，C２三点共线．证明首先将问题代数化．取坐标：O（０，０），A１（u１，０），A２（u２，０），B１（０，u３），C１（u４，u５），B２（０，x１），C２（x２，x３）．注意这里各点坐标的写法．对那些任取的点，其坐标都用ui表示，而对那些非任取的点，其坐标都用xi表示．利用这些坐标，假设条件可以写成H１＝u１x１－u２u３＝０，（A１B１∥A２B２）H２＝u４（x３－x１）－x２（u５－u３）＝０，（B１C１∥B２C２）H３＝（u４－u１）x３－u５（x２－u２）＝０．（A１C１∥A２C２）而结论可以写成G＝u４x３－u５x２＝０．为应用定理２畅４畅６，先求HS的（相对于u１＜⋯＜u５＜x１＜⋯＜x３的字典序的）特征列CSC１＝I１x１－u２u３，C２＝I２x２＋（u４－u１）u４x１＋u２u４u５，C３＝I３x３－（u５－u３）x２－u４x１畅其中I１＝u１，I２＝u１u３－u１u５－u３u４，I３＝u４畅计算G对CS的余式可知其为零．由定理２畅４畅６知，在非退化条件J＝I１I２I３≠０的情况下，Desargues定理成立．下面分析退化条件J＝I１I２I３＝０．若I１＝u１＝０，表示点A１取在O点．这时点B２无定义，定理无意义．在I３＝u４＝０时，定理仍然成立．如图２畅４畅２所示，这时点C１落在l２上，可以看出C２此时也在l２上．而l２上的点的第一个坐标都是零，即有x２＝０，由此可知G＝－u５x２＝０．·６５·\n图２畅４畅２当I２＝u１u３－u１u５－u３u４＝０时，如图２畅４畅３所示，点C１（u４，u５）在直线A１B１上，C２无确定的定义，定理不成立．图２畅４畅３在几何问题中，无论是欧氏几何还是非欧氏几何，利用吴方法不但能够证明定理，还可以发现新定理与未知关系，限于篇幅，我们这里不再介绍．练习１畅设D为UFD，A，B∈D［X］．若存在b∈D，Q，R∈D［X］，整数l，使得lbA＝QB＋R，l证明gcd（bA，B）＝gcd（B，R）．２畅设对某固定的m，定义n元单项式全体T上的一个序＜m如下：iiijjjx１x２⋯xnx１x２⋯xn，１２n＜m１２n当且仅当或者存在l，１≤l≤n，使il＜jl且ik＝jk，１≤k≤l，或者ik＝jk，１≤kiijj≤m且xm＋１nm＋１nm＋１⋯xn＜txm＋１⋯xn，其中＜t表示分次字典序．证明＜m是一个容许的单项序．倡３畅若P，R为多项式，G为多项式集合．证明若PGR≠０，令G′＝G∪｛R｝，·则PG′０．４畅设P，Q，R∈K［X］而S炒K［X］．如果P－QSR，则存在珚P，Q珡，使得PS珚P，QSQ珡且R＝珚P－Q珡．·５畅假设P，Q∈K［X］，使得对某S炒K［X］成立P－QS０，则存在R∈倡倡K［X］，使得PSR，QSR．６畅假设P１，P２∈K［X］与S炒K［X］，使得P１SP２，则对任何R∈K［X］存·６６·\n倡倡在多项式Q，使得P１＋RSQ，P２＋RSQ．７畅试举一例：一个多项式理想的理想基G是多种容许单项序下的Groebner基．８畅证明定理２畅３畅４畅９畅证明定理２畅３畅５畅１０．证明定理２畅３畅７畅１１畅利用定理２畅３畅４与２畅３畅７改进Buchberger算法．４３１２畅判断是否有A＝xz－xyz∈枙P１，P２，P３枛，其中３２２２２２P１＝xyz－xz，P２＝xyz－xyz，P３＝xy－z畅若有，则求A１，A２，A３，使得A＝A１P１＋A２P２＋A３P３畅１３畅设I＝＜x２－a２，⋯，xn－an＞，证明在多项式A的I唱adic表示中，若S＝（i）（j２，⋯，jn）∈J，则有jj（i）１抄２⋯抄nAS（x１）＝jjA（x１，a２，⋯，an）．j２！⋯jn！抄x２⋯抄xn２n１４畅设CS：A１，A２，⋯，Ar为特征列，Ii为Ai的初式，证明它相对于CS必定为约化的．·６７·\n第3章多项式最大公因子的计算多项式最大公因子的计算是计算机代数中最基本的问题之一．在符号计算中，很多问题要涉及到最大公因子的计算．例如为使运算效率更高，在有理分式的表示中我们常常希望分子与分母互素，这样对给定的原始数据，就要求我们去掉其最大公因子．又如在因式分解或积分等许多计算中也都以最大公因子计算作为子算法．因此设计最大公因子计算的有效算法，对提高符号计算的效率十分有意义．３畅１多项式的余式序列与结式3畅1畅1多项式余式序列我们先来考虑一元多项式的最大公因子问题．整数最大公因子计算的方法在多项式情形中仍然成立．因为在计算机代数中，所有的计算都是精确的，故只需讨论有理系数的多项式．而有理系数的多项式问题与整系数多项式问题可以相互转化，因此我们只需讨论整系数多项式问题即可．设K为域，则K［x］为Euclid整环．对任何A，B∈K［x］，B≠０，由带余除法，存在唯一的Q，R∈K［x］，使得A＝QB＋R，（３畅１畅１）其中deg（R）＜deg（B）或R＝０．这里我们要讨论的是如何利用这个结果来计算给定的A，B的最大公因子．对上式中的A，B，Q，R，为了方便地描述它们之间的关系，仍记余式与商为R＝rem（A，B），Q＝quo（A，B）．（３畅１畅２）对多项式的最大公因子计算问题，Euclid方法仍然有效．算法3畅1畅1Euclid算法：InputA，B；OutputU＝gcd（A，B）；R：＝B；U：＝A；V：＝B；whileR≠0doR：＝rem（U，V）；U：＝V；V：＝R；命题3畅1畅1Euclid算法是有限终止的，且当算法终止时，U＝gcd（A，B）．此命题的证明留作练习．例3畅1畅1设８６４３２A＝x＋x－３x－３x＋８x＋２x－５，·６８·\n６４２B＝３x＋５x－４x－９x＋２１，求它们的最大公因子．按Euclid算法，得如下余式序列：５４１２１－x＋x－，９９３１１７２４４１－x－９x＋，２５２５２３３１５０１０２５００x－，１９７３３２１９５１２８８７４４８２１－．５４３５８９２２５因为余式序列的最后一个是非零常数，故gcd（A，B）＝１畅有时为了某种需要，要求计算一个多项式模另一多项式的逆，即给定A，B∈K［x］，求多项式W，使得WA≡１modB．如果这样的W存在，则有B|（WA－１），即有V存在，使得WA－１＝VB，这说明A，B互素．如果A，B互素，由定理２畅１畅３知，这样的W是肯定存在的．至于W的计算，可以用第２章商环中元素的求逆方法，也可以用扩展Euclid方法．当A，B互素时，由定理２畅１畅３知，存在W，V，使得１＝WA＋VB，其中deg（W）＜deg（B），deg（V）＜deg（A）．显然这样的W即为A模B的逆．算法3畅1畅2扩展Euclid算法：InputA，B，deg（B）≤deg（A）；OutputC，W，V；S：＝［1，0］；T：＝［0，1］；whileB≠0doR：＝rem（A，B）；Q：＝quo（A，B）；L：＝S－QT；A：＝B；B：＝R；S：＝T；T：＝L；returnA，S；当A，B都是Z［x］上的多项式时，如果它们有非常数的公因子，由Gauss引理，该公因子也可取为整系数的．但是Euclid算法必须在域内进行．如果我们希望只进行环上的计算，直接套用Euclid算法是不行的．为达到这个目的，在Euclid算法中，每步用伪除来代替除法，这样每步所得的伪余多项式仍然是整系数的．自然，当算法终止时，得到的多项式也是整系数的．对于上例，应用前面所说的算法，则有４２－１５x＋３x－９，２１５７９５x＋３０３７５x－５９５３５，·６９·\n１２５４５４２８７５１４３７５０x－１６５４６０８３３８４３７５００，１２５９３３３８７９５５００７４３１００９３１１４１９９２１８７５００．但是这样做的后果是系数迅速膨胀，给存储及运算都带来了困难．那么能否找到一种算法，使得系数膨胀的比较缓慢，而运算又保持在整数环内呢？回答是肯定的，对前面所说的方法加以改造就可以达到这样的目的，为此我们先来讨论多项式余式序列．定义3畅1畅1设R为环，A，B∈R［x］，deg（A）≥deg（B），则A，B的多项式余式序列是满足下列条件的多项式序列R０，R１，⋯，Rk：１）R０＝A，R１＝B．２）αiRi－１＝QiRi＋βiRi＋１，其中αi，βi∈R．３）prem（Rk－１，Rk）＝０．利用定理２畅１畅６容易证明，如果A，B都是本原多项式，则pp（Rk）＝gcd（A，B）．在以上定义中，αi的选取应该使得满足αiRi－１＝QiRi＋R，且deg（R）＜deg（Ri）或R＝０的Ri∈R［x］存在．而βi则应选取为R的系数尽可能“大”的公因子．当R为域时，若取αi＝βi＝１，则｛Ri｝即为Euclid方法所得的多项式序列．但是当R为环时，就难以再取αi＝βi＝１，这时未必存在这样的Ri∈R［x］．记δi＝deg（Ri－１）－deg（Ri），如果取δ＋１αi＝（lc（Ri））i，（３畅１畅３）βi＝cont（prem（Ri－１，Ri）），则得第２章介绍的伪余序列．这样计算的结果虽然系数膨胀得最慢，但每步要计算一个多项式的容度，计算量较大．如果放宽对系数膨胀的控制，减少计算量，可取δ＋１δ＋１αi＝（lc（Ri））i，β１＝（－１）１，δβi＝－（lc（Ri－１））ψii，２≤i≤k，ψ１＝－１，（３畅１畅４）δ１－δψi＝（－lc（Ri－１））i－１ψi－１i－１，２≤i≤k．所得的多项式序列称为A，B的子结式余式序列．例3畅1畅2设８６４３２A＝x＋x－３x－３x＋８x＋２x－５，６４２B＝３x＋５x－４x－９x＋２１，用子结式余式序列方法求它们的最大公因子．取R０＝A，R１＝B，按上述公式可算得δ１＝２，α１＝２７，β１＝－１，４２R２＝１５x－３x＋９，δ２＝２，ψ２＝－９，α２＝３３７５，β２＝－２４３，２R３＝６５x＋１２５x－２４５畅如此下去，最后得·７０·\nR４＝９３２６x－１２３００，R５＝２６０７０８畅例３畅１畅３在定义３畅１畅１中，若取δ＋１αi＝（lc（Ri））i，β１＝１，（３畅１畅５）βi＝αi－１，２≤i≤k，则所得的多项式余式序列称为约化多项式余式序列．对于多项式８６４３２A＝x＋x－３x－３x＋８x＋２x－５，６４２B＝３x＋５x－４x－９x＋２１，其约化多项式余式序列为４２R２＝－１５x＋３x－９，２R３＝５８５x＋１１２５x－２２０５，R４＝－１８８８５１５０x＋２４９０７５００，R５＝５２７９３３７００．在定义３畅１畅１中，αi和βi的不同定义则给出不同的多项式余式序列．注意对所给的例子，所有的αi的取法都是一样的，实质上它们都是基于对伪余的改造而得到的，既注重对系数膨胀的控制，又注重对计算量的控制．作为计算最大公因子的算法，子结式余式序列方法是这一类方法中最好的，它的特点是：１）计算量较小．２）序列中的每个多项式都是整系数的．３）系数的（位数）长度增长是线性的．3畅1畅2结式mi定义3畅1畅2设R为交换环，A，B∈R［x］，为非零多项式，其中A＝∑aix，i＝０niB＝∑bix，则A，B的Sylvester矩阵定义为（m＋n）阶方阵：i＝０amam－１⋯a１a０amam－１⋯a１a０⋯⋯⋯⋯amam－１⋯⋯a０M＝．（３畅１畅６）bnbn－１⋯b１b０bnbn－１⋯b１b０⋯⋯⋯⋯bnbn－１⋯⋯b０定义3畅1畅3多项式A，B∈R［x］的结式，记作res（A，B），定义为A，B的Sylvester矩阵的行列式．对任何B∈R［x］，定义res（０，B）＝０．而对非零常数A，B∈R，则定义res（A，B）＝１畅有时为了强调未定元，也将A，B的结式记作resx（A，B）．·７１·\n无论是理论研究还是实际计算，结式对多项式问题都是有力的工具，以后我们将看到这一点．例3畅1畅4对于多项式４３２A＝３x＋３x＋x－x－２，３２B＝x－３x＋x＋５，其结式为res（A，B）＝det（M）＝０，其Sylvester矩阵为３３１－１－２０００３３１－１－２０００３３１－１－２M＝１－３１５０００．０１－３１５００００１－３１５００００１－３１５多项式A，B的结式可以用来判断A，B是否有非平凡的公因子．后面我们将证明两个多项式有非平凡公因子，当且仅当其结式为０．定理3畅1畅1设A，B∈R［x］为次数分别为m，n＞０的多项式，则存在满足deg（S）＜n，deg（T）＜m的S，T∈R［x］，使得A（x）S（x）＋B（x）T（x）＝res（A，B）．（３畅１畅７）证明设A，B的系数分别为ai与bi，构造m＋n阶线性方程组m＋n－１m＋n－２n－１n－１amx＋am－１x＋⋯＋a０x＝xAm＋n－２n－１n－２n－２amx＋⋯＋a１x＋a０x＝xA⋯⋯⋯mm－１amx＋am－１x＋⋯＋a０＝Am＋n－１m＋n－２m－１m－１bnx＋bn－１x＋⋯＋b０x＝xB⋯⋯⋯nn－１bnx＋bn－１x＋⋯＋b０＝B利用矩阵形式，以上方程组可以写成m＋n－１n－１xxA（x）……M＝．（３畅１畅８）xxB（x）１B（x）利用Cramer法则求解最后一个分量１，得·７２·\nn－１amam－１⋯a１a０xAamam－１⋯a１a０⋯⋯⋯⋯amam－１⋯a１Adet（M）＝det．m－１bnbn－１⋯b１b０xBbnbn－１⋯b１b０⋯⋯⋯⋯bnbn－１⋯b１B将上式右端的行列式按最后一列展开即得式（３畅１畅７）．推论3畅1畅1设R为UFD，A，B∈R［x］，A，B有非平凡公因子，则当且仅当res（A，B）＝０．证明假设A，B有非平凡公因子，但res（A，B）≠０，则由定理３畅１畅１，A，B的任何公因子都将整除结式．但是结式为常数，这说明A，B可能的公因子必是０次的，即A，B的公因子都是平凡的，矛盾，故必res（A，B）＝０．反之，假设res（A，B）＝０，则由定理３畅１畅１，有多项式S，T使得A（x）S（x）＝－B（x）T（x）．如果A，B互素，则由上式可推出B整除S，但是deg（S）＜deg（B），这是不可能的．从而A，B有非平凡公因子．一个有趣的结论是，Z［x］中的多项式A，B的最大公因子可以通过对它们的Sylvester矩阵进行行变换得到．定理3畅1畅2设A，B∈Z［x］．如果只允许使用行变换将A，B的Sylvester矩阵化为行阶梯形，则最后一个非零行即为A，B的（在Q量．证明如果A，B互素，则res（A，B）≠０．此时A，B的Sylvester矩阵M是非奇异的，经行变换化为行阶梯形后，其最后一个非零行必为最后一行，且该行只有最后一个元素非零．它对应的多项式为常数，此时A，B只有平凡的公因子．当res（A，B）＝０时，A，B有非平凡公因子．由定理２畅１畅２知，存在多项式S（x），T（x）满足deg（S）＜deg（B），deg（T）＜deg（A），使得gcd（A，B）＝A（x）S（x）＋B（x）T（x）．（３畅１畅９）注意，关于S，T的次数的限制，式（３畅１畅９）表明gcd（A，B）的系数向量是M的行向量的线性组合．假设M化为阶梯形后最后一个非零行对应的多项式为D，利用定理３畅１畅１证明中的式（３畅１畅８）可知，有W，V使得D（x）＝A（x）W（x）＋B（x）V（x）．因gcd（A，B）|D，D的系数向量的第一个非零元所在的列数必定不大于gcd（A，B）的系数的第一个非零元所在的列数．可以断言，这两个系数向量必定只相差一常数倍．不然，一方面因gcd（A，B）的系数向量是M的行向量的线性组合，记C为gcd（A，B）的系数向量，则有Mrank＝rank（M）．C·７３·\n另一方面，若C的第一个非零元所在的列数大于D的第一非零元所在的列数，或者虽然二者第一非零元在同一列，但是二向量不是倍数关系，则由线性代数知识可知Mrank＞rank（M）．C这个矛盾说明，C和D只能相差一常数倍，即D亦为A，B在Q［x］上的最大公因子．３畅２模方法利用多项式余式序列求最大公因子仍然需要进行大整数计算，当所给多项式的次数较高时，计算过程中系数的膨胀问题就会更加突出．为了提高计算效率，避免大整数的计算，就必须寻找另外的方法．为此考虑多项式环的同态映射Φp：Z［x］Zp［x］，ii钞aix|钞Φp（ai）x，ii其中p为素数，Φp（ai）表示ai的模p同态像，即Φp（ai）≡aimodp，－p／２＜Φp（ai）＜p／２畅容易验证如此定义的Φp的确为环同态．后面我们将记Φp（A）为Ap．设给定A，P∈Z［x］．若P|A，则有Q使A＝QP．从而其同态像满足Ap＝QpPp．上式说明，若P为A，B的公因子，则Pp相应地为Ap，Bp的公因子．因此若D＝gcd（A，B），且素数p使得D的系数的绝对值不超过p／２，只要我们能够求出Ap，Bp的最大公因子，则有可能成立D＝Dp＝gcd（Ap，Bp），从而求得D＝gcd（A，B）．而求Ap，Bp的公因子时，系数的计算又可控制在绝对值小于p／２的范围内．这种方法称为模方法（modularmethods）．在讨论模方法之前，我们先来看一个例子．例3畅2畅1设８６４３２A＝x＋x－３x－３x＋x＋２x－５，６４２B＝３x＋５x－４x－９x＋２１，则A，B模５的像为８６４３２A５＝x＋x＋２x＋２x＋x＋２x，６２B５＝－２x＋x＋x＋１畅下面我们计算A５，B５的公因子，注意计算是模５进行的．２２A５＝２（x＋１）B５＋２x－２，２R２＝２（x－１）；４２B５＝（－x－x＋２）R２＋x，R３＝x；R２＝２xR３－２，R４＝－２畅即gcd（A５，B５）＝１畅因此若P为A，B的公因子，则P的同态像P５必整除gcd（A５，·７４·\nB５）＝１，由此可知P５＝１畅我们断言，A，B的任何公因子都必为常数．不然，设整系数多项式P为A，B的公因子，则有Q使得B＝PQ．不妨设mniiP＝钞pix，Q＝钞qix，m，n≤６畅i＝０i＝０注意B是本原多项式，由Gauss引理可知，P，Q也都是本原的．又由前段分析可知P５＝１，故pi＝０mod５，i＝１，⋯，m．比较系数可知必有－２≡p０qnmod５畅由此推得n＝６，m＝０．这说明P为平凡因子，从而A，B的最大公因子为１畅一般说来，若A，B的最大公因子为D，p为任一素数，则有Dp|gcd（Ap，Bp），从而deg（Dp）≤deg（gcd（Ap，Bp））．但一般等式未必成立．例如，A＝x＋３，B＝x－２，则gcd（A５，B５）＝x－２，但D＝gcd（A，B）＝１，即deg（D５）＜deg（gcd（A５，B５））．在用模方法计算时，为通过gcd（Ap，Bp）求得D＝gcd（A，B），我们总希望成立D＝gcd（Ap，Bp）．但是一般使这个等式成立的条件很难分析，为此我们寻求Dp＝gcd（Ap，Bp）成立的条件，再要求D＝Dp，则得D＝Dp＝gcd（Ap，Bp）．分析可知，前一个等式要求p大于D系数的绝对值的２倍，而后一个等式则对素数p有进一步要求．因此要想利用模方法求得多项式的最大公因子，素数p的恰当选择十分重要．我们首先来估计多项式因子系数的界．qi定理3畅2畅1（Landau唱Mignotte不等式）若Q，P∈Z［x］，Q＝∑bix为P＝i＝０pi∑aix的因子，则i＝０qbpqq２钞|bi|≤２钞ai．i＝０api＝０证明见附录A．mnii推论3畅2畅1A＝∑aix与B＝∑bix的最大公因子的系数不超过i＝０i＝０mn２min（m，n）gcd（a１２１２．m，bn）min钞ai，钞bi|am|i＝０|bn|i＝０deg（D）证明设A，B的公因子为D，则必有deg（D）＜min（m，n），从而２＜min（m，n）２．另一方面，因D为A，B的因子，lc（D）必同时整除am，bn，从而lc（D）≤gcd（am，bn），再利用Landau唱Mignotte不等式即得．mnii推论3畅2畅2A＝∑aix与B＝∑bix的最大公因子的系数不超过i＝０i＝０mn２min（m，n）gcd（a１２１２．０，b０）min钞ai，钞bi|a０|i＝０|b０|i＝０lmlmiiii证明若C＝∑cix为A＝∑aix的因子，则C珚＝∑cl－ix为A珚＝∑am－ixi＝０i＝０i＝０i＝０·７５·\n的因子，反之亦然．对A珚，B珚应用推论３畅２畅１即得．以上的一些结论告诉我们，可用于模方法的素数的粗略下界M，当p＞２M时，则可保证D＝Dp．但并非大于这些下界的素数就可以用于模方法，为保证Dp＝gcd（Ap，Bp）成立，素数p还必须满足下述条件．命题3畅2畅1若素数p不能整除lc（gcd（A，B）），则deg（gcd（Ap，Bp））≥deg（gcd（A，B））．证明记D＝gcd（A，B），则因D|A，D|B，可知Dp|gcd（Ap，Bp）．这说明deg（Dp）≤deg（gcd（Ap，Bp））．但p嘲lc（D），所以deg（D）＝deg（Dp）≤deg（gcd（Ap，Bp））．推论3畅2畅3若素数p不同时整除lc（A）与lc（B），则deg（gcd（Ap，Bp））≥deg（gcd（A，B））．证明p不同时整除lc（A），lc（B），令D＝gcd（A，B），则必p嘲lc（D）．不然设p|lc（D），则因lc（D）|lc（A），lc（D）|lc（B），可推出p同时整除lc（A），lc（B），矛盾．再由命题３畅２畅１即得本推论．定理3畅2畅2设D＝gcd（A，B），若p满足推论３畅２畅３的条件，且p嘲resx（A／D，B／D），则gcd（Ap，Bp）＝Dp．证明易见resx（A／D，B／D）≠０．由推论３畅２畅３知，Dp≠０．由定理３畅１畅１知，存在S，T，使得S（A／D）＋T（B／D）＝resx（A／D，B／D），由此得SA＋TB＝resx（A／D，B／D）D，进而有SpAp＋TpBp＝resx（A／D，B／D）pDp．由此可推出gcd（Ap，Bp）|Dp．但一般总有Dp|gcd（Ap，Bp），故gcd（Ap，Bp）＝Dp．定义3畅2畅1如果gcd（Ap，Bp）＝gcd（A，B）p，则称该问题的约化是良好的，或p是良约化的，否则称为劣约化的．定理３畅２畅２说明劣约化的素数p是有限的．这是因为可以整除resx（A／D，B／D）的整数显然是有限的．因此在计算时，如果我们随机地选取素数p，则几乎可以满测度地取得良约化的素数．例3畅2畅2设６４２A＝３x＋５x－４x－９x＋２１，·７６·\n８６４３２B＝x＋x－３x－３x＋x＋２x－５畅则在模２运算下有６４A２＝x＋x＋x＋１，８６４３２B２＝x＋x＋x＋x＋x＋１，且５４A２≡（x＋１）（x＋x＋１）mod２，７６３B２≡（x＋１）（x＋x＋x＋x＋１）mod２畅这说明deg（gcd（A２，B２））≥１畅但我们已知gcd（A，B）＝１，按照定义３畅２畅１，２是劣约化的．在以后的素数中，３整除A领项系数，因此有可能是劣约化的，由例３畅２畅１可知，素数５是良约化的．算法3畅2畅1最大公因子的模方法：InputA，Bprimitive；OutputD；M：＝Landau唱Mignotte唱bound（A，B）；dop：＝find唱large唱prime（2M）；ifdeg（Ap）＝deg（A）ordeg（Bp）＝deg（B）；thenD：＝modular唱gcd（A，B，p）；ifD｜AandD｜B；thenreturnD；forever；在算法３畅２畅１中，Landau唱Mignotte唱bound（A，B）表示利用Landau唱Mignotte不等式求得A，B的因子的系数的一上界；find唱large唱prime（２M）表示随机地选取一个大于２M的素数p；当该素数不同时整除A和B的领项系数时，modular唱gcd（A，B，p）用模p的Euclid方法计算A，B的最大公因子D；若D整除A和B，则D为所求，否则重新选取素数p进行计算．当然上述算法仅仅是说明性的，真正在机器上实现时还需要考虑许多细节问题．命题3畅2畅2设A，B为给定的本原多项式，M为利用Landau唱Mignotte不等式求得的A，B的因子的系数的一上界，p＞２M为某一正整数，则当gcd（Ap，Bp）同时整除A和B时，gcd（Ap，Bp）＝gcd（A，B）；否则p是劣约化的．证明当p＞２M时，易见Dp＝D．若gcd（Ap，Bp）同时整除A和B，则应有gcd（Ap，Bp）|D．但一般总有D＝Dp|gcd（Ap，Bp），从而gcd（Ap，Bp）＝D．若gcd（Ap，Bp）不同时整除A和B，则由D＝Dp|gcd（Ap，Bp）可知，存在Q，使得gcd（Ap，Bp）＝DQ．如果Q为常数，则因gcd（Ap，Bp）可选为本原形式，可知Q＝１，这与gcd（Ap，Bp）不同时整除A和B矛盾，故Q非常数，此时必有deg（Q）＞０，于是可以推知deg（D）＝deg（Dp）＜deg（gcd（Ap，Bp）），这说明p是劣的．命题３畅２畅２保证算法３畅２畅１终止时，计算所得结果就是A和B的最大公因子，而劣约化素数的有限性又可以保证算法是有限步终止的．·７７·\n利用算法３畅２畅１原则上可以计算多项式的最大公因子，但是利用Landau唱Mignotte不等式确定的素数p有可能很大，如果直接用算法３畅２畅１计算多项式的最大公因子，就难以达到利用较少的数据位数进行计算的目的．我们希望利用孙子剩余定理来改进上述方法，以达到使用尽可能少的数据位数计算的目的，我们称为改进的模方法．改进模方法的基本思想是：假设p，q为两个互素的良约化整数，且已经利用某种（i）（i）方法求得Ap，Bp与Aq，Bq的最大公因子Dp，Dq，此时应存在W，V，i＝p，q，使得（p）（p）Dp＝WAp＋VBp，（q）（q）Dq＝WAq＋VBq，（r）（r）其中deg（D）＝deg（Dp）＝deg（Dq），deg（W）＜deg（Br），deg（V）＜deg（Ar），r＝p，q．对上面两个等式中的多项式的系数应用孙子定理，设deg（D）＝m，（p）m（p）（p）Dp＝a０x＋⋯＋am－１x＋am，（q）m（q）（q）Dq＝a０x＋⋯＋am－１x＋am，考虑同余方程（pq）（p）ai≡aimodp，（pq）（q）ai≡aimodq，i＝０，１，⋯，m，则可求得（pq）（pq）m（pq）（pq）D＝a０x＋⋯＋am－１x＋am．（pq）（pq）同理，也应存在W，V，使得（pq）（pq）（pq）D＝WApq＋VBpq．（pq）假设Apq，Bpq的最大公因子为Dpq，则应有Dpq整除D，但是p，q是良约化的，pq也（pq）（pq）应为良约化的，故deg（D）＝deg（Dpq）＝deg（D），从而Dpq，D只能相差一常数倍．再注意它们都取本原形式，可知二者相等．这说明仅对Dp，Dq应用孙子定理即可求得Apq，Bpq的最大公因子．一般地，我们可以先选两个良约化的素数p，q，分别计算A，B的模p与模q的公因子gcd（Ap，Bp）与gcd（Aq，Bq），然后再利用孙子定理求得A，B的模pq的公因子gcd（Apq，Bpq）．反复利用这种方法即可求得A，B的模任意大的整数的公因子．事实上，对于给定的p，q，我们无法知道它们是否为良约化的．但当它们满足推论３畅２畅３条件时，则有deg（D）＝deg（Dp）＝deg（Dq），在计算中，若deg（gcd（Ap，Bp））＜deg（gcd（Aq，Bq）），则必有deg（gcd（Aq，Bq））≠deg（Dq）＝deg（D），此时q必为劣约化的，可放弃q重新选择；否则，只好认为p，q是良约化的．算法3畅2畅2改进的最大公因子的模方法：InputA，B；OutputD；M：＝Landau唱Mignotte唱bound（A，B）；Avoid：＝gcd（lc（A），lc（B））；E0：p：＝find唱prime（Avoid）；D：＝modular唱gcd（A，B，p）；E1：ifdeg（D）＝0thenreturn1；·７８·\nKnown：＝p；Result：＝D；whileKnown≤2Mdop：＝find唱prime（Avoid）；D：＝modular唱gcd（A，B，p）；ifdeg（D）＜deg（Result）thengotoE1；ifdeg（D）＝deg（Result）thenResult：＝CRT（Result，Known，D，p）；Known：＝Known×p；ifResult｜AandResult｜B；thenreturnResult；gotoE0；在上述算法中，M仍然是利用Landau唱Mignotte不等式寻找A，B的因子的系数的一个上界；p为随机选取的不能整除Avoid的素数；modular唱gcd（A，B，p）表示用Euclid方法在模p运算下求得的A，B的最大公因子．循环体中的CRT（Result，Known，D，p）表示对多项式Result（moduloKnown）和D（modulop）利用孙子定理求A，B的模（Known×p）的最大公因子gcd（A（Known×p），B（Known×p））．在上算法中，有几种情况需要说明：１）在E１步有一个出口“ifdeg（D）＝０thenreturn１”，这说明对所选定的p，有deg（gcd（Ap，Bp））＝０．若C＝gcd（A，B），由推论３畅２畅３知，deg（C）≤deg（gcd（Ap，Bp））＝０，从而必有C＝１畅２）在循环体while唱do内有一个出口“ifdeg（D）＜deg（Result）thengotoE１”，这是因为对满足推论３畅２畅３的任意素数p，总成立deg（C）＝deg（Cp）≤deg（gcd（Ap，Bp）），因此若deg（gcd（Ap，Bp））＜deg（gcd（Aq，Bq）），则必有deg（gcd（Aq，Bq））≠deg（Dq）＝deg（D），说明对应Result的前一个素数是劣约化的，故转到步E１重新选素数．３）如果计算不从以上出口转出，则只好认为所进行的约化都是良好的；当循环体执行结束时，还需要检查所得的结果Result是否整除A，B．如果Result＝gcd（AKnown，BKnown）同时整除A和B，则有Dp|gcd（AKnown，BKnown）|D．但deg（D）＝deg（Dp），故D和Dp只相差一常数倍，又二者都是本原的，故必相等．４）若Known＞２M且Result＝gcd（AKnown，BKnown）不同时整除A和B，则由命题３畅２畅２知，Known是劣的，则需转到E０步重新选择素数计算．例3畅2畅3设A，B∈Z［x］，为４３２A＝x＋２５x＋１４５x－１７１x－３６０，５４３２B＝x＋１４x＋１５x－x－１４x－１５畅按上述算法则有M：＝４４６，Avoid：＝gcd（lc（A），lc（B））＝１畅取p＝５，模５计算得４５４２A５＝x－x，B５＝x－x－x＋x，·７９·\n４gcd（A５，B５）＝x－x．再模７计算得４３２A７＝x－３x－２x－３x－３，５３２B７＝x＋x－x－１，２gcd（A７，B７）＝x＋１畅因为deg（gcd（A７，B７））＜deg（gcd（A５，B５）），５是劣约化的．放弃模５的计算，再选下一个素数１１，模１１计算得４３２A１１＝x＋３x＋２x＋５x＋３，５４３２B１１＝x＋３x＋４x－x－３x－４，２gcd（A１１，B１１）＝x＋３x＋４畅２现在deg（gcd（A７，B７））＝deg（gcd（A１１，B１１））．设gcd（A７７，B７７）＝x＋ax＋b，其中－７７／２＜a，b＜７７／２畅由a≡３mod１１，a≡０mod７，b≡４mod１１，b≡１mod７，以及（－３）×７＋２×１１＝１，应用孙子剩余定理可求得a≡０＋（３－０）×（－３）×７≡１４mod７７，b≡１＋（４－１）×（－３）×７≡１５mod７７畅２２即D＝gcd（A７７，B７７）＝x＋１４x＋１５畅经检验，D|A且D|B，故D＝x＋１４x＋１５为所求．注意，在本例中，因为gcd（A７，B７）），gcd（A１１，B１１）的领系数都是１，故gcd（A７７，B７７）的领系数也直接取为１畅３畅３多元多项式的最大公因子3畅3畅1Euclid方法设A，B∈Z［x１，⋯，xr］．令R＝Z［x１，⋯，xr－１］，则A，B可视作系数为R中元素的关于未定元xr的一元多项式，即A，B∈R［xr］．我们称xr为主未定元．此时一元多项式最大公因子计算的许多方法都可以推广到多元情形．利用多项式的本原部分和容度的概念，记cont（A，r），pp（A，r）为视A为R［xr］中元素时A的容度和本原部分，gcd（A，B，xr）为A，B在R［xr］中的公因子，则由Gauss引理有gcd（A，B）＝cont（gcd（A，B，xr））pp（gcd（A，B，xr））＝gcd（cont（A，r），cont（B，r））×gcd（pp（A，r），pp（B，r））．此时pp（A，r），pp（B，r）为关于未定元xr的一元多项式，可用已知的方法，譬如说Euclid方法，求其最大公因子．而cont（A，r），cont（B，r）均为r－１元多项式．这样我们就把r元问题化归为r－１元问题，从而可递归地求得多元多项式的最大公因子．·８０·\n算法3畅3畅1多元多项式最大公因子的Euclid递归算法：Proceduregcd（A，B，r）Acont：＝cont（A，r）；App：＝A／Acont；Bcont：＝cont（B，r）；Bpp：＝B／Bcont；returnpp（Euclid（App，Bpp，r），xr）×gcd（Acont，Bcont，r－1）；算法中gcd（A，B，r）表示求r元问题的最大公因子；Euclid（App，Bpp，r）表示视App，Bpp为R［xr］上的一元多项式，并用Euclid方法求其最大公因子．设求得的公因子为D，则有Q１，Q２∈R［xr］，c１，c２∈R使得c１App＝DQ１，c２Bpp＝DQ２畅于是由Gauss引理，得App＝pp（D）pp（Q１），Bpp＝pp（D）pp（Q２）．即用Euclid算法求得最大公因子后，还需取其本原部分．gcd（Acont，Bcont，r－１）表示求一r－１元问题，即已把原问题降维．对于上算法中求R［xr］中多项式的容度，可用下列子算法求得．算法3畅3畅2容度的计算：Subprocedurecont（A，r）Result：＝coef（A，xr，0）；i：＝1；whileResult≠1andi＜deg（A，xr）doResult＝gcd（Result，coef（A，xr，i），r－1）；i：＝i＋1；returnResult；在上述子算法中，coef（A，xr，i）表示A关于主未定元xr的i次项的系数．整个子算法仍需调用计算r－１元多项式最大公因子的程序．例3畅3畅1设A（x，y），B（x，y）∈Z［x，y］，定义为２２２２A（x，y）＝（y－y－１）x－（y－２）x＋（y＋y＋１），２２２２B（x，y）＝（y－y＋１）x－（y＋２）x＋（y＋y＋２）．视x为主未定元，容易看出cont（A）＝cont（B）＝１畅即A，B都是本原的．用伪除方法求余式序列（把A，B看成x的一元多项式）得２２R２＝（２y－４y）x＋（y＋３y＋３），６５４３２R３＝－７y＋５y－１６y＋１５y－２６y＋１５y－９畅最后一个多项式关于x是常数，其本原部分为１，故gcd（A，B）＝gcd（cont（A），cont（B））pp（R３）＝１畅由本例可以看出，多元多项式的Euclid方法是不实用的．在计算过程中，多项式的系数与非主未定元的次数增长得都很快．·８１·\n3畅3畅2模方法已知在一元多项式中采用模方法可以控制中间未定元的系数与次数的增长．那么在多元情形模方法是否也可以应用它并具有同样的效果呢？回答是肯定的．下面我们就来讨论这个问题．设A，B，D∈Z［x１，x２，⋯，xr］且D|A，D|B，则有P，Q∈Z［x１，x２，⋯，xr］，使得A＝DP，B＝DQ．记L（２）（２）为将未定元xa＝x２－a，DL２用a代换所得的多项式，其他多项式定义类似，a则有（２）（２）P（２）（２）（２）（２）AL＝DLL，BL＝DLQL．aaaaaa这表明D（２）（２）（２）L仍为AL，BL的公因子．aaa例3畅3畅2设２２２２A＝（y－y－１）x－（y－２）x＋（y＋y＋１），２２２２B＝（y－y＋１）x－（y＋２）x＋（y＋y＋２），（y）取L２＝y－２，则A（y）２（y）２L＝x－２x＋７，BL＝３x－６x＋８畅２２易算得B（y）（y）（y）（y）L＝３AL－１３，即BL，AL互素．设D为A，B的最大公因子，由此可推２２２２得D（y）L＝１畅记lcx（D）为D的关于x的一元多项式的领项系数，则lcx（D）必同时整除２lcx（A），lcx（B），从而lcx（D）|gcd（lcx（A），lcx（B））．但gcd（lcx（A），lcx（B））＝gcd（y２－y－１，y２－y＋１）＝１，从而lc（y）关于x（D）＝１畅在将２赋予y以后，D与DL２x应具有相同的次数，由此推得D＝１畅从表面上看，我们是对多项式的某个未定元赋值，但实际上是将该多项式除以一个线性多项式求余．如果A∈Z［x１，⋯，xr］，a∈Z，考虑A伪除以xr－a，则有A＝Q（xr－a）＋C，其中C关于xr的次数为０，或者说C不含有未定元xr，在上式两端对xr赋以值a，则得A（r）（r）L＝CL＝C．aa如果A∈Z［x１，⋯，xr］，P∈Z［xr］，并且有lcx（P）＝１，degx（P）＝m，则由伪除rr性质有Q，RP∈Z［x１，⋯，xr］，使得A＝QP＋RP，degx（RP）＜m．r考虑商环Z［x１，⋯，xr］／枙P枛，记AP为A在环同态ΦP：Z［x１，⋯，xr］Z［x１，⋯，xr］／枙P枛下的同态像，即AP＝ΦP（A），则上述关系又可写成AP＝ΦP（A）≡AmodP．需要注意的是，当degx（P）＝m＞degx（A）时，A＝AP．类似于一元情形，我们也有rr·８２·\n良约化与劣约化的概念．定义3畅3畅1设R为整环，A，B∈R［y］［x］．R的元素a称为良约化的，如果（y）（y），B（y）gcd（A，B）L＝gcd（ALL），aaa否则称为劣约化的．和一元情形相类似，我们有下列结果．命题3畅3畅1设R为整环，A，B∈R［y］［x］，D＝gcd（A，B），则R的元素a是劣约化的当且仅当y－a整除resx（A／D，B／D）．证明完全类似于一元情形．命题3畅3畅2若a是良约化的，且y－a不同时整除A与B的（关于x的）领项系数，则gcd（A，B）与gcd（A（y）（y）L，BL）关于x有相同的次数．aa证明因为（y－a）嘲lcx（A）并且（y－a）嘲lcx（B），故（y－a）嘲lcx（gcd（A，B））．从而deg（y）x（gcd（A，B））＝degx（gcd（A，B）L）a（y），B（y）＝degx（gcd（ALL））．aa命题3畅3畅3若D为A的因子，则D关于y的次数不超过A关于y的次数．证明显然．有了以上的准备，我们可以讨论算法．算法的基本思想是递归地把r元问题化归为r－１元问题．假定已经能解决r－１元问题，我们来讨论r元问题的求解．设A，B∈Z［x１，⋯，xr］，则存在一最小正整数m，使得deg（A，xr－１）≤m，deg（B，xr－１）≤m．首先随机地取一整数v１，记L１＝xr－１－v１，Av＝AL，Bv＝BL，１１１１则Av，Bv为r－１元多项式．当deg（Av，xr）＝deg（A，xr）且deg（Bv，xr）＝１１１１deg（B，xr），即xr－１－v１不整除A和B的关于xr的最高项系数时，计算Av，Bv的最１１大公因子．这是一个r－１元问题，按假定是可以解决的，将计算结果记为gcd（Av，１Bv，r，r－１）．１再随机地取另一不同的整数v２，重复进行上述过程，将所得结果记为gcd（Av，２Bv，r，r－１）．如果degx（gcd（Av，Bv，r，r－１））＞degx（gcd（Av，Bv，r，r－１）），２r１１r２２说明v１是劣约化的，放弃关于v１的计算，重新选取一整数（不妨仍叫做v１）进行计算，直到两者相等，此时我们可以假定约化是良好的．假设gcd（Av，Bv，r，r－１），gcd（Av，Bv，r，r－１）中出现的单项集合为｛t１，１１２２t２，⋯，tl｝炒Z［x１，⋯，xr－２，xr］，则其可以表示为gcd（Av，Bv，r，r－１）＝a１t１＋a２t２＋⋯＋altl，１１gcd（Av，Bv，r，r－１）＝b１t１＋b２t２＋⋯＋bltl，２２其中ai，bi∈Z．通过解同余方程ci（xr－１）≡ai，modL１ci（xr－１）≡bi，modL２，i＝１，２，⋯，l．·８３·\n则可得A，B模（xr－１－v１）（xr－１－v２）的同态像的最大公因子gcd（ALL，BLL，r，r－１）＝c１（xr－１）t１＋c１（xr－１）t２＋⋯＋cl（xr－１）tl．１２１２求得gcd（ALL，BLL，r，r－１）后，再选异于v１，v２的整数v３，此时L１L２与L３＝１２１２xr－１－v３是互素的，再利用孙子定理，则可求得A，B模（xr－１－v１）（xr－１－v２）（xr－１－v３）的同态像的最大公因子gcd（ALLL，BLLL，r，r－１）．１２３１２３重复上述过程，可求得A，B模xr－１的更高次多项式L１L２⋯Ls的最大公因子，当s≥m，即多项式L１L２⋯Ls的次数高于m时，因A，B关于xr－１的次数不超过m，故其同态像与其本身相等，我们自然也就求得了A，B的最大公因子．在后面的算法３畅３畅３中，r表示主未定元的足标，它在整个计算中保持不变；s表示除主未定元之外的未定元的个数，也是我们将要赋值的未定元的足标；在开始计算时，s应取作r－１畅当s下降到０时，我们得到一个一元问题，可用３畅３畅１节的方法解决此问题，此时递归过程结束．算法中的random（）表示随机地产生一个整数，当然假定每次产生的整数都不相同；subs（xs，v，A）表示将A中的未定元xs赋予值v；在算法结束时，还需判断所得的最大公因子是否为A，B的最大公因子．若不是，还需重新计算．算法3畅3畅3多元多项式最大公因子的模方法：Procgcd（A，B，r，s）ifs＝0thenreturngcd唱simple（A，B，xr）；M：＝1＋min（deg（A，xs），deg（B，xs））；E0：dov：＝random（）；Av：＝subs（xs，v，A）；Bv：＝subs（xs，v，B）；whiledeg（Av，xr）≠deg（A，xr）anddeg（Bv，xr）≠deg（B，xr）；D：＝gcd（Av，Bv，r，s－1）；E1：Known：＝xs－v；n：＝1；Res：＝D；whilen≤Mdodov：＝random（）；Av：＝subs（xs，v，A）；Bv：＝subs（xs，v，B）；whiledeg（Av，xr）≠deg（A，xr）anddeg（Bv，xr）≠deg（B，xr）；D：＝gcd（Av，Bv，r，s－1）；ifdeg（D，xr）＜deg（Res，xr）thengotoE1；ifdeg（D，xr）＝deg（Res，xr）thenRes：＝CRT（Res，Known，D，xs－v）；Known：＝Known×（xs－v）；n：＝n＋1；ifRes｜AandRes｜BthenreturnRes；gotoE0；·８４·\n例3畅3畅3设A，B∈Z［x，y，z］的定义为５４３３３２３A（x，y，z）＝９x＋２xyz－１８９xyz＋１１７xyz＋３x２４２２２３２３－４２xyz＋２６xyz＋１８x－６３xyz２＋３９xyz＋４xyz＋６，６４３４２４B（x，y，z）＝６x－１２６xyz＋７８xyz＋xy４３２４２３２＋xz＋１３x－２１xyz－２１xyz２２２２３３＋１３xyz＋１３xyz－２１xyz２＋１３xyz＋２xy＋２xz＋２畅首先对本例而言，若取x作为主未定元，则A，B关于x的最高项系数都是常数．因此若选z作为第一个赋值未定元，则无论z在哪一点赋值，相应的线性式都不会整除最高项系数．其次要想利用模方法求A，B的最大公因子，应估计出最大公因子关于各个非主未定元的次数，这关系到我们在算法中应该使用多少次多项式形式的孙子剩余定理．因为最大公因子关于某个未定元的次数不会超过A，B关于该未定元的次数的最小者，若C＝gcd（A，B），则有degy（C）≤４，degz（C）≤３畅按照模方法的思想，关于z，应该取４个赋值点（因degz（C）≤３）zi，i＝１，⋯，４畅然后分别计算A（x，y，zi），B（x，y，zi），i＝１，⋯，４，的最大公因子Ci，i＝１，⋯，４畅最后利用孙子剩余定理求出C．这样就将问题化归为４个二元子问题．为了控制系数的膨胀，对系数我们也采用模方法．即取一系列素数pi，i＝１，⋯，用关于未定元的模方法求出A，B在Zp［x，y，z］内的最大公因子，再利用整数形式的孙i子剩余定理计算A，B在Zp⋯p［x，y，z］中的最大公因子．因为事先无法估计出A，B１i的因子的系数的界，我们不能确定应该使用多少次整数形式的孙子剩余定理，只能在每次求得A，B在Zp⋯p［x，y，z］内的最大公因子后，检验其是否整除A，B，是则停止，１i否则继续计算．按照上述思想，我们首先取p１＝１１，求A，B在Z１１［x，y，z］内的同态像的最大公因子．此时其同态像为５４３３３２３A１１（x，y，z）＝－２x＋２xyz－２xyz－４xyz＋３x２４２２２３２３＋２xyz＋４xyz－４x＋３xyz２－５xyz＋４xyz－５，６４３４２４B１１（x，y，z）＝－５x－５xyz＋xyz＋xy４３２４２３２＋xz＋２x＋xyz＋xyz２２２２３３＋２xyz＋２xyz＋xyz２＋２xyz＋２xy＋２xz＋２畅按照算法的原则，我们应将其递归为一个二元问题．为此随机地取z＝２，－５，－３，５，先考虑z＝２的情形，有５４３３３A１１（x，y，２）＝－２x＋４xy－４xy＋５xy３２４２２２＋３x－３xy－xy－４x·８５·