《数论教案》word版.doc

数论教案第一章 整数的可除性整除整除是数论中的基本概念，在这一部分中，我们从这个概念出发，引进带余数除法及辗转相除法，然后利用这两个工具，建立最大公因数与最小公倍数的理论，进一步证明极具重要性的算术基本定理。最后介绍两个重要的函数与,并用来说明如何把!表成质数幂的乘积。整除的定义设，是任意两个整数，其中，如果存在一个整数使得等式 =(1)成立，我们就称为整除或被整除,记做|，此时我们把叫做的因数，把叫做的倍数，如果（1）里的整数不存在，就说不能整除或不被整除，记做。例如6，3时，有q2使，故3|6；又如4，3时，不存在整数使bq，故34。整除的性质定理1若是的倍数，是的倍数，则是的倍数。即：|，| |。证：由|，|及整除的定义知存在整数 使得 。因此，但是一个整数，故|。定理2若，都是的倍数，则 也是的倍数。证，都是的倍数的意义就是存在两个整数 ，使得所以 ，但 为整数，故 是的倍数。用类似方法可以证明下面的定理3，请同学们自己给出证明。定理3若 都是的倍数， 是任意个整数，则是的倍数。例证明3|(+1)(2+1)，其中是任何整数。证因为(+1)(2+1)= (+1)(+2)+(-1)=(+1)(+2)+(-1)(+1)，而三个连续整数的积可被3整除，于是 3|(+1)(+2)，3|(-1)(+1) 。所以3|(+1)(2+1)。第一章 整数的可除性 带余数除法 任给两个整数，它们之间不一定有整除关系，一般有下面的带余数除法。定理若，是两个整数，其中0，则存在两个整数及，使得（2）成立，而且及是唯一的。证作整数序列，3，2，0，2，3，则必在上述序列的某两项之间，即存在一个整数使得 成立。令，则为整数，且，而 。设 是满足（2）的另两个整数，则， 所以 ，于是 ，故 。由于 都是小于的正整数或零，故 。如果 ，则 ，这是一个矛盾。因此 ，从而 。整数的很多性质都可以从这一定理引导出来，我们这一章的最主要部分就是建立在这一定理的基础上的。定义（2）中的叫做被除所得的不完全商，叫做被除所得到的余数。例设15，则当255时170，17，015；而当417时，2712，27，1215；当81时，69，6，90，实际上只需0即可，即有下面的 推论若，是两个整数，其中 ，则存在两个整数及使得， 成立，而且及是唯一的。第一章 整数的可除性最大公因数利用前面的带余数除法，我们可以着手研究整数的最大公因数及实际求法，处理整个问题的方法就是用所谓的辗转相除法。最大公因数的定义设 是(2)个整数，若整数是它们之中每一个的因数，那么就叫做 的一个公因数。整数 的公因数中最大的一个叫做最大公因数，记作 。若 ，就称 互质，若 中每两个互质，我们就说它们两两互质。注若整数 两两互质，则 ，但反过来却不一定成立，比如(6，10，15)1，但（6，10）1，（6，15）1，（10，15）1。又由定义知，当 不全为零时， 是存在的。为了能方便地计算最大公因数，下面我们先讨论一下最大公因数的性质，通过这些性质，就可找到计算最大公因数的方法。最大公因数的性质定理1若是任意个不全为零的整数，则（1） 与的公因数相同；（2）证我们只证明（1），（2）可由（1）及最大公因数的定义得出，设是的任一公因数，则 ，于是 ，又 或，故，所以也是的公因数。反之，设是的任一公因数，则，。因或，故或，当时，由及整除性质可得，。所以也是的公因数。利用定理1，可将负数的最大公因数转化为正数的情况。下面先讨论两个整数的最大公因数的计算方法，然后再推广到个的情况。定理2若是任一正整数，则（0，）。证因|0，|，所以是0和的公因数，设 是0和的任一公因数，则|，所以=，故。从而。由定义知（0，）。定理3设，是任意三个不全为零的整数，且，其中是整数，则，与，有相同的公因数，从而（，）（，）。证设 是，的任一公因数，则|，|，由于，于是由整除的性质知|，从而为，的一个公因数。同理可证，的任一公因数也是，的一个公因数。故，与，有相同的公因数。再由最大公因数的定义知后一结论成立。最大公因数的计算由定理3及带余数除法，可得出两个数的最大公因数的计算方法如下：设，为两个整数。（1）0，0时，规定（，）0；（2），之一为零时，不妨设0，0，则（，）。（3），均不为零时，由定理1，可设0，0。由带余数除法可得下面一系列等式， ，。因为每进行一次带余数除法，余数至少减一，而是有限的，所以上面这一系列等式只有有限个，即到第1步时必有0出现。由定理3有：，但。故（，b）例1：设1859，1573，求（，）。解：由定理1，（1859，1573）（1859，1573）。由（3）作一系列带余数除法：所以。注上面这种计算两个整数的最大公因数的方法叫辗转相除法。例2：设169，121，求（，）。解：作辗转相除法：所以（169，121）1。由最大公因数的性质及计算方法可得定理4，的公因数与（，）的因数相同。证设d 是，的任一公因数，则，。由（3）知，从而，一直下去有 ，即为（，）的因数。同理，当 为（，）的因数时，可得为，的公因数。利用定理4，可将两个整数的最大公因数的计算方法推广到计算个整数的最大公因数。定理5设是个正整数，令（*）则。证由（*）式，但，故，由此类推，最后得到，即是的一个公因数。又设是的任一公因数，则，由定理4，同理，由此类推，最后得到。因而。故是的最大公因数。第一章 整数的可除性整除的进一步性质在最大公因数的计算方法（3）中，我们已看到带余数除法的重要性，在这一部分中，我们来讨论与，的关系，由此可得到关于整除的进一步性质。设，是任意两个正整数，由带余数除法有：， （1），。由上面这一系列等式可得定理1若，是任意两个正整数，则，k1，2，n （2）其中，2， （3） 证当1时，（2）显然成立，当2时，由（1）得但 ，故 。假设（2），（3）对于不超过的正整数都成立，则故 ，其中，。由归纳法，定理1的结论成立。由于，于是由定理1立即可得到下面的结论。推论1.1若，是任意两个不全为零的整数，则存在两个整数， 使得(4)证在（2）中取，得 。 两边乘以 ，得 。于是取 ， ，则 。定理2若，是三个整数，且（，）1，则（i），与，有相同的公因数。（ii）（，）（，）。其中，至少一个不为零。证由最大公因数的定义，我们只须证明（i）由已知条件及推论1.1，存在两个整数， 满足等式 两边乘以，得设是，的任一公因数，则 ， 于是由上式得 ，从而 为，的一个公因数。反之，的任一公因数显然是，的一个公因数。故（i）成立。由定理2及整除的基本性质可得推论2.1若，则。证因，故。但由定理2有（，）（，），所以（，）。于是，从而。推论2.2设及是任意两组整数。若前一组中任一整数与后一组中任一整数互质。则与互质。证由定理2可得1，j1，2，。再用定理2，（）1。有关整除的性质我们就讨论到此，这些性质都非常重要，大家在学习中要逐一理解并掌握。第一章 整数的可除性最小公倍数前面学了最大公因数，与此对应，在这一部分中，我们再讨论最小公倍数。我们将把最小公倍数和最大公因数联系在一起，并由最大公因数的计算推出最小公倍数的计算。最小公倍数的定义设是(2)个整数。若是这个数的倍数，则 就叫作这个数的一个公倍数。又在的一切公倍数中的最小正数叫做最小公倍数，记为。由于任何正数均不是0的倍数，故我们在讨论最小公倍数时总是假定均不为零。最小公倍数的性质为得到最小公倍数的计算方法，我们先讨论一下最小公倍数的性质。下面的定理1可将负数化为正数讨论，定理2讨论了两个正整数的情形，最后定理3讨论一般情况，即个正整数(2)的情形。定理1。该定理的证明类似于最大公因数中相应性质的证明，请大家作为练习自己给出证明。定理2设，是任意两个正数，则（i），的所有公倍数就是，的所有倍数。（ii），特别地，若（，）1，则，。证设是，的任一公倍数，由定义可得 。令，由上式即得。但，由整除的性质得。因此， （1）其中t 满足。反过来，当为任一整数时，为，的一个公倍数，故（1）恰好表示，的一切公倍数，当1时即得到最小公倍数，故（2）结论（ii）成立。将（2）代入（1），结论（i）也成立。定理3设是个正整数，令（3）则。证由（3），1，且，故 是的一个公倍数。又设是的任一公倍数，则，故由定理2（i），又，同样由定理2（i）得，依此类推，最后得，因此。故。最小公倍数的计算由定理2和定理3，我们重点掌握两个正整数的最小公倍数的计算。由定理2，只须计算出最大公因数，则由定理2（ii）即可求出最小公倍数。例设169，121，求，。解 由最大公因数的计算易求得（，）1。故第一章 整数的可除性质数在正整数里，1的正因数只有1本身，因此在整数中间1占有特殊的地位。任何一个大于1的整数，都至少有两个正因数，即1和它本身。为更好地讨论这些数的性质，我们把这些数进行分类。质数的定义一个大于1的整数，如果它的正因数只有1和它本身，就叫作质数（或素数）；否则就叫作合数。例如2，3，5，7等为质数，而4，6，8，10等为合数。质数的性质定理1设是任一大于1的整数，则的除1以外的最小正因数是一个质数，并且当为合数时，。证假定不是质数，由定义，除1及本身外还有一正因数，因而1 。但，所以，这与是的除1以外的最小正因数矛盾。故一定是一个质数。当为合数时，则，且，否则是质数。由的最小性知，从而，故。定理2 若是一质数，是任一整数，则能被整除或者与互质。证因为，由质数的定义，（，）1，或者（，）。即（，）1，或者。推论2.1设是个整数，是质数。若，则一定能整除某一个。证假设均不能被整除，则由定理2，（）1，。于是由整除的进一步性质中的推论2.2，这与矛盾。于是推论2.1成立。算术基本定理任一大于1的整数能表成质数的乘积，即任一大于1的整数（1）其中质数，并且若其中是质数，则，。 证我们先用数学归纳法证明（1）式成立。当2时，因2为质数，取1，（1）式成立。假设对一切小于的正整数，（1）式都成立，此时若为质数，则取1， 这时（）式对成立；若为合数，则有两正整数，满足条件：，1，1。由定理1，有一质因数，这里，否则，得，矛盾。故是上面个质数以外的质数。定理获证。第一章 整数的可除性 函数与在这一部分中，我们先介绍在数论里面常常用到的两个函数与，再讨论这两个函数的性质，最后利用这些性质实际求出的标准分解式。函数与的定义函数与是对于一切实数都有定义的函数，函数的值等于不大于的最大整数；函数的值是。我们常常把叫做的整数部分，叫的小数部分。例，；，。函数与的性质由这两个函数的定义立即可得出下列简单性质：.。.，。.，是整数。.,。. . 若，是两个整数，则. 若，是任意两个正整数，则不大于而为的倍数的正整数的个数是证前几条性质都比较简单，我们在这里只证明最后一条。时是显然的，下面设，设是任一不大于而为的倍数的正整数，则 （）故满足以上条件的的个数等于满足（1）的的个数，因而等于。函数与的应用用与的性质，我们可以求出的标准分解式。定理在的标准分解式中质因数的指数 （）注由于对给定的及，总存在正整数使，于是，故（2）式中的和是有限和。证设想把2，都分解成标准分解式，则由算术基本定理，就是这1个数的分解式中的指数之和，设其中的指数是的有个（1），则,其中恰好是2，这1个数中能被除尽的个数，但由性质，故推论1，其中表示展布在不超过的一切质数上的积式。推论2贾宪数是整数（0kn）。证由性质及，有，所以。故由推论1即得。推论3若（）是次整系数多项式，是它的阶导数（），则是次整系数多项式。该推论的证明只须用到导数的计算及推论，请大家作为练习自己给出证明。第二章 不定方程二元一次不定方程 中国古代数学家张丘建在张丘建算经中解答了下面的题目：“鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一。百钱买百鸡，问鸡翁母雏各几何？”设，分别代表鸡翁、鸡母、鸡雏的数目，就可得到下面的方程组消去，再化简，即得 （*）像（*）这种含有未知数的个数大于1的方程就是不定方程。在数论中我们主要讨论（*）这种不定方程的整数解。因由高等代数的知识我们知道在实数或复数范围内（*）总是有解的 ，但一个整系数不定方程不一定有整数解，比如 就无整数解。二元一次不定方程的一般形式本部分讨论二元一次不定方程，其一般形式为： （）其中，是整数，不为零，为未知量。对二元一次不定方程（1），我们主要讨论它有整数解的判别条件，以及在它有整数解时，如何求出它的全部整数解。二元一次不定方程有整数解的判别定理1二元一次不定方程（1）有整数解的充要条件是。证若（1）有整数解，设为 ，则但 ， ，因而，必要性得证。反之，若，则，为整数。由最大公因式的性质，存在两个整数， 满足下列等式于是。令，则，故为（1）的整数解，从而（1）有整数解二元一次不定方程的解法定理2设二元一次不定方程（1）有整数解，是其中一个整数解，又设，则（1）的一切整数解可表成 （）其中。证因是（1）的解，故有，因此 ，这说明（2）是（1）的整数解。设是（1）的任一整数解，则，从此式减去得将，代入上式，移项并消去（注意)，得到又，故。由整除的性质知，所以存在整数 使，亦即。将代入即得 。故可表成（2）的形状。由上面两方面的证明知（2）表示（1）的一切整数解。给定二元一次不定方程（1），可先由定理（1）判别其是否有整数解，在有整数解时，由定理2，要先求出其一特殊解，再用公式（2）即可写出其一切整数解的表达式，即所谓通解。下面重点讨论(1)的特解（即一个固定解）的求法。由定理1的证明知，只须求出整数， 使，则即为（1）的一个解。为求， 我们先用最大公因数的计算方法辗转相除法，求出各个商，最后一个商不要，按下表排列，并按所给式子计算出 。其中。则。最后根据及，的大小选择， 的绝对值及符号即可。例1求， 使。解先写出辗转相除法的过程如下：不要，将，排成下表计算经计算（或观察）取，即得例2求的一切整数解。解因为，所以有整数解。先求， 使。作辗转相除法： 所以取，得。从而。故一个特解为：。一切整数解为：。注在例2中为求， 使，由于此式较简单，也可直接观察得出。第二章 不定方程多元一次不定方程在本小节内，我们将二元一次不定方程的解法推广到 元一次不定方程。多元一次不定方程的一般形式多元一次不定方程的一般形式是，（）其中为整数，均不为零、多元一次不定方程有整数解的判别定理1多元一次不定方程（1）有整数解的充分必要条件是证设。（i）若（1）有整数解，设为其一个整数解，则由整除的性质知，故。（ii）若，我们用数学归纳法来证明（1）有整数解。当时，由二元一次不定方程有解的判别知（1）有整数解。设上述条件对 1 元一次不定方程是充分的。令，则，因，由归纳假设知方程有整数解，设为其一整数解。再考虑由二元一次不定方程有整数解的判别及，知它有整数解，设为其一整数解。则故是（1）的一个整数解。定理证毕。多元一次不定方程的解法定理1不仅提供了多元一次不定方程有整数解的判别法，同时由证明过程也给出了具体求解的方法。 先计算。由定理1，若，则（1）无整数解；若，则（1）有整数解。作以下二元一次不定方程（）利用解二元一次不定方程的解法，从（2）的最后一个方程开始，依次求出（2）中各二元一次不定方程的整数解的表达式，就可得出（1）的整数解的表达式。例求的一切整数解。解，故方程有整数解。考虑方程与。先解得再解，即得故原方程的一切整数解为第二章 不定方程勾股数在这一节我们讨论一种特殊的二次不定方程（1）该不定方程肯定有整数解。如就是（1）的一个整数解。显然 或是（1）的解，故我们只须讨论（1）的一切非零整数解，又当, 满足（1）时，也满足（1），所以我们重点讨论（1）的一切正整数解。下面假定。若（1）有正整数解，且，则，从而，故这时可在（1）的两边约去，所以我们再假定若（1）有正整数解，则，中一定是一单一双。因为由知，不能同时为偶数。又如果，同时为奇数，则，从而，但或，故，于是，必一单一双，我们设是双数，即。下面先证一个引理。引理不定方程(2)的一切整数解可以表达成：(3)证设是（2）的任一解。令，其中不能再被任何数的平方整除。则，因此。又，故，所以，设，代入（2）即得。若，则有一质数 满足，但由的定义及知。所以，但均为正整数，故。因此反之，（3）式中的显然满足（2）式。定理不定方程（1）的适合条件（）的一切正整数解可以表成：（）证（i）先证（5）是（1）的适合条件（4）的正整数解。显然，且，。设，则。因此。但，故或。又因为单数，|，得 。（ii）设，是（1）的适合条件（4）的任一组正整数解。则，(，)=1，因此，均为单数。而其中为互质的正整数，因为若，则，因而，故 。由引理有正整数， 存在且使下式成立：，即。由，即知，又由为单质数可知， 之中一单一双。费尔马问题介绍在这一部分我们介绍一个与不定方程有关的问题，著名的费尔马最后定理（Fermatslast theorem），在中国较普遍地的叫做费尔马大定理。费尔马（16011665），出身于法国南部一个富裕的中产阶级家庭，学过法律，1631年前曾在波尔多做法官，1631年5月，费尔马成为图鲁兹地方高等立法议会议员，并移居图鲁兹。费尔马的数学研究是业余的。他对数论、几何、分析和概率等学科都做过深入的研究，并做出了重大的贡献。所谓费尔马大定理，就是在1637年费尔马提出的下面的猜测：当时，没有正整数解。全世界很多著名数学家为这个问题绞了很多脑汁，到1983年，由于莫德尔猜想的证明，数学家看出有一系列猜想最终可导出费尔马定理的证明。发展到1986年，数学家已经看到了，要证明费尔马大定理，只须证明对半稳定椭圆曲线，谷山志村猜想成立就可以了，英国数学家安德鲁维尔斯（Andrew Wiles）知道这个消息后，面壁7年，终于在1993年6月取得了突破，但还有一些漏洞。直到1994年10月25日，美国俄亥俄州立大学的卢宾（Karl Rubin）教授用电子邮件向全世界宣布，A.维尔斯完成了对费尔马大定理的证明。1995年5月，数学年刊用一整期发表了维尔斯的论文。1996年3月，维尔斯获得了沃尔夫奖，这更加肯定了他的功绩。至此，一个困扰人类三百年的著名问题被完全解决了，费尔马大定理最终成为一个真正的定理。维尔斯和他同事们的工作又一次地证明了人类智慧的伟大。第三章 同余同余的概念在日常生活中，我们所要注意的常常不是某些整数，而是这些数用某一个固定的数去除所得的余数。例如我们问现在是几点钟，就是用24去除某一个总的时数所得的余数，又如问今天是星期几，就是问用去除某一个总的天数所得的余数，于是就在数学中产生了同余的概念。在本部分中我们先介绍同余的概念及基本性质。同余的定义给定一个正整数，把它叫做模。如果用去除任意两个整数与 所得的余数相同，我们就说与对模同余，记为（）。如果余数不同，我们就说与对模不同余，记为（）。例如，=6，则713（6），810（6）。这是因为7和13除以6的余数均为1，而8和10除以6的余数分别为2和4。同余的基本性质利用同余的定义，我们可以得到同余的若干基本性质。性质1为正整数，为任意整数，则（）；若（），则 （）； 若（），（），则（）。由定义知性质是显然的，请读者自己给出证明。性质整数，对模同余的充要条件是，即+ ，是整数。证设 。若（），则，因此，即。反之，若，则，因此，但，故，即（）。注在很多问题中，我们常用性质来判断、是否对模 同余，有时用性质比用定义要方便些。性质 若，则若=（），则（）。证由性质有，因，故，获证。由有，这就是的结论性质若，则。证明由性质，所以。故。将性质、性质结合起来一般有性质若，则。特别地，若，则。性质6若，则。证由性质，但，又（，），故，即。性质若（），则（）。若（），是，及的任一公因数，则。利用性质即可证明性质，请大家作为练习自己给出证明。性质若， 则。证由性质，则由最小公倍数的性质有，故由性质即得。性质若（），则（）。证由性质，又，由整除的性质知，故（）性质10若（），则（，）（，），因而若 能整除及，二数之一，则能整除，中的另一个。证由性质，由最大公因数的性质得（，）（，）。以上的每一条性质都很简单，但是都非常重要，今后会经常使用，请大家认真学好每一条性质。同余的简单应用A一个整数能被（或）整除的充要条件是它的十进位数码的和能被（或）整除。证可只对正整数 证明，将 写成十进位数的形式：因101（），故由性质得，再由性质10即知 当且仅当。同理可证 当且仅当设正整数，其中。则（或11，或13）整除 的充要条件是（或11，或13）整除 。 证因为。故。所以（或11，或13）当且仅当7（或11，或13）整除。计算高次幂的个位数。例求的十进位表示中的个位数字。解本题实质上就是求10除的余数，即求中的，。因为，所以，因此，所以，即的个位数是9。剩余类及完全剩余系有了同余的概念，对于一个给定的模，我们就可以把对模 同余的所有数放在一起，即把除以 后有相同余数的数放在一起，这就产生了剩余类的概念。剩余类及完全剩余系的定义在给出定义之前，我们先证明一个重要结果。定理1设 是一个给定的正整数，则全部整数可以分成 个集合，记作，其中是由一切形如的整数所组成的，这些集合具有下列性质：（i） 每一整数必包含在而且仅包含在上述的一个集合里面；（ii） 两个整数同在一个集合的充要条件是这两个整数对模 同余。证明（i）设 是任一整数，由带余数除法得。故 在内。又由带余数除法知， 由 唯一确定，故 只能在内。（ii）设，是两个整数，并且都在内，则。故（），反之若（），则由同余的定义知， 同在某个一个内。定义我们把定理中的叫做模的剩余类。若是个整数，并且其中任何两个都不在同一个剩余类里，则称为模的一个完全余剩余系。由定理和上面的定义，可得推论个整数作成模的一个完全剩余系的充分必要条件是这个数两两对模不同余。例：设为正整数，则；都是模的完全剩余系。完全剩余系的性质定理设是正整数，（，），是任一整数，若通过模的一个完全剩余系，则也通过模的一个完全剩余系，也就是说，若是模的一个完全剩余系，则也就是模的一个完全剩余系。证由推论，只须证明个整数两两对模不同余就够了。假设。则由同余的性质得，又由同余性质及（，）得，这与是模的一个完全剩余系矛盾，定理获证。定理若是两个互质的正整数，而分别通过模的完全剩余系，则通过模的一个完全剩余系。证由假设分别通过个整数，因此通过个整数，由推论，只须证明这个整数两两对模不同余即可。假定（）其中是所通过的完全剩余系中的整数，而是所通过的完全剩余系中的整数，由同余的性质得又由同余的性质及 即得，。由推论得。这表明如果与不全相同时，（）式即不成立，因此定理获证。在本部分最后，我们给出几个今后要用到的特殊名词。定义 这个整数叫模的最小非负完全剩余系；当为偶数时，或叫模的绝对最小完全剩余系；当为奇数时，叫模的绝对最小完全剩余系。简化剩余系与欧拉函数在上一节里我们讨论了完全剩余系的基本性质，这一节我们要进一步讨论完全剩余系中与模互质的整数，这需要引进简化剩余系的概念。在讨论简化剩余系的过程中，需要用到数论上一个很重要的函数欧拉（Euler）函数。欧拉函数的定义欧拉函数是定义在正整数上的函数，它在正整数上的值等于序列0,1,2,1中与互质的数的个数。例如。简化剩余系如果模的一个剩余类里面的数与互质，就把它叫做一个与模互质的剩余类。在与模互质的全部剩余类中，从每一类中各任取一数所作成的数组，叫做模的一个简化剩余系。定理模的一个剩余类与模互质的充要条件是此类中有一数与互质。因此与模互质的剩余类的个数是，的每一简化剩余系是由与互质的个两两对模不同余的整数组成的。证设是模的全部剩余类。若是一个与模互质的剩余类，则（，）。反之若有，则由剩余类的定义及同余的性质知中的每个整数都与互质，因而是与模互质的剩余类。由于为与模互质的剩余类当且仅当（，），因此由欧拉函数的定义及模的简化剩余系的定义即得定理结论成立。定理若是个与互质的整数，并且两两对模不同余，则是模的一个简化剩余系。证由定理及简化剩余系的定义知结论成立。定理若（，）， 通过模的简化剩余系，则通过模的简化剩余系。证通过个整数，由于（，），（，），故（，）。若，则由同余的性质有，这与原假设矛盾。故由定理知，定理成立。定理若是两个互质的正整数，分别通过模的简化剩余系，则通过模的简化剩余系。 证由定理知，简化剩余系是一个完全剩余系中一切与模互质的整数作成的。因此只须证明：若分别通过模的一个简化剩余系时，则通过模的一个完全剩余系中一切与模互质的整数。由完全剩余系的性质知，若分别通过模的完全剩余系时，则通过模的一个完全剩余系。又若，则由即得，于是，故。反之，若，则。所以又，所以。定理证毕。推论若是两个互质的正整数，则。证由定理立即可得。欧拉函数值的计算利用上面的推论及标准分解式我们可以得出欧拉函数值的计算方法，这可由下面的定理给出。定理设为 的标准分解式，则。证（i）由推论得。（ii）下证。由定义知等于从减去中与不互质的数的个数由于为质数，故等于从中减去中被 整除的数的个数。由函数的性质知中被 整除的数的个数是，故。（iii）由（i），（ii）即得。欧拉定理费尔马定理在这一节我们应用简化剩余系的性质证明数论中两个著名的定理，并说明它们在研究循环小数时的用处。欧拉定理设是大于的整数，（，），则。 证设是模的简化剩余系，则由简化剩余系的性质知也是模的一个简化剩余系。故，即，但，因此，由同余性质得。费尔马定理若是素数，则。证若（，），则由欧拉定理得。由欧拉函数值的计算公式有 。所以，故。若（，），则，从而，所以。对循环小数的应用欧拉定理及费尔马定理在数论里是很有用的，下面我们介绍它们在研究分数与小数互化时的用处，由于任何一个有理数都可以写成分数的形式，即。由带余数除法知：，即，因此我们只讨论与间的分数与小数互化的问题。定义设是一个不大于的非负整数（1,2,3），如果在中任取一个，一定存在一个大于的正整数，使得，则称为一个无限小数，否则，叫做有限小数。如1/22=0.3181818，5/7=0.714285714285为无限小数，而1/5=0.2，1/2=0.5为有限小数。定理设，（，），则可化为有限小数的充要条件是，(，但不同时为零），并且当时，令，则可化为 位有限小数。证必要性：设，两边乘以得。因（，），故，于是。若，则，这是不可能的。所以。充分性：设，可设，于是，但。所以可令，显然，否则有 与（，）矛盾。故化为位小数；同理在时，可化为位小数，于是当时，可化为为小数，当然可化为有限小数。例如：1/2=0.5，1/4=0.25，1/10=0.1，1/20=0.05。定义如果对于无限小数能找到两个整数，使得我们就称它为循环小数，并记为。若存在的是满足条件的中最小的，就称为循环节，称为循环节的长度，若最小的，就称该循环小数为纯循环小数，否则叫混循环小数。定理设，（，），则能表成纯循环小数的充要条件是（，10）。证设，两边乘以 得：。其中。所以，即。因为（，），故，所以（，10）。反之，若（，10），则由欧拉定理知有一正整数使得。即。进一步有，故存在整数使得，即，并且，当然还有。所以 ，令，因，故不全为零，也不全为，于是，故。注当（，10）时，若是使的最小正整数，则可表成循环节长为的纯循环小数。例如。类似于定理可证明下面的定理定理设0，（，），不全为零，则可表成混循环小数，其中不循环的位数，而循环节的长是使的最小正整数，反之亦成立。注由定理，定理，定理知，与之间的有理数要么为有限小数，要么为循环小数，由此可知无限不循环小数为无理数。第四章 同余式基本概念在代数里面，一个主要的问题就是解代数方程。在本章所要讨论的同余式正是与解代数方程相类似的问题。先介绍一些基本概念。模的同余式用f(x)表示多项式，其中 是整数，设是一个正整数，则()（）（）叫做模的同余式。若（），则 叫做（）的次数。如 是次同余式。同余式的解由同余的性质知，若整数能使()（），则剩余类中任何整数 都能使 。于是有下面的定义定义若整数是使()（）的，则称（）为（）的一个解。由定义知，同余式（）的一个解指的是模的一个剩余类，而非一个整数。例如（）是 的一个解，（）也是的一个解，即有两个解，但实际上适合 的一切整数是形如3及3的整数， 。下面我们先从简单同余式开始讨论。一次同余式的一般形式一次同余式的一般形式为：（），（）（）一次同余式有解的判定及解法定理一次同余式（）有解的充要条件是（，），且在（）有解时，（）的解数（对模来说）是（，）。证首先由同余的性质知（）有解的充要条件是不定方程有解，由不定方程有解的判别知，（）有解的充要条件即为（，）。设（，），若（）有解，则适合（）的一切整数可以表成。此式对模来说可写成 。但两两对模不同余，故（）有个解：。由定理的证明可知，要解一次同余式（），只需解不定方程，求出该不定方程解中的表达式，即可得到适合（）的一切整数，再将这些整数分写成模的（，）个同余式即可。例解一次同余式3（12）。解：因为（3，12）3，36，所以同余式有解，且有个解。由3126得：42，0，1，2。所以个解为：，10（12）。第四章 同余式孙子定理同余式组在本节我们讨论下面的同余式组的解法 （）我们重点讨论两两互质的情况，一般情况大家可参考教材后面习题中第题提供的解法思路。（）的解法通常由下面的叫孙子定理的定理给出。孙子定理设是个两两互质的正整数， ，则同余式组（）的解是 （）其中是满足的一个整数，。证由，即可得到，故由一次同余式的解的判别知，对每个，存在使得。另一方面，因此，故，所以为（）的解。若是适合（）式的任意两个整数，则。因，于是，故（）的解只有（）。孙子定理提供了（）式的一个解法，在解题过程中，先计算出，再求出适合的一个整数，最后按（）式计算出解答即可。例解同余式组解因，两两互质，故可由孙子定理给出解答，105，。由，即得，所以。由，即得，所以。由，即得，所以。故由孙子定理，所给同余式的解为：2352+1213+1152（mod105）即23（mod105）。在本节最后，我们再证明一个关于完全剩余系的性质。定理若分别过模的完全剩余系，则（）过模的完全剩余系，其中两两互质。证明令，则过个数，这个数是两两对模不同余的。这是因为若，则，即。但是模的同一完全剩余系中的二数，故，由完全剩余系的判别知定理结论成立。第四章 同余式高次同余式在本节我们初步讨论一下高次同余式的解数及解法。一般情况，对于一个给定的高次同余式要判别其是否有解，以及有多少个解是比较困难的。高次同余式的一般形式设，其中为整数，是一个