数论教案第一章 整数的可除性整除整除是数论中的基本概念，在这一部分中，我们从这个概念出发，引进带余数除法及辗转相除法，然后利用这两个工具，建立最大公因数与最小公倍数的理论，进一步证明极具重要性的算术基本定理。最后介绍两个重要的函数与,并用来说明如何把!表成质数幂的乘积。整除的定义设，是任意两个整数，其中，如果存在一个整数使得等式 =(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，只须计算