关于质和计算基本定理的问题
一、知识
大于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,b为整数.若p|ab，则a,b中至少有一个数被p整除. 事实上，若p不整除a和b，由性质2知，p与a和b均互素，从而p与ab互素。这与已知的p|ab矛盾.
特别地：若素数p整除an(n≥1)，则p|a
4.定理1 素数有无限多个 (公元前欧几里得给出证明)
证明：（反证法）假设只有k个素数，设它们是p1，p2， ，pk。记
N=p1p2 pw+1。（N不一定是素数）
由第一节定理2可知，p有素因数p，我们要说明p≠pi,1≤i≤k从而得出矛盾
事实上，若有某个i,1≤i≤k使得p≠pi,则由
p|N=p1p2 pw+1
推出p|1，这是不可能的。因此在p1，p2， ，pk之外又有一个素数p，这与假设是矛盾的。所以素数不可能是有限个。
5.引理1 任何大于1的正整数n可以写成素数之积，即
n=p1p2 pm (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, ql，使得d=q1,q2, ql，从而k+1=pq1,q2, ql。证毕。
6.定理2(算术基本定理)
任何大于1的整数n可以唯一地表示成
αkα1α2， (2) n=p1p2 pk
其中p1，p2， ，pk是素数，p1
αkα1α2我们称n=p1a1,a2, ,ak是n的标准分解式，其中pi,1≤i≤k是素数，p2 pk
p1
证明：由引理1，任何大于1的整数n可以表示成式(2)的形式，因此，证明表示式(2)的唯一性。
假设pi,1≤i≤k与qj,1≤j≤l都是素数，
p1
并且
n=p1p2 pk=q1q2 ql ， (4)
则由第三节定理4推论1，必有某个qj,1≤j≤l，使得p1|qi，所以p1=qi；又有某个pi,1≤i≤k，使得q1|pi，所以q1=pi。于是，由式(3)可知p1=q1，从而由式
(4)得到
p2 pk=q2 ql
重复上述这一过程，得到
k=l,pi=qi,1≤i≤k 证毕。
7.定理：若设τ(n)为n的正约数的个数，σ(n)为n的正约数之和，则有
（1）τ(n)=(α1+1)(α2+1) ⋅⋅⋅ (αk+1)
pkαk+1-1p1α1+1-1p2α2+1-1（2）σ(n)= ⋅ ⋅⋅⋅p1-1p2-1pk-1
8.推论1 使用式(2)中的记号，有
(ⅰ) n的正因（约）数d必有形式
γkγ1γ2d =d=p1p2 pk,γ1∈Z,0≤i≤αi,1≤i≤k
(ⅱ) n的正倍数m必有形式
βkβ2 m=p1β1p2 pkM,M∈N,βi∈N,βi≥αi,1≤i≤k
9.推论2 设正整数a与b的标准分解式是
βkα1α2β1β1ka=p1p2 pα
k，b=p1p2 pk，
其中p1, p2, , pk 是互不相同的素数，αi，βi（1 ≤ i ≤ k）都是非负整数，则
λkλ1λ1(a,b)=p1p2 pk，λi=min{αi,βi}，1≤i≤k，
μ1μ1μk[a,b]=p1p2 pk，μi=max{αi,βi}，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。
γkγ1γ1证明 设c =p1，其中p1, p2, , pk 是互不相同的素数，γi（1 ≤ p2 pk
i ≤ k）是正整数。又设
βkα1α2β1β1ka=p1p2 pα
k，b=p1p2 pk，
其中αI，βi（1 ≤ i ≤ k）都是非负整数。由式(5)及推论2 '可知
min{αi, βi} = 0，αi + βi = nγi，1 ≤ i ≤ k，
因此，对于每个i（1 ≤ i ≤ k），等式
αi = nγi ，βi = 0与αi = 0，βi = nγi
有且只有一个成立。这就证明了推论。证毕。
11.定理： 对任意的正整数m及素数p，记号pα||m表示pα|m,pα+1\|m，即pα是m的标准分解中出现的p的幂.
⎫⎡n⎤⎛⎡n⎤⎡n⎤设n>1，p为素数，p||n!，则ap=∑⎢l⎥ =⎢⎥+⎢2⎥+⋅⋅⋅⎪
l=1⎣p⎦⎝⎣p⎦⎣p⎦⎭αp∞
⎡n⎤这里[x]表示不超过实数x的最大整数.由于当pl>n时, 则⎢l⎥=0，故上面和
⎣p⎦
式中只有有限多个项非零.
另一种表现形式：
设p为任一素数，在n!中含p的最高乘方次数记为p(n!)，则有：
⎡n⎤⎡n⎤⎡n⎤p(n!)=⎢⎥+⎢2⎥+ +⎢m⎥(pm≤n
证明：由于p是素数，所有n!中所含p的方次数等于n!的各个因数1,2, ,n
⎡n⎤所含p的方次数之总和。由性质10可知，在1,2, ,n中，有⎢⎥个p的倍数，⎣p⎦
⎡n⎤⎡n⎤有⎢2⎥个p2的倍数，有⎢3⎥个p3的倍数， ，当pm≤n
⎡n⎤⎡n⎤⎢pm+1⎥=⎢pm+2⎥= =0，所以命题成立。 ⎣⎦⎣⎦
另证：对于任意固定的素数p，以p(k)表示在k的标准分解式中的p的指数，则
p(n!)=p(1)+p(2)+ p(n).
以nj表示p(1),p(2), ,p(n)中等于j的个数，那么
p(n!)=1⋅n1+2⋅n2+3⋅n3+ , (2)
|a的整数a的个数，所以 显然，nj就是在1,2, ,n中满足pj∣a并且pj + 1/
由定理2有
nj=[nn]-[]。 jj+1pp
将上式代入式(2)，得到
p(n!)=1([
=∑[
r=1∞n]-[n2])+2([n2]-[n3])+3([n3]-[n4])+ ppppppn]。rp
即式(1)成立。证毕。
二、重要方法
证明某些特殊形式的数不是素数（或给出其为素数的必要条件）是初等数论中较为基本的问题，其方法是应用各种分解技术（如代数式的分解），指出所给数的一个真因子
常用分解技术有：
（1）利用代数式分解（如因式分解）指出其一个真因子；
（2）应用数的分解（例如算术基本定理），指出数的一个真因子；
（3）运用反证法，假定其是素数，然后利用素数的性质推出矛盾.
三、例题讲解
例1.证明：无穷数列10001,100010001,⋅⋅⋅中没有素数. （教材第13页例1）
证明：记an=10001 10001,( n≥2)，则
n个1
an=1+10+10+⋅⋅⋅+10484(n-1)104n-1=4 10-1
对n分奇偶讨论：
108k-1108k-1108-1=⋅（1）当n为偶数时，设n=2k，则an=4 10-1108-1104-1
108-1108k-1(108)k-1=显然4是大于1的整数，当k≥2时，8是大于1的整数 10-110-1108-1
而当k=1时，a2=10001=13⨯137是合数.
(2) 当为奇数时，设n=2k+1， 108k+4-1104k+2+1104k+2-1(102)2k+1+1(102)2k+1-1=⋅=⋅ nan=104-1102+1102-1102+1102-1
(102)2k+1+1(102)2k+1-1,易知都是大于1的整数 102+1102-1
综上：命题获证；
例2.证明：对任意整数n>1，数n4+4n不是素数.（教材第13页例2）
证明：我们对n分奇偶讨论：
（1） 当为偶数时，n4+4n大于2，且也为偶数，故结论显然成立.
（2） 当为奇数时，设n=2k+1，则
n4+4n=n4+42k+1
=n4+4⋅(2k)4
=(n2+2⋅22k)2-4n2⋅(2k)2
=(n2+2⋅22k)2-(2n⋅2k)2
=(n2+2⋅22k+2n⋅2k)(n2+2⋅22k-2n⋅2k)
由于n>1，所以n2+2⋅22k+2n⋅2k,n2+2⋅22k-2n⋅2k都是大于1的整数， 故n4+4n是合数.
综上：n4+4n不是素数.
例3.设正整数a,b,c,d满足ab=cd，证明：a+b+c+d不是素数
证明一：本题不宜采用代数式的分解来产生所需的分解.我们的第一种解 是应用数的分解，指出a+b+c+d的一个真因子.
由ab=cd，可设adm==，其中m,n是互素的正整数. cbn
故a=mu,c=nu，同理d=mv,c=nv
故a+b+c+d=mu+nu+mv+nv=(m+n)(u+v)是两个大于1的整数
积，从而不是素数.
证明二：
由ab=cd，得b=a+b+c+d是整数. cdcd(a+c)(a+d)=，因此a+b+c+d=a+c+d+，因aaa
若它是一个素数，设为p，则由
(a+c)(a+d)=ap（*）|ac+()ad)+，p(
a+d≤a，故p|(a+c)或p|(a+d)，不妨设，p|(a+c)则a+c≥p，结合（*）式得：
即d≤0，这不可能，故结论成立;
例4.设整数a,b,c,d满足a>b>c>d>0，且a2+ac-c2=b2+bd-d2
证明：ab+cd不是素数. （教材第18页习题3-4）
证明：本题运用反证法，设有满足题设的一组a,b,c,d，使得ab+cd为素数，将其记为p=ab+cd，于是a=p-cd带入已知条件得到： b
p(p-2cd+bc)=(b2+c2)(b2+bd-d2)
由于p是素数，故p|(b2+c2)或者p|(b2+bd-d2)
（ⅰ）若p|(b2+c2)，则由b2+c2
故b|(c-d)，这与0
（ⅱ）若p|(b2+bd-d2)，则由0
a2+ac-c2=b2+bd-d2=ab+cd，
进而得到
a2+ac-c(c+d)=ab,b2+bd-d(d+c)=ab，
于是得到a|c(c+d),b|d(c+d)都成立，但又知(ab,cd)=1，故被c+da和b整除.
因0
例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）得右端为（1）b2是一个完全平方数，故|a-b|,|2a+2b+1|均是完全平方数.
下面证明a-b≥0，我们运用反证法.
假设有整数a,b满足问题中的等式，但a-b0；结合（1）推出r|b，再由b-a=r2得出r|a.设b=b1r,a=a1r，带入问题中的等式可得(注意r>0,b1=a1+r)
a12+6a1r+3r2+1=0 （2）
将上式视为关于a1的二次方程，
由求根公式解得a1=-3r±因a1是整数，
故由上式知6r2-1是完全平方数.但易知一个完全平方数被3除得的余数只能为0或1；而6r2-1被3除得余数为2，矛盾.
(或者更直接地：由a12被3除得余数为0或1，故（2）左边被3除得的余数
是1或2；但（2）的右边为0，被3整除.矛盾.即（2）对任何整数a1及r均不成立)
从而必须有a-b≥0，这就证明了本题的结论.
注：1.许多数论问题需证明一个正整数为1（例如，证明整数的最大公约数是1），由此我们常假设所说的数有一个素因子，利用素数的锐利性质（3）作进
一步论证，以导出矛盾.如例4
例6．写出n=51480的标准分解式，并求它的正约数的个数τ(n)；
解：我们有
51480 = 2⨯25740 = 22⨯12870 = 23⨯6435= 23⨯5⨯1287
= 23⨯5⨯3⨯429= 23⨯5⨯32⨯143 = 23⨯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的幂指数是
[199]+[199]+[199]+ =47 55253
所以，所求的最大整数是k=47。
3例8．设x与y是实数，则[2x] + [2y] ≥[x] + [x + y] + [y] (*)
证法一:
+α,0≤α≤1，y=[y]+β,0≤β≤1，则 设x=[x]
右边=[x] + [x + y] + [y]=2[x] +2?[y]+[α+β]， (1)
左边=[2x] + [2y] 2[=x] +2?[y]+[2α]+[2β] ， (2) 如果[α+β]=0，那么显然有[α+β]≤[2α]+[2β]；
如果[α+β]=1，那么α与β中至少有一个不小于，于是 1
2
[2α]+[2β]≥1=[α+β]。
因此无论[α+β]=0或1，都有[α+β]≤[2α]+[2β]，由此及式(1)和式(2)可以推出式(*)成立.
证法二:注意到对任意整数k及任意实数α，[k+α]=k+[α]，即上述不等式中x或y 改变一个整数量，则不等式(*)两边改变一个相同的量.故不等式(*)只需证明0≤x
+[2y] ≥[x +y] 于是问题等价于证明：[2x] 下面同证法一
例9．一个经典的问题
设m,n是非负整数，证明：(2m)!(2n)!是一个整数. m!n!(m+n)!证明:我们只需证明：对每一个素数p，分母m!n!(m+n)!的标准分解中p的幂次，不超过分子(2m)!(2n)!中p的幂次,由定理知等价于证明
⎛⎡2m⎤⎡2n⎤⎫∞⎛⎡m⎤⎡n⎤⎡m+n⎤⎫ ⎢l⎥+⎢l⎥⎪≥∑ ⎢l⎥+⎢l⎥+⎢l⎥⎪ ① ∑l=1⎝⎣p⎦⎣p⎦⎭l=1⎝⎣p⎦⎣p⎦⎣p⎦⎭∞
事实上我们能够证明一个更强的命题：
+ [2y] ³≥[x] + [x + y] + [y] ② 设x与y是实数，则[2x]
这就是例9讨论的问题.
结合①②知命题成立.
例10．设a,b,c是整数，证明：
(ⅰ) (a,b)[a,b]=ab；
(ⅱ) (a[b,c])=[(a,b),(a,c)]。 解 为了叙述方便，不妨假定a,b,c是正整数。 (ⅰ) 设
αkβkα1α2β1a=p1p2 pk，b=p1β1p2 pkb，
其中p1，p2， ，pk是互不相同的素数，αi,βi(1≤i≤k)都是非负整数。由定理1推论2 '，有
λkλ1(a,b)=p1λ1p2 pk，λi=min{αi,βi}，1≤i≤k， μkμ1μ1[a,b]=p1p2 pk，μi=max{αi,βi}，1≤i≤k。
由此知
(a,b)[a,b]=∏pi
i=1kλi+μi=∏pi=1kmin{αi,βi}+max{αi,βi}i=∏piαi+βi=ab； i=1k
(ⅱ) 设
a=∏pi，b=∏pi，c=∏piγi， αiβi
i=1i=1i=1kkk
其中p1，p2， ，pk是互不相同的素数，αi,βi,γi(1≤i≤k)都是非负整数。由定理有
(a,[b,c])=∏pi，[(a,b),(a,c)]=∏piμi， λi
i=1i=1kk
其中，对于(1≤i≤k)，有
λi =min{αi, max{βi,γi}}，
μi =max{min{αi,βi}, min{αi,γi}}，
不妨设βi≤γi，则
min{αi, βi}≤min{αi,?βi}，
所以
μi =min{αi, γi} =λi ，
即(a[b,c])=[(a,b),(a,c)]。
注：利用定理可以容易地处理许多像这样的问题。
引理：设整数k≥1，证明：
|a； (ⅰ) 若2k≤n
1≤b≤n，2b-1≠3k，则3k/|2b-1 (ⅱ) 若3k
证明:
(ⅰ) 若2k|a，则存在整数q，使得a=q⋅2k。显然q只可能是0或1。此
|a； 时a=0或2k这都是不可能的，所以2k/
(ⅱ) 若 3k|2b-1，则存在整数q，使得2b-1=q⋅3k，显然q只可能是0，
|2b-1。 1, 或2。此时2b-1，3k，或2⋅3k，这都是不可能的，所以3k/
推论3 设a，b，c，n是正整数，
ab = cn ，(a, b) = 1， (5) 则存在正整数u，v，使得
a = un，b = vn，c = uv，(u, v) = 1。
γkγ1γ1证明 设c =p1，其中p1, p2, , pk 是互不相同的素数，γi（1 ≤ p2 pk
i ≤ k）是正整数。又设
βkα1α2β1β1ka=p1p2 pα
k，b=p1p2 pk，
其中αI，βi（1 ≤ i ≤ k）都是非负整数。由式(5)及推论2 '可知
min{αi, βi} = 0，αi + βi = nγi，1 ≤ i ≤ k，
因此，对于每个i（1 ≤ i ≤ k），等式
αi = nγi ，βi = 0与αi = 0，βi = nγi
有且只有一个成立。这就证明了推论。证毕。
关于质和计算基本定理的问题
一、知识
大于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,b为整数.若p|ab，则a,b中至少有一个数被p整除. 事实上，若p不整除a和b，由性质2知，p与a和b均互素，从而p与ab互素。这与已知的p|ab矛盾.
特别地：若素数p整除an(n≥1)，则p|a
4.定理1 素数有无限多个 (公元前欧几里得给出证明)
证明：（反证法）假设只有k个素数，设它们是p1，p2， ，pk。记
N=p1p2 pw+1。（N不一定是素数）
由第一节定理2可知，p有素因数p，我们要说明p≠pi,1≤i≤k从而得出矛盾
事实上，若有某个i,1≤i≤k使得p≠pi,则由
p|N=p1p2 pw+1
推出p|1，这是不可能的。因此在p1，p2， ，pk之外又有一个素数p，这与假设是矛盾的。所以素数不可能是有限个。
5.引理1 任何大于1的正整数n可以写成素数之积，即
n=p1p2 pm (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, ql，使得d=q1,q2, ql，从而k+1=pq1,q2, ql。证毕。
6.定理2(算术基本定理)
任何大于1的整数n可以唯一地表示成
αkα1α2， (2) n=p1p2 pk
其中p1，p2， ，pk是素数，p1
αkα1α2我们称n=p1a1,a2, ,ak是n的标准分解式，其中pi,1≤i≤k是素数，p2 pk
p1
证明：由引理1，任何大于1的整数n可以表示成式(2)的形式，因此，证明表示式(2)的唯一性。
假设pi,1≤i≤k与qj,1≤j≤l都是素数，
p1
并且
n=p1p2 pk=q1q2 ql ， (4)
则由第三节定理4推论1，必有某个qj,1≤j≤l，使得p1|qi，所以p1=qi；又有某个pi,1≤i≤k，使得q1|pi，所以q1=pi。于是，由式(3)可知p1=q1，从而由式
(4)得到
p2 pk=q2 ql
重复上述这一过程，得到
k=l,pi=qi,1≤i≤k 证毕。
7.定理：若设τ(n)为n的正约数的个数，σ(n)为n的正约数之和，则有
（1）τ(n)=(α1+1)(α2+1) ⋅⋅⋅ (αk+1)
pkαk+1-1p1α1+1-1p2α2+1-1（2）σ(n)= ⋅ ⋅⋅⋅p1-1p2-1pk-1
8.推论1 使用式(2)中的记号，有
(ⅰ) n的正因（约）数d必有形式
γkγ1γ2d =d=p1p2 pk,γ1∈Z,0≤i≤αi,1≤i≤k
(ⅱ) n的正倍数m必有形式
βkβ2 m=p1β1p2 pkM,M∈N,βi∈N,βi≥αi,1≤i≤k
9.推论2 设正整数a与b的标准分解式是
βkα1α2β1β1ka=p1p2 pα
k，b=p1p2 pk，
其中p1, p2, , pk 是互不相同的素数，αi，βi（1 ≤ i ≤ k）都是非负整数，则
λkλ1λ1(a,b)=p1p2 pk，λi=min{αi,βi}，1≤i≤k，
μ1μ1μk[a,b]=p1p2 pk，μi=max{αi,βi}，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。
γkγ1γ1证明 设c =p1，其中p1, p2, , pk 是互不相同的素数，γi（1 ≤ p2 pk
i ≤ k）是正整数。又设
βkα1α2β1β1ka=p1p2 pα
k，b=p1p2 pk，
其中αI，βi（1 ≤ i ≤ k）都是非负整数。由式(5)及推论2 '可知
min{αi, βi} = 0，αi + βi = nγi，1 ≤ i ≤ k，
因此，对于每个i（1 ≤ i ≤ k），等式
αi = nγi ，βi = 0与αi = 0，βi = nγi
有且只有一个成立。这就证明了推论。证毕。
11.定理： 对任意的正整数m及素数p，记号pα||m表示pα|m,pα+1\|m，即pα是m的标准分解中出现的p的幂.
⎫⎡n⎤⎛⎡n⎤⎡n⎤设n>1，p为素数，p||n!，则ap=∑⎢l⎥ =⎢⎥+⎢2⎥+⋅⋅⋅⎪
l=1⎣p⎦⎝⎣p⎦⎣p⎦⎭αp∞
⎡n⎤这里[x]表示不超过实数x的最大整数.由于当pl>n时, 则⎢l⎥=0，故上面和
⎣p⎦
式中只有有限多个项非零.
另一种表现形式：
设p为任一素数，在n!中含p的最高乘方次数记为p(n!)，则有：
⎡n⎤⎡n⎤⎡n⎤p(n!)=⎢⎥+⎢2⎥+ +⎢m⎥(pm≤n
证明：由于p是素数，所有n!中所含p的方次数等于n!的各个因数1,2, ,n
⎡n⎤所含p的方次数之总和。由性质10可知，在1,2, ,n中，有⎢⎥个p的倍数，⎣p⎦
⎡n⎤⎡n⎤有⎢2⎥个p2的倍数，有⎢3⎥个p3的倍数， ，当pm≤n
⎡n⎤⎡n⎤⎢pm+1⎥=⎢pm+2⎥= =0，所以命题成立。 ⎣⎦⎣⎦
另证：对于任意固定的素数p，以p(k)表示在k的标准分解式中的p的指数，则
p(n!)=p(1)+p(2)+ p(n).
以nj表示p(1),p(2), ,p(n)中等于j的个数，那么
p(n!)=1⋅n1+2⋅n2+3⋅n3+ , (2)
|a的整数a的个数，所以 显然，nj就是在1,2, ,n中满足pj∣a并且pj + 1/
由定理2有
nj=[nn]-[]。 jj+1pp
将上式代入式(2)，得到
p(n!)=1([
=∑[
r=1∞n]-[n2])+2([n2]-[n3])+3([n3]-[n4])+ ppppppn]。rp
即式(1)成立。证毕。
二、重要方法
证明某些特殊形式的数不是素数（或给出其为素数的必要条件）是初等数论中较为基本的问题，其方法是应用各种分解技术（如代数式的分解），指出所给数的一个真因子
常用分解技术有：
（1）利用代数式分解（如因式分解）指出其一个真因子；
（2）应用数的分解（例如算术基本定理），指出数的一个真因子；
（3）运用反证法，假定其是素数，然后利用素数的性质推出矛盾.
三、例题讲解
例1.证明：无穷数列10001,100010001,⋅⋅⋅中没有素数. （教材第13页例1）
证明：记an=10001 10001,( n≥2)，则
n个1
an=1+10+10+⋅⋅⋅+10484(n-1)104n-1=4 10-1
对n分奇偶讨论：
108k-1108k-1108-1=⋅（1）当n为偶数时，设n=2k，则an=4 10-1108-1104-1
108-1108k-1(108)k-1=显然4是大于1的整数，当k≥2时，8是大于1的整数 10-110-1108-1
而当k=1时，a2=10001=13⨯137是合数.
(2) 当为奇数时，设n=2k+1， 108k+4-1104k+2+1104k+2-1(102)2k+1+1(102)2k+1-1=⋅=⋅ nan=104-1102+1102-1102+1102-1
(102)2k+1+1(102)2k+1-1,易知都是大于1的整数 102+1102-1
综上：命题获证；
例2.证明：对任意整数n>1，数n4+4n不是素数.（教材第13页例2）
证明：我们对n分奇偶讨论：
（1） 当为偶数时，n4+4n大于2，且也为偶数，故结论显然成立.
（2） 当为奇数时，设n=2k+1，则
n4+4n=n4+42k+1
=n4+4⋅(2k)4
=(n2+2⋅22k)2-4n2⋅(2k)2
=(n2+2⋅22k)2-(2n⋅2k)2
=(n2+2⋅22k+2n⋅2k)(n2+2⋅22k-2n⋅2k)
由于n>1，所以n2+2⋅22k+2n⋅2k,n2+2⋅22k-2n⋅2k都是大于1的整数， 故n4+4n是合数.
综上：n4+4n不是素数.
例3.设正整数a,b,c,d满足ab=cd，证明：a+b+c+d不是素数
证明一：本题不宜采用代数式的分解来产生所需的分解.我们的第一种解 是应用数的分解，指出a+b+c+d的一个真因子.
由ab=cd，可设adm==，其中m,n是互素的正整数. cbn
故a=mu,c=nu，同理d=mv,c=nv
故a+b+c+d=mu+nu+mv+nv=(m+n)(u+v)是两个大于1的整数
积，从而不是素数.
证明二：
由ab=cd，得b=a+b+c+d是整数. cdcd(a+c)(a+d)=，因此a+b+c+d=a+c+d+，因aaa
若它是一个素数，设为p，则由
(a+c)(a+d)=ap（*）|ac+()ad)+，p(
a+d≤a，故p|(a+c)或p|(a+d)，不妨设，p|(a+c)则a+c≥p，结合（*）式得：
即d≤0，这不可能，故结论成立;
例4.设整数a,b,c,d满足a>b>c>d>0，且a2+ac-c2=b2+bd-d2
证明：ab+cd不是素数. （教材第18页习题3-4）
证明：本题运用反证法，设有满足题设的一组a,b,c,d，使得ab+cd为素数，将其记为p=ab+cd，于是a=p-cd带入已知条件得到： b
p(p-2cd+bc)=(b2+c2)(b2+bd-d2)
由于p是素数，故p|(b2+c2)或者p|(b2+bd-d2)
（ⅰ）若p|(b2+c2)，则由b2+c2
故b|(c-d)，这与0
（ⅱ）若p|(b2+bd-d2)，则由0
a2+ac-c2=b2+bd-d2=ab+cd，
进而得到
a2+ac-c(c+d)=ab,b2+bd-d(d+c)=ab，
于是得到a|c(c+d),b|d(c+d)都成立，但又知(ab,cd)=1，故被c+da和b整除.
因0
例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）得右端为（1）b2是一个完全平方数，故|a-b|,|2a+2b+1|均是完全平方数.
下面证明a-b≥0，我们运用反证法.
假设有整数a,b满足问题中的等式，但a-b0；结合（1）推出r|b，再由b-a=r2得出r|a.设b=b1r,a=a1r，带入问题中的等式可得(注意r>0,b1=a1+r)
a12+6a1r+3r2+1=0 （2）
将上式视为关于a1的二次方程，
由求根公式解得a1=-3r±因a1是整数，
故由上式知6r2-1是完全平方数.但易知一个完全平方数被3除得的余数只能为0或1；而6r2-1被3除得余数为2，矛盾.
(或者更直接地：由a12被3除得余数为0或1，故（2）左边被3除得的余数
是1或2；但（2）的右边为0，被3整除.矛盾.即（2）对任何整数a1及r均不成立)
从而必须有a-b≥0，这就证明了本题的结论.
注：1.许多数论问题需证明一个正整数为1（例如，证明整数的最大公约数是1），由此我们常假设所说的数有一个素因子，利用素数的锐利性质（3）作进
一步论证，以导出矛盾.如例4
例6．写出n=51480的标准分解式，并求它的正约数的个数τ(n)；
解：我们有
51480 = 2⨯25740 = 22⨯12870 = 23⨯6435= 23⨯5⨯1287
= 23⨯5⨯3⨯429= 23⨯5⨯32⨯143 = 23⨯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的幂指数是
[199]+[199]+[199]+ =47 55253
所以，所求的最大整数是k=47。
3例8．设x与y是实数，则[2x] + [2y] ≥[x] + [x + y] + [y] (*)
证法一:
+α,0≤α≤1，y=[y]+β,0≤β≤1，则 设x=[x]
右边=[x] + [x + y] + [y]=2[x] +2?[y]+[α+β]， (1)
左边=[2x] + [2y] 2[=x] +2?[y]+[2α]+[2β] ， (2) 如果[α+β]=0，那么显然有[α+β]≤[2α]+[2β]；
如果[α+β]=1，那么α与β中至少有一个不小于，于是 1
2
[2α]+[2β]≥1=[α+β]。
因此无论[α+β]=0或1，都有[α+β]≤[2α]+[2β]，由此及式(1)和式(2)可以推出式(*)成立.
证法二:注意到对任意整数k及任意实数α，[k+α]=k+[α]，即上述不等式中x或y 改变一个整数量，则不等式(*)两边改变一个相同的量.故不等式(*)只需证明0≤x
+[2y] ≥[x +y] 于是问题等价于证明：[2x] 下面同证法一
例9．一个经典的问题
设m,n是非负整数，证明：(2m)!(2n)!是一个整数. m!n!(m+n)!证明:我们只需证明：对每一个素数p，分母m!n!(m+n)!的标准分解中p的幂次，不超过分子(2m)!(2n)!中p的幂次,由定理知等价于证明
⎛⎡2m⎤⎡2n⎤⎫∞⎛⎡m⎤⎡n⎤⎡m+n⎤⎫ ⎢l⎥+⎢l⎥⎪≥∑ ⎢l⎥+⎢l⎥+⎢l⎥⎪ ① ∑l=1⎝⎣p⎦⎣p⎦⎭l=1⎝⎣p⎦⎣p⎦⎣p⎦⎭∞
事实上我们能够证明一个更强的命题：
+ [2y] ³≥[x] + [x + y] + [y] ② 设x与y是实数，则[2x]
这就是例9讨论的问题.
结合①②知命题成立.
例10．设a,b,c是整数，证明：
(ⅰ) (a,b)[a,b]=ab；
(ⅱ) (a[b,c])=[(a,b),(a,c)]。 解 为了叙述方便，不妨假定a,b,c是正整数。 (ⅰ) 设
αkβkα1α2β1a=p1p2 pk，b=p1β1p2 pkb，
其中p1，p2， ，pk是互不相同的素数，αi,βi(1≤i≤k)都是非负整数。由定理1推论2 '，有
λkλ1(a,b)=p1λ1p2 pk，λi=min{αi,βi}，1≤i≤k， μkμ1μ1[a,b]=p1p2 pk，μi=max{αi,βi}，1≤i≤k。
由此知
(a,b)[a,b]=∏pi
i=1kλi+μi=∏pi=1kmin{αi,βi}+max{αi,βi}i=∏piαi+βi=ab； i=1k
(ⅱ) 设
a=∏pi，b=∏pi，c=∏piγi， αiβi
i=1i=1i=1kkk
其中p1，p2， ，pk是互不相同的素数，αi,βi,γi(1≤i≤k)都是非负整数。由定理有
(a,[b,c])=∏pi，[(a,b),(a,c)]=∏piμi， λi
i=1i=1kk
其中，对于(1≤i≤k)，有
λi =min{αi, max{βi,γi}}，
μi =max{min{αi,βi}, min{αi,γi}}，
不妨设βi≤γi，则
min{αi, βi}≤min{αi,?βi}，
所以
μi =min{αi, γi} =λi ，
即(a[b,c])=[(a,b),(a,c)]。
注：利用定理可以容易地处理许多像这样的问题。
引理：设整数k≥1，证明：
|a； (ⅰ) 若2k≤n
1≤b≤n，2b-1≠3k，则3k/|2b-1 (ⅱ) 若3k
证明:
(ⅰ) 若2k|a，则存在整数q，使得a=q⋅2k。显然q只可能是0或1。此
|a； 时a=0或2k这都是不可能的，所以2k/
(ⅱ) 若 3k|2b-1，则存在整数q，使得2b-1=q⋅3k，显然q只可能是0，
|2b-1。 1, 或2。此时2b-1，3k，或2⋅3k，这都是不可能的，所以3k/
推论3 设a，b，c，n是正整数，
ab = cn ，(a, b) = 1， (5) 则存在正整数u，v，使得
a = un，b = vn，c = uv，(u, v) = 1。
γkγ1γ1证明 设c =p1，其中p1, p2, , pk 是互不相同的素数，γi（1 ≤ p2 pk
i ≤ k）是正整数。又设
βkα1α2β1β1ka=p1p2 pα
k，b=p1p2 pk，
其中αI，βi（1 ≤ i ≤ k）都是非负整数。由式(5)及推论2 '可知
min{αi, βi} = 0，αi + βi = nγi，1 ≤ i ≤ k，
因此，对于每个i（1 ≤ i ≤ k），等式
αi = nγi ，βi = 0与αi = 0，βi = nγi
有且只有一个成立。这就证明了推论。证毕。