算术基本定理.doc

关于质和计算基本定理的问题一、知识大于1的整数总有两个不同的正约数：1和.若仅有两个正约数（称没有正因子），则称为质数（或素数）.若有真因子，即可以表示为的形式（这里为大于1的整数），则称为合数.正整数被分为三类：数1，素数类，合数类关于素数的一些重要理论1.大于1的整数必有素约数.2.设为素数，为任意一个整数，则或者整除，或者与互素.事实上，与的最大公约数必整除，故由素数的定义推知，或者，或者，即或者与互素，或者.3.设为素数，为整数.若，则中至少有一个数被整除.事实上，若不整除，由性质2知，与均互素，从而与互素。这与已知的矛盾.特别地：若素数整除，则4.定理1 素数有无限多个 (公元前欧几里得给出证明)证明：（反证法）假设只有k个素数，设它们是。记。（N不一定是素数）由第一节定理2可知，有素因数，我们要说明从而得出矛盾事实上，若有某个使得则由推出，这是不可能的。因此在之外又有一个素数，这与假设是矛盾的。所以素数不可能是有限个。5.引理1 任何大于1的正整数可以写成素数之积，即 (1)其中是素数。证明 当时，结论显然成立。假设对于，式(1)成立，我们来证明式(1)对于也成立，从而由归纳法推出式(1)对任何大于1的整数成立。如果是素数，式(1)显然成立。如果是合数，则存在素数与整数，使得。由于，由归纳假定知存在素数，使得，从而。证毕。6.定理2(算术基本定理)任何大于1的整数可以唯一地表示成， (2)其中是素数，是正整数。我们称是的标准分解式，其中是素数，是正整数.证明：由引理1，任何大于1的整数可以表示成式(2)的形式，因此，证明表示式(2)的唯一性。假设与都是素数， (3)并且 ， (4)则由第三节定理4推论1，必有某个，使得，所以；又有某个，使得，所以。于是，由式(3)可知，从而由式(4)得到重复上述这一过程，得到 证毕。7.定理：若设为的正约数的个数，为的正约数之和，则有（1）（2）8.推论1 使用式(2)中的记号，有() 的正因（约）数d必有形式d =() 的正倍数必有形式 9.推论2 设正整数a与b的标准分解式是，其中p1, p2, L, pk 是互不相同的素数，ai，bi（1 i k）都是非负整数，则10.推论3 设a，b，c，n是正整数， ab = cn ，(a, b) = 1， (5)则存在正整数u，v，使得a = un，b = vn，c = uv，(u, v) = 1。证明 设c =，其中p1, p2, L, pk 是互不相同的素数，gi（1 i k）是正整数。又设，其中aI，bi（1 i k）都是非负整数。由式(5)及推论2 可知minai, bi = 0，ai + bi = ngi，1 i k，因此，对于每个i（1 i k），等式ai = ngi ，bi = 0与ai = 0，bi = ngi有且只有一个成立。这就证明了推论。证毕。11.定理： 对任意的正整数及素数，记号表示，即是的标准分解中出现的的幂.设，为素数，则这里表示不超过实数的最大整数.由于当时, 则，故上面和式中只有有限多个项非零.另一种表现形式：设为任一素数，在中含的最高乘方次数记为，则有：证明：由于是素数，所有中所含的方次数等于的各个因数所含的方次数之总和。由性质10可知，在中，有个的倍数，有个的倍数，有个的倍数，当时，所以命题成立。另证：对于任意固定的素数，以表示在的标准分解式中的的指数，则以表示中等于的个数，那么 (2)显然，就是在中满足并且pj + 1的整数的个数，所以由定理2有。将上式代入式(2)，得到即式(1)成立。证毕。二、重要方法证明某些特殊形式的数不是素数（或给出其为素数的必要条件）是初等数论中较为基本的问题，其方法是应用各种分解技术（如代数式的分解），指出所给数的一个真因子常用分解技术有：（1） 利用代数式分解（如因式分解）指出其一个真因子；（2） 应用数的分解（例如算术基本定理），指出数的一个真因子；（3）运用反证法，假定其是素数，然后利用素数的性质推出矛盾.三、例题讲解例1.证明：无穷数列中没有素数. （教材第13页例1）证明：记，则对分奇偶讨论：（1）当为偶数时，设，则显然是大于1的整数，当时，是大于1的整数而当时，是合数.(2) 当为奇数时，设，易知都是大于1的整数综上：命题获证；例2.证明：对任意整数，数不是素数.（教材第13页例2）证明：我们对分奇偶讨论：（1） 当为偶数时，大于2，且也为偶数，故结论显然成立.（2） 当为奇数时，设，则由于，所以都是大于1的整数，故是合数. 综上：不是素数.例3.设正整数满足，证明：不是素数证明一：本题不宜采用代数式的分解来产生所需的分解.我们的第一种解是应用数的分解，指出的一个真因子.由，可设，其中是互素的正整数. 故，同理故是两个大于1的整数积，从而不是素数.证明二：由，得，因此，因是整数.若它是一个素数，设为，则由（*），故或，不妨设，则，结合（*）式得：，即，这不可能，故结论成立;例4.设整数满足，且证明：不是素数. （教材第18页习题3-4）证明：本题运用反证法，设有满足题设的一组，使得为素数，将其记为，于是带入已知条件得到：由于是素数，故或者（）若，则由，推出，即，从而，显然（因为是素数）故，这与矛盾.（）若，则由知，故，进而得到，于是得到都成立，但又知，故被和整除.因从而必须有，矛盾.例5.证明：若整数满足，则和都是完全平方数. 证明：已知关系式变形为（1）论证的第一个要点是证明整数与互素.记.若，则有素因子，从而由（1）知,因是素数，故.结合知.再由导出，这不可能，故，即与互素.因此，由（1）得右端为（1）是一个完全平方数，故均是完全平方数.下面证明，我们运用反证法.假设有整数满足问题中的等式，但.因已证明是一个完全平方数故有，这里；结合（1）推出，再由得出.设，带入问题中的等式可得(注意) （2）将上式视为关于的二次方程，由求根公式解得，因是整数，故由上式知是完全平方数.但易知一个完全平方数被3除得的余数只能为0或1；而被3除得余数为2，矛盾.(或者更直接地：由被3除得余数为0或1，故（2）左边被3除得的余数是1或2；但（2）的右边为0，被3整除.矛盾.即（2）对任何整数及均不成立)从而必须有，这就证明了本题的结论.注：1.许多数论问题需证明一个正整数为1（例如，证明整数的最大公约数是1），由此我们常假设所说的数有一个素因子，利用素数的锐利性质（3）作进一步论证，以导出矛盾.如例4例6写出的标准分解式，并求它的正约数的个数；解：我们有例7求最大的正整数，使得解：因为,正整数的最大值取决于的分解式中所含5的幂指数.由定理2，的标准分解式中所含的5的幂指数是 所以，所求的最大整数是。例8设与是实数，则 (*)证法一:设，则右边， (1) 左边 ， (2)如果，那么显然有；如果，那么a与b中至少有一个不小于，于是。因此无论或1，都有，由此及式(1)和式(2)可以推出式(*)成立.证法二:注意到对任意整数及任意实数，即上述不等式中或 改变一个整数量，则不等式(*)两边改变一个相同的量.故不等式(*)只需证明的情形即可.于是问题等价于证明：下面同证法一例9一个经典的问题设是非负整数，证明：是一个整数.证明:我们只需证明：对每一个素数，分母的标准分解中的幂次，不超过分子中的幂次,由定理知等价于证明 事实上我们能够证明一个更强的命题：设x与y是实数，则 这就是例9讨论的问题.结合知命题成立.例10设是整数，证明：() ；() 。解 为了叙述方便，不妨假定是正整数。() 设，其中是互不相同的素数，都是非负整数。由定理1推论2 ，有由此知=；() 设，其中是互不相同的素数，都是非负整数。由定理有，其中，对于，有，不妨设，则，所以 ，即。注：利用定理可以容易地处理许多像这样的问题。引理：设整数，证明：() 若，则；() 若，则 证明:() 若，则存在整数，使得。显然只可能是0或1。此时或这都是不可能的，所以；() 若 ，则存在整数，使得，显然只可能是0，1, 或2。此时，或，这都是不可能的，所以。推论3 设a，b，c，n是正整数， ab = cn ，(a, b) = 1， (5)则存在正整数u，v，使得a = un，b = vn，c = uv，(u, v) = 1。证明 设c =