整数的可除性

1、第一章整数的可除性整 除整除是数论中的基本概念，在这一部分中，我们从这个概念出发，引进带余数除法及辗 转相除法，然后利用这两个工具，建立最大公因数与最小公倍数的理论，进一步证明极具重 要性的算术基本定理。最后介绍两个重要的函数 与 ,并用 来说明如何把-；!表成质数幕的乘积。整除的定义设,;是任意两个整数，其中-工0,如果存在一个整数 /使得等式一 W成立，我们就称为/整除或“被：整除，记做：，此时我们把J叫做的因数，把“叫做：的倍数，如果（1）里的整数/不存在，就说一：不能整除丿或不被一：整除，记做例如=6，一： = 3时，有q= 2使=一：，故3|6;又如=4, ： = 3时，不存在整数：

2、 使卜、=bq,故3 4。整除的性质定理1若是丨的倍数，；是1的倍数，则是的倍数。即：卄 r I- u。证：由：卜，一及整除的定义知存在整数 如h 使得-。因此一 m 一“一，但匕1是一个整数，故c匚。定理2若，丨都是匸的倍数，贝则.也是匸的倍数。证 ，；都是匸的倍数的意义就是存在两个整数如h ，使得/ - -j所以 ，但:.'i - 为整数，故 aib 是*的倍数。用类似方法可以证明下面的定理3,请同学们自己给出证明。定理3若""=都是：'的倍数，如加X £ 是任意个整数，则i- v是匸的倍数。例 证明3|、G +1）（2 L +1），其中、是任

3、何整数。证因为“（：+1）（2 卜 +1）=卜（：+1）仁 +2）+（卜-1）= 1 C- +1）C- +2）+C. -1）1 （ ； +1）,而三个连续整数的积可被3整除，于是 3|； （ ； +1）（.+2）, 3|（.-1）.（：+1）所以 3p. C： +1）（2 ' +1）。第一章整数的可除性带余数除法任给两个整数，它们之间不一定有整除关系，一般有下面的带余数除法。定理 若“，：是两个整数，其中:>0，则存在两个整数：及“，使得一；-注'匚._ L'（ 2）成立，而且：及，是唯一的。证作整数序列，-3 一： , - 2 一：，- 一：，0，:, 2 -

4、, 3：,则必在上述序列的某两项之间，即存在一个整数/使得1-： -】 < '-成立。令一f='，则：'为整数，且=：】+ '，而 0<r<b 。设"':是满足（2）的另两个整数，则厂妬+片,01 <4所以吐一仍，于是。加，故一。由于：i 都是小于0的正整数或零，故卜一尸宀。如果01"，则 咖詡2“，这是一个矛 盾。因此 牯q ，从而】。整数的很多性质都可以从这一定理引导出来，我们这一章的最主要部分就是建立在这一 定理的基础上的。定义 （2）中的:叫做“被-：除所得的不完全商，J叫做被：除所得到的余数。例设=1

5、5,则当=255时丿=17： + 0, < = 17 , = 0<15;而当-=417 时，-=27：. + 12, ： = 27, = 12<15;当- = 81 时，卜、=一 6+ 9, ： =一 6, " = 9<15。注 在定理中我们要求；>0，实际上只需；工0即可，即有下面的推论 若“,:是两个整数，其中1 “ ，则存在两个整数：及，使得成立，而且：及”是唯一的。第一章整数的可除性最大公因数利用前面的带余数除法，我们可以着手研究整数的最大公因数及实际求法，处理整个问题的方法就是用所谓的辗转相除法。最大公因数的定义设：，：，是、C- >2个

6、整数，若整数是它们之中每一个的因数，那么丿就叫做彳的一个公因数。整数T 1"、的公因数中最大的一个叫做最大公因数，记作-:一。若，就称'互质，若'中每两个互质，我们就说它们两两互质。注 若整数 1、两两互质，则-'-j，但反过来却不一定成立，比如(6, 10, 15) = 1,但(6, 10)工1 (6, 15)工1, (10, 15)工1又由定义 知，当：，：，不全为零时，-；-是存在的。为了能方便地计算最大公因数，下面我们先讨论一下最大公因数的性质，通过这些性 质，就可找到计算最大公因数的方法。最大公因数的性质定理1若11"、是任意 '个

7、不全为零的整数，则（1） “卩坷rr仏与|砧曲兔的公因数相同；（2）（如时r知）=佃|时，血证 我们只证明（1）,（2）可由（1）及最大公因数的定义得出，设 d是 弘円叫的任一公因数，则，|吗，j=l, 2，於，于是"丨一內，又坷二坷 或®,故叭忆，尸1, 2, s月，所以d也是如说臥的公因数。反之, 设人是。冷如，的任一公因数，则川Pi , j = l, 2，黴。因坷-吗或円，故川坷或坷，当吗二角时，由引飞及整除性质可得方I叫,', '。所以：也是1"、的公因数。利用定理1，可将负数的最大公因数转化为正数的情况。下面先讨论两个整数的最大公 因数的

8、计算方法，然后再推广到' 个的情况。定理2 若：是任一正整数，则（0,：）=。证 因：|0, 一： I：,所以：是0和：的公因数，设是0和：的任一公因数，则讣，所以 b = dq，故同° 。从而.乙。由定义知（0，）=：。定理3设，c是任意三个不全为零的整数，且-I = '-+ c，其中：是整数，则“， ”， :有相同的公因数，从而（，一：）= （ 一：，C ）。证 设一：是丿，的任一公因数，则 J u，一： I】，由于=；-;:，于是由整除的 性质知一：I】，从而；为丨，C的一个公因数。同理可证，C的任一公因数也是，丨的一个公因数。故“，：与一：，C有相同的公因数。

9、再由最大公因数的定义知后一结论成立。最大公因数的计算由定理3及带余数除法，可得出两个数的最大公因数的计算方法如下：设-，一：为两 个整数。（1）位=0, ： = 0 时，规定（位，1 ）= 0;（2）a, 0之一为零时，不妨设a = o, b刊卩（必，6）=卩I。（3）一；，:均不为零时，由定理 1，可设“ >0, ； >0。由带余数除法可得下面一系列等式a =切+巾 0（ d匚疔心也+心°心也,因为每进行一次带余数除法，余数至少减一，而 :.是有限的，所以上面这一系列等式只T有有限个，即到第+ 1步时必有：|1 = 0出现。由定理3有：-:广.J： - U，但 _。故（

10、，b）例 1:设“ =-1859，' = 1573，求（，：）。解：由定理1，（- 1859，1573） = （ 1859，1573）。由（3）作一系列带余数除法: 所以：一。注 上面这种计算两个整数的最大公因数的方法叫辗转相除法。例 2 :设-. = 169， - = 121，求（暑，-）。解：作辗转相除法:所以（169，121）= 1。由最大公因数的性质及计算方法可得证设d是a, b的任一公因数，则2 ,邙。由（3）知d h，从而 d|D,- 直下去有，即丿为（“，）的因数。同理，当：为（，）的因数时，可得 为，一:的公因数。利用定理4，可将两个整数的最大公因数的计算方法推广到计算

11、' 个整数的最大公因数。仏.% a定理5设一 I ，是1个正整数，令伽岛”（如如询卫a.） =（*）证 由（* ）式，八】！，八 4. 1，但八】1 i 1，-！-，故；1，八 "-J _， 由此类推，最后得到血|和心血血临,即血是血fljrr的一个公因数。又设d是即如r心的任一公因数，则did, d|旳,由定理4,山厶,同理 也， 由此类推，最后得到 丨菱。因而。故4是T ：的最大公因数。第一章整数的可除性整除的进一步性质在最大公因数的计算方法（3）中，我们已看到带余数除法的重要性，在这一部分中， 我们来讨论；与的关系，由此可得到关于整除的进一步性质。设，：是任意两个正整数

12、，由带余数除法有：a =切+ 巾汗厂局+中0工©，由上面这一系列等式可得定理1若丄，是任意两个正整数，则U':'，k = 1, 2,，n其中证当'= 1时，（2 ）显然成立，当= 2时，由（1 ）得(2):(3)但11-U -L _-j-1,故”_ 一 门 _- 1'；_：_ _i 、上.-二；-'.<1假设（2）, （ 3）对于不超过上2 2的正整数都成立，则故其中一 一-二 J 1 ,卜 L 一、 一 J 1。 由归纳法，定理1的结论成立。由于'',于是由定理1立即可得到下面的结论。推论1.1若丄，丨是任意两个不全为零

13、的整数，则存在两个整数一，一使得as+加(偽 4)证在（2）中取'=:,得两边乘以 I:，得于是取 - 丁 二，一- 二，则二 一 m。定理2 若丄，：,c是三个整数，且（一：，c ）= 1，贝U（i），c与一：，c有相同的公因数。（ii）（"，c ） = C- , c）。其中：，c至少一个不为零。证 由最大公因数的定义，我们只须证明（i）由已知条件及推论1.1，存在两个整数一，一满足等式两边乘以J，得设d是血,c的任一公因数，则dab , dc于是由上式得de ,从而d为丨，C的一个公因数。反之，:.,C的任一公因数显然是，C的一个公因数。故（i）成立。由定理2及整除的基本

14、性质可得推论2.1若一一：,，则一。证因门必，故伽沪H。但由定理2有（血，C ） = （ & , c ）,所以 EL （扒C）。于是计卩，从而屮。推论2.2 设"*及：I'"' =；是任意两组整数。若前一组中任一整数与后一组中任一整数互质。则zy：与；互质。证由定理2可得再用定理2,= =（I 儿 l）= 1。有关整除的性质我们就讨论到此，这些性质都非常重要，大家在学习中要逐一理解并掌 握。第一章整数的可除性最小公倍数前面学了最大公因数，与此对应，在这一部分中，我们再讨论最小公倍数。我们将把最 小公倍数和最大公因数联系在一起，并由最大公因数的计算推出

15、最小公倍数的计算。最小公倍数的定义设* r " 是C- >2个整数。若是这、个数的倍数，则 Y就叫作这1个数的一个公倍数。又在、的一切公倍数中的最小正数叫做最小公倍数，记为由于任何正数均不是 0的倍数，故我们在讨论最小公倍数时总是假定G " 几均不为零。最小公倍数的性质为得到最小公倍数的计算方法，我们先讨论一下最小公倍数的性质。下面的定理1可将负数化为正数讨论，定理 2讨论了两个正整数的情形，最后定理 3讨论一般情况，即个正 整数（> 2的情形。定理 4'I-'该定理的证明类似于最大公因数中相应性质的证明，请大家作为练习自己给出证明。定理2设丄，

16、丨是任意两个正数，则，：的所有公倍数就是，一：的所有倍数。（乩Q ,特别地，若（证 设是，：的任一公倍数，由定义可得''二点=匸。令.；，； - '- -，由上式即得o但'-，由整除的性质得I ”。因此ah其中t满足'_ '1； o反过来，当:为任一整数时，为.（，:的一个公倍数,故（1）恰好表示.，:.的一切公倍数，当一 =1时即得到最小公倍数，故结论（ii）成立。将（2）代入（1）,结论（i）也成立。定理3设/、是1个正整数，令知如二 陶偽二吟，=（3）则 1 = o证由（3）,胸叫1, i=h 2 n -1, 且込蚀勺1團，i = 2严,月

17、，故是、的一个公倍数。又设是、的任一公倍数，则 曲曲 沟|删，故由定理2 （i）,朋2 M,又码 巴同样由定理2 （i）得蚀m，依此 类推，最后得时附，因此叫、IHo故叫=laY旳抵最小公倍数的计算2，只须计算由定理2和定理3,我们重点掌握两个正整数的最小公倍数的计算。由定理 出最大公因数，则由定理 2 （ii）即可求出最小公倍数。例设“ =169, ； = 121，求“，丿。解 由最大公因数的计算易求得（，）=1o故第一章整数的可除性质 数在正整数里，1的正因数只有1本身，因此在整数中间 1占有特殊的地位。任何一个大 于1的整数，都至少有两个正因数，即1和它本身。为更好地讨论这些数的性质，我

18、们把这些数进行分类。质数的定义一个大于1的整数，如果它的正因数只有1和它本身，就叫作质数（或素数）；否则就叫作合数。例如2，3，5，7等为质数，而4, 6，8，10等为合数。质数的性质定理1设是任一大于1的整数，则“的除1以外的最小正因数：是一个质数，并且当二为合数时，：-' o证 假定：不是质数，由定义，：除1及本身外还有一正因数 匸，因而 1匸“ 。但' - - ，所以上匸，这与1是“的除1以外的最小正因数矛盾。故 :一定是一个质 数。当为合数时，则"一，且'，否则是质数。由/的最小性知！ fl，从而/仙弋,故q亦。定理2若：是一质数，丄是任一整数，则 丿

19、能被：整除或者 / 互质。证因为;1 '，一二:，由质数的定义，（：，）=1，或者（P，dl）=P。即（P，M）= 1,或者川。推论2.1设/ r/'"' 、是'：个整数，是质数。若：，则* 一定能整除某一个''。证 假设""*均不能被整除，则由定理2，（：）= 1，；'-'。于是由整除的进一步性质中的推论2.2, J,这与-.l-L 矛盾。于是推论2.1成立。算术基本定理任一大于1的整数能表成质数的乘积，即任一大于1的整数(1)其中 h加山h 质数，并且若其中.'7上是质数，则:U;。证 我

20、们先用数学归纳法证明（1）式成立。当丿=2时，因2为质数，取:=1 ,1一：，（ 1 ）式成立。假设对一切小于的正整数，（1 ）式都成立，此时若为质数，则取、=1 ,一；这时（1）式对成立；若为合数，则有两正整数-,满足条件：=_：, 1； , 1 。由归纳假设于是；一' 二；将：的次序调动后即可得到（1 ）式。故（1）式对成立。由归纳法即知对任一大于1的正整数，（1 ）式成立。下面再证（1）式的唯一性。若厂一九 为质数，则防广利血（2）因此的宀。由推论2.1，有旳你，使得氷,'。但i :;均为质数，故""',又比-：7，故”-，因而,L由（2）式得

21、 t 匚'。同法可得八=识。依次类推，最后可得标准分解式由算术基本定理，将 的分解式（1）中的丨:，中相同的写成幕的形式可得到】=1, 2,上,（3）其中 加r h 为质数,PlPk称（3）式为Q的标准分解式。注 在具体应用中，有时为了同时考虑两个正整数，甚至更多时，常将它们写成一个统 一的表达式，汁打、I，。（4）其中为质数，二.宀。定理3设U的标准分解式为（3），则。的正因数d可表示成；，二一二一，二”。而且当：可以表成上面的形式时，.：是的正因数。证 若二二，则，"：'。由标准分解式的唯一性知：'的标准分解式中出现的质数都在一1）中出现，且 I在匚的标准

22、分解式中出现的指数 *、=,亦即罕。反过来，当L，.' - _：.时，显然整除-。由定理3及（4）式可以得到中学教科书中求最大公因数及最小公倍数的方法。定理4设，：是任意两个正整数，将-，-：写成（4）式的形状，则仏恥朴pP,厂二,其中了广血Op 0J ,叮m讹i，如，上。质数的个数问题对于质数的个数，有定理5质数的个数是无穷的。证假设在正整数中只有有限个质数，设为；I mi,令一二二二-，则N>1。由定理1，N有一质因数丿，这里°工门，：，：，否则 二'丨-，得"，矛盾。故r是上面个质数以外的质数。定理获证。第一章整数的可除性函数订与 在这一部分中，我们先介绍在数论里面常常用到的两个函数 与.，再讨论这两个函数的性质，最后利用这些性质实际求出.!的标准分解式。函数:与的定义函数 与:.是对于一切实数都有定义的函数，函数:的值等于不大于；的最大整数；函数 L.的值是二丨二。我们常常把:叫做的整数部分，;叫；的小数部分。例【闻?，圖=2，卜小4，【# = &#