算术基本定理

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，即或者 p与n互素，或者 p|n.3. 设p为素数，a,bp|ab，那么a, b中至少有一个数被p整除.事实上，假设p不整

2、除a和b，由性质2知，p与a和b均互素，从而p与ab 互素。这与的p | ab矛盾.特别地：假设素数p整除an n 1，那么p | a4. 定理1素数有无限多个公元前欧几里得给出证明证明：反证法假设只有k个素数，设它们是 J, p2,，pk。记NP1P2Pw1。 N不一定是素数由第一节定理2可知，p有素因数p，我们要说明p p,1 i k从而得出 矛盾事实上，假设有某个i,1 i k使得p 5那么由p I N P1P2 Pw 1推出P |1 ，这是不可能的。因此在P-!，P2,，Pk之外又有一个素数P，这 与假设是矛盾的。所以素数不可能是有限个5. 引理1任何大于1的正整数n可以写成素数之积，

3、即nP1P2 Pm 其中口,1 i m是素数。证明 当n=2时，结论显然成立。假设对于2 n k，式(1)成立，我们来证明式(1)对于n=k 1也成立，从而 由归纳法推出式(1)对任何大于1的整数n成立。如果k 1是素数，式(1)显然成立。如果k 1是合数，那么存在素数p与整数d，使得k仁pd。由于2 d k，由归纳假定知存在素数 qq,qi，使得d qq,q，从而k 1 pqq,qi。 证毕。6. 定理2(算术根本定理)任何大于1的整数n可以唯一地表示成n P/P22 Pkk，(2)其中P1，P2,，Pk是素数，P1P2Pk，厲月2,ak是正整数。我们称n Pl1 P22Pkk Oi，a2,

4、ak是n的标准分解式，其中Pi ,1 i k是素数，Pi P2 Pk，是正整数证明：由引理1,任何大于1的整数n可以表示成式 的形式，因此，证明 表示式(2)的唯一性。假设Pi,1 i k与qj,1 j l都是素数，P1 P2 Pk，q q?q，并且n P4 Pk qq?qi，(4)那么由第三节定理4推论1，必有某个q ,1 j l，使得P | cj，所以P1=qi ;又有某个Pi,1 i k，使得q | Pi，所以q1=Pi。于是，由式可知?=q1，从而由式得到P2 Pk=cfe qi重复上述这一过程，得到k l, Pi qi,1 i k 证毕。7. 定理：假设设(n)为n的正约数的个数，(

5、n)为n的正约数之和，那么有1(n) ( i 1)( 2 A ( k 1)I,21/k 1 A2(n)P11 -P2_ _1P1 1P2 1Pk 18. 推论1使用式(2)中的记号，有(i ) n的正因约数d必有形式d = d pg2 Pkk, 1Z,0 i i,1 i k(ii) n的正倍数m必有形式m P/P22 PkkM,M N, i N, i i,1 i k9.推论2设正整数a与b的标准分解式是a12k.P1 P2Pk ， b11P1 P2kPk ，其中P1, P2, Pk是互不相同的素数，i， i1 i k都是非负整数,那么(a,b)11kP1 P2Pk， imin i ,i，1 i

6、 k，a,b11kP1 P2Pk ， imax i,i，1 i k。10.推论3设a，b，c，n是正整数，ab=cn，(a, b) = 1(5)那么存在正整数u，v，使得a =nnu， b = v， c =uv，(u,v) = 10证明 设c = p11 p21 pkk，其中P1, P2, , Pk是互不相同的素数，i 1i k是正整数。又设a Pi1 P22 Pkk, b pi1 P21 Pkk ,其中i, i 1 i k都是非负整数。由式 及推论2可知mi n i, i = 0 , i i = ni, 1 i k,因此，对于每个i 1 ik，等式i = n i， i = 0 与 i = 0

7、 ， i = n i有且只有一个成立。这就证明了推论。证毕。11.定理：对任意的正整数m及素数p，记号p |m表示p |m, p 1 | m，即p是m的标准分解中出现的p的幕.设n 1， p为素数，p p | n!，那么ap这里x表示不超过实数x p1 n时，那么吕p0，故上面和式中只有有限多个项非零.另一种表现形式:设p为任一素数，在n!中含p的最高乘方次数记为p n!，那么有:p n!证明：由于p是素数，所有n!中所含p的方次数等于n!的各个因数1,2,，n 所含p的方次数之总和。由性质10可知，在1,2,，n中，有-个p的倍数,pn有2p个p的倍数，有 3个p的倍数，当p n p 时，

8、pnm 1p吕0，所以命题成立。p另证：对于任意固定的素数p，以p k表示在k的标准分解式中的p的指数，那么pn! =p(1) p(2)祕 n).以nj表示p(1), p(2),，p(n)中等于j的个数，那么p n! =1 m 2 n? 3 g ，(2)显然，nj就是在1,2,n中满足pj a并且p十1 | a的整数a的个数，所以 由定理2有。肿。将上式代入式(2)，得到问)吧冷)2(罰制3(罰制-【制。r 1 p即式成立。证毕。二、重要方法证明某些特殊形式的数不是素数或给出其为素数的必要条件是初等数论 中较为根本的问题，其方法是应用各种分解技术如代数式的分解 ，指出所给 数的一个真因子常用分

9、解技术有：(1) 利用代数式分解如因式分解指出其一个真因子；(2) 应用数的分解例如算术根本定理，指出数的一个真因子；3运用反证法，假定其是素数，然后利用素数的性质推出矛盾.三、例题讲解 例1.证明：无穷数列10001,100010001,中没有素数.教材第13页例1证明：记 an 1000110001,(n2)，那么n个 1an 1 104108104(n °104n 1104 1对n分奇偶讨论:1当n为偶数时，设n 2k，那么an108k 1104 1108k 1 108 1108 1 104 188k8、k显然10J 是大于1的整数，当k 2时，巴厂啤 1是大于1的整数10 1

10、 10 1 10 1而当k 1时，a210001 13 137是合数.(2)当为奇数时，设n 2k 1 ,n an8k 410 14k 24k 210 1 10 1(102)2k11 (102)2k 1104 1102 1 102 1102 1102 1易知 竺 1,1都是大于1的整数102 1 102 1综上：命题获证；例2.证明：对任意整数n 1，数n4 4n不是素数.教材第13页例2证明：我们对n分奇偶讨论：(1) 当为偶数时，n4 4n大于2,且也为偶数，故结论显然成立.(2) 当为奇数时，设n 2k 1，那么4,n 4,2k 1n 4 n 4n4 4 (2k)4(n2 2 22k)2

11、 4n2 (2k)2(n2 2 22k)2 (2n2k)2(n2 2 22k 2n 2k)(n2 2 22k 2n 2k)由于n 1，所以n2 2 22 k 2n 2k,n2 2 22k 2n 2k都是大于1的整数，故n4 4n是合数.综上：n4 4n不是素数.例3.设正整数a, b, c,d满足ab cd，证明：a b c d不是素数证明一：是应用数的分解，指出abed的一个真因子.由ab ed，可设旦d m，其中m,n是互素的正整数e b n故 a mu, e nu，同理 d mv, e nv故abed mu nu mv nv (m n)(u v)是两个大于1的整数积，从而不是素数证明二：

12、由ab cd，得b竺，因此a b acd a cd竺a(a c)(aad)，因a b c d是整数.假设它是一个素数，设为p，那么由(a c)(a d) ap*，p |(ac)(a d)故 p|(a c)或 p|(a d)，不妨设,p|(ac)那么a cp，结合*式得：ad a，即d 0，这不可能，故结论成立；例4.设整数a,b, c, d满足a b c d0，且 a2 acc2 b2bd d2证明：ab cd不是素数.教材第18页习题3-4证明：此题运用反证法，设有满足题设的一组a,b,c,d，使得ab cd为素数, 将其记为p ab cd，于是a -cd带入条件得到：b2 2 2 2p(p

13、 2cd bc) (b c )(b bd d )由于p是素数，故p| (b2 c2)或者p| (b2 bd d2)i假设 p |(b2 c2)，那么由 b2 c2 ab ab 2ab 2(ab cd) 2p，推出2 2b c p，即 b2 c2 abcd，从.而 b | c(cd)，显然(b,c)1因为b2c2是素数故 b|(cd)，这与0c dcb矛盾.ii假设p|(b2bdd2)，那么由02 2b bd d 2(ab cd)2p知b2 bd d2p，故2 aac2 cb2 bdd2ab cd，进而得到2a acc(cd)ab, b2bdd(d c) ab，于是得到a| c(c d),b |

14、 d(c d)都成立，但又知(ab,cd) 1，故被c d a和例5.证明：假设整数a,b满足2a2 a 3b2 b，那么a b和2a 2b 1都是完全平 方数证明：关系式变形为(a b)(2a 2b 1) b2 1论证的第一个要点是证明整数a b与2a 2b 1 (a b,2a 2b 1) d .假设 d 1,那么d有素因子p，从而由1知p| b2,因p是素数，故p|b.结合p|(a b) 知p|a.再由p|(2a 2b 1)导出p|1，这不可能，故d 1，即a b与2a 2b 1互 素因此，由1得右端为1b2是一个完全平方数，故|a b|,|2a 2b 1|均 是完全平方数下面证明a b

15、0，我们运用反证法.假设有整数a,b满足问题中的等式，但a b 0 .因已证明| a b|是一个完全 平方数故有bar2，这里r 0 ；结合1丨推出r | b，再由b a r2得出r | a . 设b b|,a r，带入问题中的等式可得(注意r 0,厲r)訂 6* 3r2 1 0 2将上式视为关于 的二次方程，由求根公式解得a1 3r 6r2 1，因a1是整数， 故由上式知6r2 1是完全平方数.但易知一个完全平方数被3除得的余数只能为 0或1；而6r2 1被3除得余数为2,矛盾.(或者更直接地：由a12被3除得余数为0或1，故2左边被3除得的余数 是1或2;但2的右边为0,被3整除.矛盾.即

16、2对任何整数ai及r均不 成立)从而必须有a b 0，这就证明了此题的结论.注：1例6.写出n 51480的标准分解式，并求它的正约数的个数(n);解：我们有514802 2574022 1287023 6435 23 5 128723 5 3 42923 5 32 14323 32 5 11 13(n) ( 1 1)( 2 1卜( k 1) (3 1)(2 1)(1 1)(1 1)(1 1) 96例7.求最大的正整数k，使得10k |199!解：因为10 2 5,正整数k的最大值取决于199!的分解式中所含5的幕指由定理2, 199!的标准分解式中所含的5的幕指数是47r199199199丁

17、子I片所以，所求的最大整数是k 47 o例8.设x与y是实数，那么2x2y3 x x yy(*)设xx,01, yy,01，那么右边xx yy2x2?y(1)左边2x2y 2x2?y22 ,如果0，那么显然有22 ；如果1,那么与中至少有一个不小、于丄，于是2221o证法因此无论0或1,都有,由此及式(1)和式可以推出式(*)成立.证法二：注意到对任意整数k及任意实数k ,即上述不等式中x或y改变一个整数量，那么不等式(*)两边改变一个相同的量.故不等式(*)只 需证明0 x 1,0 y 1的情形即可.例9.一个经典的问题设m,n是非负整数，证明：(2m)!(2n)!是一个整数.m!n !(m

18、 n)!证明：我们只需证明：对每一个素数 p，分母m!n!(m n)!的标准分解中p的幕次，不超过分子(2m)!(2 n)!中p的幕次，由定理知等价于证明2m2nmllll 1ppl 1pnl pm nlp事实上我们能够证明一个更强的命题：设X与y是实数，那么2x2y 3 x xyy这就是例9讨论的问题. 结合知命题成立.例10.设a,b,c是整数，证明：(i )(a,b)a,b ab ;(ii)(ab,c)(a,b),(a,c)。解 为了表达方便，不妨假定a,b,c是正整数。apg2 PkP1S21 Pkkb，其中Pi, P2,Pk是互不相同的素数,i(1 i k)都是非负整数。由定理 1推论2，(a,b)a,bP11 P21 Pkk，Pl1 P21 Pkmin i, i，1 imax i, i， 1 ik，k。由此知(a,b)a, b=Pimin i, i max*pikPii 1i ab ;Pii，kP i，其中Pl, P2,，Pk是互不相同的素数,i, i, i(1 i k)都是非负整数。由定理有kk(a,b,c) Pii, (a,b),(a,c) Pii ,i 1i 1其中，对于(1 i k)，有i min i, max i, ，i maxmin i, , min i,