素数与合数

                     

贡献者： int256

　　 由定义可以立即得到推论。

　　 在定义了素数后我们可以引入一个定理。

　　 证明：$n$ 要么自己本身就是素数，否则 $n$ 就有大于 $1$ 且小于 $n$ 的因子。不失一般性的，考虑 $n$ 的大于 $1$ 且小于 $n$ 的最小因子 $a$，则 $a$ 要么是素数，要么 $a$ 是合数。对于 $a$ 是合数的时候，则必定存在 $1<l<a$ 使得 $l|a$，而 $a|m$，故 $l|m$（整除的传递性）。这使得 $l$ 是更小的一个 $n$ 的大于 $1$ 的因子，矛盾！故 $a$ 必定是素数。

　　 这指出，$n$ 要么本身就是素数，要么可以被一个小于 $n$ 的素数 $p_1$ 整除。而 $n/p_1$ 又是一个数，要么本身是素数，要么可以被一个小于 $n/p_1$ 的素数 $p_2$ 整除，依次类推...... 最终终将得到一个 $p_{m+1}=n/p_1/p_2/\cdots /p_m$ 是一个素数。这就使得 $n$ 可以表示为各个素数 $p_1,p_2,\dots ,p_{m+1}$ 的乘积。证毕。

　　 这个证明非常简单，考虑若有有限个素数，则存在一个最大的素数 $p$，取所有小于等于 $p$ 的素数的乘积 $q=2\times 3\times \cdots \times p$，则 $q+1$ 不是任何一个小于等于 $p$ 的素数的倍数，这说明 $q+1$ 是一个新的素数，故总可以根据已有的素数得到一个新的素数，这就说明有无限个素数。

　　 我们定义符号 $\pi (n)$ 表示小于等于 $n$ 的素数的个数。

　　 证明：假设对于 $n=1,2,\cdots ,N$ 有 $p_n<2^{2^n}$，则

也就有，$p_{N+1}<2^{2^{N+1}}+1$。由归纳法得到对于任意 $n$ 都有 $p_n<2^{2^n}$。

　　 而对于 $n\ge 4$ 的情况，考虑 $e^{e^{n-1}}<x\le e^{e^n}$，通过不等式的技巧可以得到 $e^{n-1}>2^n$ 且 $e^{e^{n-1}}>2^{2^n}$。从而 $\pi (x)\ge \pi (e^{e^{n-1}})\ge \pi (2^{2^n})\ge n$。故对于足够大的 $x$（$x>e^{e^3}$）有 $\pi (x)\ge \ln \ln x$。

　　 而对于 “不足够大” 的 $x$，可以证明不等式 $\pi (x)\ge \ln \ln x$ 都成立。证毕！

---

1. ^ 这里符号 $\mathbb{Z}$ 表示所有整数构成的集合。