Question

试证不超过费马数Fn的质数至少有n+1个，因此质数有无穷多个。 请各位帮帮忙！回答的好的话我会追加分。

Answer 1

F[n]=2^(2^n)+1,F[0]=3,F[1]=5,F[2]=17
记p[n]为第n个质数,p[1]=2,p[2]=3,p[3]=5
因此p[1]<F[0],p[2]<F[1],p[3]<F[2].

猜想p[n]<F[n-1]
现用归纳法证明;
(1)当n=1时,p[1]<F[0]成立
(2)假设当n≤k也成立,即p[1]<F[0]，p[2]<F[1],...,p[k]<F[k-1]
数q=p[1]*p[2]*...*p[k]+1的质因子不可能含有p[1]到p[k]中的任意一个(因为假设含有p[m],则p[1]*p[2]*...*p[k]+1=ap[m]<=>p[m](a-b)=1，由于p[m]≥2，所以这是不可能的),从而q的质因子(若q为质数,则其质因子为其本身)比p[k]要大,所以第k+1个质数不大于q的质因子,从而也不大于q
从而p[k+1]≤p[1]*p[2]*...*p[k]+1，由归纳假设有
p[k+1]<F[0]*F[1]*..*F[k-1]+1
=(2-1)(2+1)*(2^2+1)*...*(2^(2^(k-1))+1)+1
=2^(2^k)-1+1
=F[k]-1
<F[k]
即n=k+1也成立
综合(1)(2)知命题成立
所以p[n+1]<F[n]
即不超过F[n]的质数至少有n+1个

Answer 2

证明质数无穷很简单，反证法，假设有限 2 3 5 7--x是有限个质数 构造数p：2*3*5---*x+1 如果p是质数 则假设不成立，如果p是合数 则p有素因数q 不同于全部已知素数，假设也不成立，所以素数无穷个