算术基本定理

1、关于质和计算基本定理的问题一、知识大于 1 的整数 n 总有两个不同的正约数： 1 和 n .若 n 仅有两个正约数（称 n 没有正因子），则称 n 为质数（或素数） .若 n 有真因子，即 n 可以表示为 a b 的形式（这里 a, b 为大于 1 的整数），则称 n 为合数 .正整数被分为三类：数1，素数类，合数类关于素数的一些重要理论1.大于 1 的整数必有素约数 .2.设 p 为素数， n 为任意一个整数，则或者p 整除 n ，或者 p 与 n 互素 .事实上， p 与 n 的最大公约数 ( p, n) 必整除 p ，故由素数的定义推知，或者( p, n)1，或者 ( p,n)p ，即

2、或者 p 与 n 互素，或者 p | n .3.设 p 为素数， a,b 为整数 .若 p | ab ，则 a, b 中至少有一个数被p 整除 .事实上，若 p 不整除 a和 b ，由性质 2 知， p 与 a和b 均互素，从而 p 与 ab 互素。这与已知的p | ab矛盾 .特别地：若素数p 整除 an (n1) ，则p | a4.定理1素数有无限多个(公元前欧几里得给出证明)证明：（反证法） 假设只有 k 个素数，设它们是p1， p2，L ， pk 。记Np1 p 2 L p w 1 。（ N 不一定是素数）由第一节定理2 可知， p 有素因数 p ，我们要说明 p pi ,1 ik 从

3、而得出矛盾事实上，若有某个i,1ik 使得 ppi ,则由p | Np1 p 2 Lp w1推出p |1 ，这是不可能的。因此在p1，p2，L， pk 之外又有一个素数p ，这与假设是矛盾的。所以素数不可能是有限个。5.引理1任何大于1 的正整数n 可以写成素数之积，即np1p 2 Lp m(1)其中pi ,1im 是素数。证明当 n=2 时，结论显然成立。假设对于 2nk ，式 (1)成立，我们来证明式(1)对于 n=k1 也成立，从而由归纳法推出式 (1)对任何大于 1 的整数 n 成立。如果 k1是素数，式 (1)显然成立。如果 k1是合数，则存在素数 p 与整数 d ，使得 k 1=p

4、d 。由于 2 d k ，由归纳假定知存在素数 q1 , q2 ,L ql ，使得 dq1, q2 ,L ql ，从而 k 1 pq1, q2 ,L ql 。证毕。6.定理 2(算术基本定理 )任何大于 1 的整数 n 可以唯一地表示成n p11 p22 Lpk k ，(2)其中 p1， p2，L ， pk 是素数， p1p2 Lpk ， a1 , a2 ,L , ak 是正整数。我们称 np11 p22 L pk k a1 , a2 ,L , ak 是 n 的标准分解式，其中 pi ,1 ik 是素数，p1 p2 Lpk，是正整数 .证明：由引理 1，任何大于 1 的整数 n 可以表示成式

5、(2)的形式，因此，证明表示式 (2)的唯一性。假设 pi ,1 ik 与 q j,1j l 都是素数，p1p2Lpk ， q1q2Lql ，(3)并且np1 p2 Lpkq1q2 Lql ，(4)则由第三节定理 4推论 1，必有某个 qj ,1jl ，使得 p1| qi ，所以 p1 =qi ；又有某个 pi ,1ik ，使得 q1 | pi ，所以 q1 =pi 。于是，由式 (3)可知 p1 =q1 ，从而由式 (4)得到p2 Lpk =q2 L ql重复上述这一过程，得到k l , piqi ,1ik 证毕。7.定理：若设 ( n) 为 n 的正约数的个数，(n) 为 n 的正约数之和

6、，则有（1） ( n) ( 11)( 21)gg(k1)（2）p 1 11 p 2 11pkk 11(n)12ggp11p21pk18.推论 1使用式 (2)中的记号，有( )n 的正因（约）数d 必有形式d =dp1 1 p2 2 Lpkk , 1Z,0ii ,1ik( )n 的正倍数 m 必有形式mp1 1 p2 2 Lpk k M , MN ,iN ,ii ,1ik9.推论 2设正整数 a 与 b 的标准分解式是a p1 1 p2 2p k k ， b p1 1 p2 1p k k ，其中 p12k 是互不相同的素数，i，i（1 i k）都是非负整数，, p , p则(a, b) p1

7、p1pk ，i12k a, b p1 1 p 21p k k ，imini ,i ， 1ik，maxi , i ， 1ik。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 1 p 21p kk ，其中 p1, p2, pk 是互不相同的素数，（i1ik）是正整数。又设a p1 1 p 2 2p k k ， bp1 1 p2 1pk k ，其中Iik）都是非负整数。由式 (5)及推论 2可知，（ 1 imin ,i=0，ii= n， 1 ik，

8、ii因此，对于每个 i（1ik），等式i = n i ， i = 0 与 i = 0， i = n i有且只有一个成立。这就证明了推论。证毕。11.定理： 对任意的正整数m 及素数 p ，记号 p| m 表示 p| m, p1 | m ，即 p 是 m 的标准分解中出现的p 的幂 .设 n 1 ， p 为素数， p p | n! ，则 a pnnnl 1plpp2这里 x 表示不超过实数 x 的最大整数 .由于当 pln 时, 则n0 ，故上面和式pl中只有有限多个项非零 .另一种表现形式：设 p 为任一素数，在 n! 中含 p 的最高乘方次数记为 pn!，则有：p n!nnLnpm n pm

9、 1pp2pm证明：由于 p 是素数，所有 n! 中所含 p 的方次数等于 n! 的各个因数 1,2,L , n所含 p 的方次数之总和。由性质10 可知，在 1,2, L , n 中，有 n个 p 的倍数，p有n个 p2 的 倍 数 ， 有n个 p3的 倍 数 ， L ，当 pmn pm 1 时 ，p2p3nnL 0 ，所以命题成立。pm 1pm 2另证： 对于任意固定的素数p ，以 p k 表示在 k 的标准分解式中的p 的指数，则p n! =p(1)p(2)Lp(n).以 n j 表示 p(1), p(2), L , p(n) 中等于 j 的个数，那么p n! =1 n12 n23 n3

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

11、个真因子；（3）运用反证法，假定其是素数，然后利用素数的性质推出矛盾 .三、例题讲解例 1.证明：无穷数列 10001,100010001,中没有素数 . （教材第 13 页例 1）证明：记 an10001L10001,(n 2)，则1 4424 43n个1an 1 104108104( n 1)104n11041对 n 分奇偶讨论：（1）当 n 为偶数时，设 n108k1108k1 10812k ，则 an110811041104显然 1081 是大于 1 的整数，当 k2 时， 108k1(108 )k1 是大于 1 的整数104110811081而当 k1 时， a2 10001 131

12、37 是合数 .(2) 当为奇数时，设 n 2k 1 ，n an108k41 10 4k21 104 k 21(102 )2k11 (102 ) 2k1 110411021102110 211021易知 (102 )2k 11, (102 )2k11 都是大于 1 的整数102110 21综上：命题获证；例 2.证明：对任意整数 n 1 ，数 n4 4n 不是素数 .（教材第 13 页例 2）证明：我们对 n 分奇偶讨论：（1）当为偶数时，n44n大于，且也为偶数，故结论显然成立.2（2）当为奇数时，设 n2k 1，则n4 4nn442k1n44 (2k )4(n2 2 22k )24n2 (

13、2k)2(n22 22k )2(2n 2k )2(n22 22k2n 2k )(n22 22k 2n 2k)由于 n1 ，所以 n22 22k2n 2k , n22 22 k2n2k 都是大于 1 的整数，故 n44n 是合数 .综上： n44n 不是素数 .例 3.设正整数 a, b, c, d 满足 ab cd ，证明： abc d 不是素数证明一： 本题不宜采用代数式的分解来产生所需的分解.我们的第一种解是应用数的分解，指出ab cd 的一个真因子 .由 ab cd ，可设 adm ，其中 m, n 是互素的正整数 .cbn故 amu,cnu ，同理 dmv, cnv故 ab cdmun

14、umvnv(mn)(uv) 是两个大于 1 的整数积，从而不是素数 .证明二：由 abcd ，得 bcd ，因此 abc dac dcd(a c)(a d ) ，因aaaa b c d 是整数 .若它是一个素数，设为 p ，则由(a c)(a d) ap （* ）， p | (ac)(ad )故 p |( ac) 或 p | ( a d ) ，不妨设， p | (ac) 则 acp ，结合（* ）式得：a da ，即 d0 ，这不可能，故结论成立 ;例 4.设整数 a,b,c,d 满足 abcd0 ，且 a2acc2b2bd d 2证明： ab cd 不是素数 .（教材第 18 页习题 3-4

15、）证明：本题运用反证法， 设有满足题设的一组 a, b,c, d ，使得 abcd 为素数，将其记为 p abcd ，于是 apcd 带入已知条件得到：bp( p2cdbc)(b2c2 )(b2bdd 2 )由于 p 是素数，故 p | (b2c2 ) 或者 p | (b2bdd 2 )（）若 p | (b2c2 ) ，则由 b2c2abab2ab2(abcd )2 p ，推出b2c2p ，即 b2c2abcd ，从而 b | c(cd ) ，显然 (b, c)1（因为 b2c2 是素数）故 b | (cd ) ，这与 0cdcb 矛盾 .（）若p | (b2bdd2 )， 则 由0b2bdd

16、 22(abcd )2 p知b2bdd 2p ，故a2acc2b2bdd 2abcd，进而得到a2acc(cd )ab, b2bdd(dc)ab ，于是得到 a |c(c因 0cd2a,0d ), b | d (ccdd ) 都成立，但又知2b 从而必须有 cd(ab, cd )a,cd1 ，故被 c b ，矛盾 .d a 和 b 整除 .例5.证明：若整数a, b 满足2a2a3b2b ，则ab 和 2a2b1都是完全平方数 .证明：已知关系式变形为( ab)(2 a2b1)b2 （1）论证的第一个要点是证明整数ab 与 2a2b1互素 .记(ab,2 a2b1)d .若d1 ，则 d 有素

17、因子 p ，从而由（1）知 p | b2 ,因 p 是素数，故 p |b .结合 p | (ab)知 p | a .再由 p | (2a 2b 1)导出 p |1，这不可能，故 d 1 ，即 ab 与 2a2b1互素 .因此，由（ 1）得右端为（ 1） b2是一个完全平方数，故 | ab |,| 2a2b1| 均是完全平方数 .下面证明 ab 0 ，我们运用反证法 .假设有整数 a, b 满足问题中的等式，但 a b0 .因已证明 | ab |是一个完全平方数故有 b ar 2 ，这里 r 0 ；结合（ 1）推出 r |b ，再由 bar 2 得出 r | a .设 b b1 r, a a1

18、r ，带入问题中的等式可得 (注意 r0, b1a1 r )a126a1r 3r 2 1 0（2）将上式视为关于 a1 的二次方程，由求根公式解得 a13r6r 21 ，因 a1 是整数，故由上式知 6r 21 是完全平方数 .但易知一个完全平方数被3 除得的余数只能为 0或 1；而 6r 21 被 3 除得余数为 2，矛盾 .(或者更直接地：由 a12 被 3 除得余数为 0 或 1，故（2）左边被 3 除得的余数是 1 或 2；但（ 2）的右边为 0，被 3 整除 .矛盾 .即（ 2）对任何整数 a1 及 r 均不成立 )从而必须有 ab0 ，这就证明了本题的结论.注： 1.许多数论问题需

19、证明一个正整数为1（例如，证明整数的最大公约数是 1），由此我们常假设所说的数有一个素因子，利用素数的锐利性质（3）作进一步论证，以导出矛盾 .如例 4例 6 写出 n 51480的标准分解式，并求它的正约数的个数(n) ；解：我们有51480225740221287023643523512872353429235321432332511 13(n) ( 11)( 21)gg( k1)(31)(21)(1 1)(11)(11)96例 7 求最大的正整数 k ，使得 10 k |199 !解：因为 102 5,正整数 k 的最大值取决于 199! 的分解式中所含 5 的幂指数 .由定理 2， 1

20、99! 的标准分解式中所含的5 的幂指数是1991992 1993 L47555所以，所求的最大整数是 k 47 。例 8 设 x 与 y 是实数，则 2 x2 y 3 x xy y(*)证法一 :设 x x, 01， y y,01 ，则右边 x x y y2 x2? y，(1)左边2 x2 y 2x2? y22，(2)如果0 ，那么显然有22；如果1，那么 与中至少有一个不小于 1，于是2221。因此无论0 或 1，都有22，由此及式 (1)和式 (2)可以推出式 (*)成立 .证法二 :注意到对任意整数 k 及任意实数， kk，即上述不等式中 x 或 y改变一个整数量，则不等式 (*) 两

21、边改变一个相同的量 .故不等式 (*)只需证明 0 x1,0 y1 的情形即可 .于是问题等价于证明 ： 2 x2 y xy 下面同证法一例 9一个经典的问题设 m, n 是非负整数，证明：(2 m)!(2 n)!是一个整数 .m! n!( m n)!证明 :我们只需证明：对每一个素数p ，分母 m! n!(mn)! 的标准分解中 p 的幂次，不超过分子(2 m)!(2 n)! 中 p 的幂次 ,由定理知等价于证明2m2nmnm nl 1plpll 1plplpl事实上我们能够证明一个更强的命题：设 x 与 y 是实数，则 2 x2 y 3 x xy y这就是例 9 讨论的问题 .结合知命题成

22、立 .例 10 设 a,b,c 是整数，证明：( )(a, b) a, bab ；( )(ab,c)( a,b),( a,c) 。解为了叙述方便，不妨假定a,b,c 是正整数。()设ap1 1 p2 2 Lpk k， bp1 1 p2 1 Lpk k b ，其中 p1， p2，L ， pk 是互不相同的素数，i , i (1ik) 都是非负整数。由定理1推论 2，有(a,b)p11 p21 Lpk k， imini ,i ，1ik，a,bp11 p21 Lpk k，imaxi ,i ，1ik。由此知(a,b) a, b =kkpimini ,i maxi ,i kpiiipiiiab ；i1i 1i1( )设kkkapii ， bpii， cpii，i1i1i 1其中 p1， p2，L ， pk 是互不相同的素数，i , i , i (1ik ) 都是非负整数。由定理有kk(a, b,c)pii ，