第一章第六节算术基本定理

1、 初等数论 第一章 整除理论 第六节 素数与算术基本定理（正整数唯一分解定理）一、 知识 大于1的整数总有两个不同的正约数：1和.若仅有两个正约数（称没有正因子），则称为素数（或质数）.若有真因子，即可以表示为的形式（这里为大于1的整数），则称为合数. 正整数被分为三类：数1，素数类，合数类关于素数的一些重要理论1. 大于1的整数必有素约数.2. 设为素数，为任意一个整数，则或者整除，或者与互素.事实上，与的最大公约数必整除，故由素数的定义推知，或者，或者，即或者与互素，或者.【素数最精彩的性质是下面的】：3. 设为素数，为整数.若，则中至少有一个数被整除.事实上，若不整除，由性质2知，与均互

2、素，从而与互素。这与已知的矛盾.特别地：若素数整除，则4. 定理1 素数有无限多个 (公元前欧几里得给出证明)证明：（反证法）假设只有k个素数，设它们是p1, p2, L, pk 。记N = p1p2Lpk + 1。（N不一定是素数）由第一节定理2可知，N有素因数p，我们要说明p ¹ pi ，1 £ i £ k，从而得出矛盾事实上，若有某个i，1 £ i £ k，使得p = pi ，则由p½N = p1p2Lpk + 1推出p½1，这是不可能的。因此在p1, p2, L, pk之外又有一个素数p，这与假设是矛盾的。所以素数不

3、可能是有限个。5.引理1 任何大于1的正整数n可以写成素数之积，即n = p1p2Lpm， (1)其中pi（1 £ i £ m）是素数。证明 当n = 2时，结论显然成立。假设对于2 £ n £ k，式(1)成立，我们来证明式(1)对于n = k + 1也成立，从而由归纳法推出式(1)对任何大于1的整数n成立。如果k + 1是素数，式(1)显然成立。如果k + 1是合数，则存在素数p与整数d，使得k + 1 = pd。由于2 £ d £ k，由归纳假定知存在素数q1, q2, L, ql，使得d = q1q2Lql，从而k + 1 =

4、 pq1q2Lql。证毕。6.定理2(算术基本定理)【刻画了素数在正整数集合中的特殊重要的地位】 任何大于1的整数n可以唯一地表示成n =， (2)其中p1, p2, L, pk是素数，p1 < p2 < L < pk，a1, a2, L, ak是正整数。我们称n =是n的标准分解式，其中pi（1 £ i £ k）是素数，p1 < p2 < L < pk，a i（1 £ i £ k）是正整数.【证明】 由引理1，任何大于1的整数n可以表示成式(2)的形式，因此，只需证明表示式(2)的唯一性。假设pi（1 £

5、i £ k）与qj（1 £ j £ l）都是素数，p1 £ p2 £ L £ pk，q1 £ q2 £ L £ ql， (3)并且 n = p1p2Lpk = q1q2Lql ， (4)则由第三节定理4推论1，必有某个qj（1 £ j £ l），使得p1½qj，所以p1 = qj；又有某个pi（1 £ i £ k），使得q1½pi，所以q1 = pi。于是，由式(3)可知p1 = q1，从而由式(4)得到p2Lpk = q2Lql 重复上述这一过

6、程，得到k = l，pi = qi ，1 £ i £ k 。证毕。7.若设为n的正约数的个数，为n的正约数之和，则有（1）（2）8.推论1 使用式(2)中的记号，有() n的正因（约）数d必有形式d =，giÎZ，0 £ gi £ a i，1 £ i £ k；() n的正倍数m必有形式 m =M，MÎN，biÎN，bi ³ a i，1 £ i £ k。证明 9.推论2 设正整数a与b的标准分解式是，其中p1, p2, L, pk 是互不相同的素数，ai，bi（1 £

7、 i £ k）都是非负整数，则10.定理（极为重要） 对任意的正整数及素数，记号表示，即是的标准分解中出现的的幂.设，为素数，则这里表示不超过实数的最大整数.由于当时, 则，故上面和式中只有有限多个项非零.【另一种表现形式】设为任一素数，在中含的最高乘方次数记为，则有：【证明】由于是素数，所有中所含的方次数等于的各个因数所含的方次数之总和。由性质10可知，在中，有个的倍数，有个的倍数，有个的倍数，当时，所以命题成立。【另证】对于任意固定的素数p，以p(k)表示在k的标准分解式中的p的指数，则p(n!) = p(1) + p(2) + L + p(n)。以nj表示p(1), p(2),

8、 L, p(n)中等于j的个数，那么p(n!) = 1×n1 + 2×n2 + 3×n3 + L ， (2)显然，nj就是在1, 2, L, n中满足pj½a并且pj + 1a的整数a的个数，所以，由定理2有nj =。将上式代入式(2)，得到即式(1)成立。证毕。二、重要方法证明某些特殊形式的数不是素数（或给出其为素数的必要条件）是初等数论中较为基本的问题，其方法是应用各种分解技术（如代数式的分解），指出所给数的一个真因子常用分解技术有：（1）利用代数式分解（如因式分解）指出其一个真因子；（2）应用数的分解（例如算术基本定理），指出数的一个真因子；（3）

9、运用反证法，假定其是素数，然后利用素数的性质推出矛盾.三、例题讲解例1.证明：无穷数列中没有素数. （教材第13页例1）【证明】记，则对分奇偶讨论：（1）当为偶数时，设，则显然是大于1的整数，当时，是大于1的整数而当时，是合数.(2) 当为奇数时，设，易知都是大于1的整数综上：命题获证；例2.证明：对任意整数，数不是素数.（教材第13页例2）【证明】我们对分奇偶讨论：（1） 当为偶数时，大于2，且也为偶数，故结论显然成立.（2） 当为奇数时，设，则由于，所以都是大于1的整数，故是合数. 综上：不是素数.例3.设正整数满足，证明：不是素数（教材第14页例3）【证明一】本题不宜采用代数式的分解来产

10、生所需的分解.我们的第一种解法是应用数的分解，指出的一个真因子.由，可设，其中是互素的正整数.故，同理故是两个大于1的整数之积，从而不是素数.【证明二】由，得，因此，因是整数.若它是一个素数，设为，则由（*），故或，不妨设，则，结合（*）式得：，即，这不可能，故结论成立;例4.设整数满足，且证明：不是素数. （教材第18页习题3-4）【证明】本题运用反证法，设有满足题设的一组，使得为素数，将其记为，于是带入已知条件得到：由于是素数，故或者（）若，则由，推出，即，从而，显然（因为是素数）故，这与矛盾.（）若，则由知，故，进而得到，于是得到都成立，但又知，故被和整除.因从而必须有，矛盾.例5.证明

11、：若整数满足，则和都是完全平方数. （教材第14页例4）【证明】已知关系式变形为（1）论证的第一个要点是证明整数与互素.记.若，则有素因子，从而由（1）知,因是素数，故.结合知.再由导出，这不可能，故，即与互素.因此，由（1）得右端为（1）是一个完全平方数，故均是完全平方数.下面证明，我们运用反证法.假设有整数满足问题中的等式，但.因已证明是一个完全平方数，故有，这里；结合（1）推出，再由得出.设，带入问题中的等式可得(注意)（2）将上式视为关于的二次方程，由求根公式解得，因是整数，故由上式知是完全平方数.但易知一个完全平方数被3除得的余数只能为0或1；而被3除得余数为2，矛盾.(或者更直接地

12、：由被3除得余数为0或1，故（2）左边被3除得的余数是1或2；但（2）的右边为0，被3整除.矛盾.即（2）对任何整数及均不成立)从而必须有，这就证明了本题的结论.【注】1.许多数论问题需证明一个正整数为1（例如，证明整数的最大公约数是1），由此我们常假设所说的数有一个素因子，利用素数的锐利性质（3）作进一步论证，以导出矛盾.如例4例6写出的标准分解式，并求它的正约数的个数；【解答】我们有51480 = 2×25740 = 22×12870 = 23×6435= 23×5×1287 = 23×5×3×429= 23&

13、#215;5×32×143 = 23×32×5×11×13例7求最大的正整数k，使得10k½199!【解答】因为,正整数k的最大值取决于199!的分解式中所含5的幂指数.由定理2，199!的标准分解式中所含的5的幂指数是 = 47，所以，所求的最大整数是k = 47。例8设x与y是实数，则2x + 2y ³ x + x + y + y (*)【证法一】设x = x + a，0 £ a < 1，y = y + b，0 £ b < 1，则右边=x + x + y + y = 2x + 2

14、y + a + b， (1)左边=2x + 2y = 2x + 2y + 2a + 2b。 (2)如果a + b = 0，那么显然有a + b £ 2a + 2b；如果a + b = 1，那么a与b中至少有一个不小于，于是2a + 2b ³ 1 = a + b。因此无论a + b = 0或1，都有a + b £ 2a + 2b，由此及式(1)和式(2)可以推出式(*)成立.【证法二】注意到对任意整数及任意实数，即上述不等式中或 改变一个整数量，则不等式(*)两边改变一个相同的量.故不等式(*)只需证明的情形即可. 于是问题等价于证明：2x + 2y ³

15、x + y 下面同证法一例9【一个经典的问题】设是非负整数，证明：是一个整数.【证明】我们只需证明：对每一个素数，分母的标准分解中的幂次，不超过分子中的幂次,由定理知等价于证明 事实上我们能够证明一个更强的命题：设x与y是实数，则2x + 2y ³ x + x + y + y 这就是例9讨论的问题.结合知命题成立.例10设a，b，c是整数，证明：() (a, b)a, b = ab；() (a, b, c) = (a, b), (a, c)。解 为了叙述方便，不妨假定a，b，c是正整数。() 设，其中p1, p2, L, pk是互不相同的素数，ai，bi（1 £ i

16、63; k）都是非负整数。由定理1推论2 ¢，有由此知(a, b)a, b =ab；() 设，其中p1, p2, L, pk是互不相同的素数，ai，bi，gi（1 £ i £ k）都是非负整数。由定理有，其中，对于1 £ i £ k，有li = minai, maxbi, gi，mi = maxminai, bi, minai, gi，不妨设bi £ gi，则minai, bi £ minai, gi，所以mi = minai, gi = li ，即(a, b, c) = (a, b), (a, c)。注：利用定理可以容易地

17、处理许多像这样的问题。例11、证明：（n ³ 2）不是整数【为此我们先证明下面的一个引理】设整数k ³ 1，证明：() 若2k £ n < 2k + 1，1 £ a £ n，a ¹ 2k，则2ka；() 若3k £ 2n - 1 < 3k + 1，1 £ b £ n，2b - 1 ¹ 3k，则3k2b - 1 【证明】() 若2k|a，则存在整数q，使得a= q2k。显然q只可能是0或1。此时a= 0或2k ，这都是不可能的，所以2ka；() 若 3k|2b-1，则存在整数q，使得2

18、b-1= q3k，显然q只可能是0，1, 或2。此时2b-1= 0，3k，或，这都是不可能的，所以3k2b - 1。【证明】设3k £ 2n - 1 < 3k + 1对于任意的1 £ i £ n，2i - 1 ¹ 3k，记2i - 1 =Qi，QiÎZ，由前面引理知ai £ k - 1。因为3k - 1Q1Q2LQ2n - 1是整数，所以，如果N是整数，则存在整数Q，使得3k - 1Q1Q2LQ2n - 1N = Q + 3k - 1Q1Q2LQ2n -1由于3Q1Q2LQ2n-1，所以上式右端不是整数，这个矛盾说明N不能是整数

19、习 题 六1. 写出22345680的标准分解式【解答】2.证明：有无穷多个奇数，使得是合数. （教材第18页习题3-3）【分析】取，则，由因式分解定理知其有真因子；故是合数.3.证明：对任意给定的正整数，都存在连续个合数. （教材第18页习题3-1）【证明】构造例如就符合，也符合； 故可证明：是个连续的合数；4. 证明：在1, 2, L, 2n中任取n + 1数，其中至少有一个能被另一个整除。【解答】构造，则为中的奇数，即只能取这个值.在个这样的数中，必存在，于是易知与成倍数关系.5. 证明：形如的素数有无穷多个，形如的素数也有无穷多个（为正整数）（教材第18页习题3-2）【证明】可将欧几里

20、得证明素数有无穷多个的方法稍作修改来论证.假设形式的素数只有有限多个，设它们的全部为.考虑数，显然，故,故有素因子.进一步因两个形式的数之积仍具有形式，而有形式，故必有一个形式的素因子，由前面的假设知，应同于之一，进而被整除，即，矛盾.同理可证明形如的素数也有无穷多个.6.设是互素的正整数，证明： （教材第17页例7）【证法一】等价于证明是一个整数.与上例相似，我们证明，对每个素数，有（1）我们希望证明单项不等式：（2）对任意素数及任意整数成立.然而我们不能搭建像上例中那样的对所有实数成立的结果导出（2），需要利用所说整数的特别性质： 由带余除法，这里，而均为非负整数，则有.但，故不能同时为0，从而故，这就证明了（2）.证毕