一个不小于 \(2\) 的整数是素数，当且仅当它没有除了 \(1\) 与自身以外的因子

素数最关键的性质是 \(p\mid ab=>p\mid a 或 p\mid b\)

算术基本定理：任意正整数 \(n>1\) 可以唯一写成素数的乘积，一般记作 \(n=p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}\)

素数的无穷性：设素数有限，为 \(p_1,p_2,...,p_k\) ，则 \(p_1p_2...p_k+1\) 可以分解成这些素数的乘积，但这些素数很明显不整除它，矛盾

有一些高等结论：

1. (Dirichlet定理) 对 \((a,b)=1\) ，存在无穷 \(an+b,n\ge 1\) 形式的素数

2. 存在任意长的素数等差数列

3. 存在无穷多对差不超过 \(270\) 的素数

Bertrand假设：对任意 \(n>3\) ，区间 \((n,2n-2)\) 存在素数

记 \(P_n\) 表示 \((n,2n)\) 的素数乘积， \(\pi(n)=\sum_{p<n} 1\) ，对 \(n>125\) 有 \(P_n>\frac{4^{\frac n3}}{(2n)^{\sqrt{\frac n2}}}\)

首先： \([1,2,...,n]<4^n\) ，给出 \(\prod\limits_{p\le n}p\le 4^{n-1}\) （更强的结论是小于 \(3^n\) ，需要精细的估计）

这个证明不难： \([1,2,...,2n+1]\mid [1,2,...,n]C_{2n+1}^n,[1,...,2n]\mid [1,...,2n-1]\)

回到原命题， \(A=C_{2n}^n=P_n\prod_{p\le n}p^{v_p(A)}\) 满足 \(A\ge \frac {4^n}{2n+1}\ge \frac{4^{n-1}}{2n}\) ，只需证：

\(\prod _{p\le n}p^{v_p(A)}\le (2n)^{\sqrt{\frac n2}-1}\cdot 4^{\frac {2n}3-1}\)

这里需要一个引理： \(\large p^{v_p(C_n^k)}\le n\) ，这是 \(Lucas\) 定理的直接推论

特别地，对于 \(\sqrt{2n}<p\le\frac {2n}{3}\) ， \(v_p(C_{2n}^n)\le 1\) ，而对 \(n\ge p> \frac {2n}3\) ，由 \(v_p(n!)=1,v_p(2n!)=2\) 知 \(p\nmid C_{2n}^n\)

从而 \(\prod\limits_{p\le n}p^{v_p(A)}\le \prod\limits_{p\le \sqrt{2n}}(2n)\cdot \prod\limits_{\sqrt {2n}<p\le \frac {2n}3} p\)

对 \(n\ge 125,[\sqrt{2n}]\ge 15\) ，而 \(1,9,15,4,6,8,...,2[\frac k2]\) 不是合数，从而 \(\pi(k)\le k-(2+[\frac k2])<\sqrt{\frac n2}-1\)

若不存在 \(p\in(n,2n-2)\) ，则 \(P_n\le 2n-1\) ，即 \(\frac{4^{\frac n3}}{(2n)^{\sqrt{\frac n2}}}<2n\) ，当 \(n\ge 125\) 不成立

实际上 \(P_n<(2n)^{\pi(2n)-\pi(n)}\) 可知 \(\pi(2n)-\pi(n)>\frac{\ln4}3\cdot \frac{n}{\ln2n}-\sqrt{\frac n2}\) ，可知当 \(n\) 充分大时， \((n,2n)\) 存在充分多的素数

更强的定理是 \(Sylvester-Schur\) 定理，表明 \(b>a\) 时， \(b,b+1,...,b+a-1\) 存在至少一个数最大素因子超过 \(a\) 。特别地，当 \(b\) 充分大，只会有一个数最大素因子不超过 \(a\) 。

CP1

素数相关的不定方程，关键是 \(p\mid ab=>p\mid a 或 p\mid b\)

素数条件经常采用直接设出给定量，因式分解等方法，应当注意在问题中刻意寻求因式分解，即使是 \(\frac{ab}c\) 型的，当 \(a,b>c\) 也是合数

例1

求所有素数对 \((p,q)\) ，使得 \(p-q\) 与 \(pq-q\) 都是完全平方数

记 \(p-q=a^2,q(p-1)=b^2\) ，则 \(q\mid p-1,q<p\)

又 \((q-1)p=(b+a)(b-a)\) ，若 \(p\le b-a\) 则 \(q-1<p<b+a\) ，矛盾！从而 \(p>b-a\) 并且 \(p\mid b+a\)

而 \(p-q=a^2\) 给出 \(a<\sqrt p\) ，\(q(p-1)=b^2\) 给出 \(p-1\ge b\) （因为 \(q\) 是素数， \(b\mid q\) ） ，从而 \(b+a<2p\) ，只能有 \(b+a=p\) ，进一步 \(b-a=q-1\)

那么 \(p,q\) 奇偶性不同，可知 \(p=3,q=2\)

例2

求所有素数 \(p\) 使得 \(p^2-p-1\) 是立方数

\(p=2\) 满足条件

设 \(p^2-p-1=x^3\) ，即 \(p(p-1)=(x+1)(x^2-x+1)\) （ \(p>2=>x>1\)）

若 \(p\mid x+1,p-1\le x<x^2-x+1\) ，矛盾！从而 \(p\mid x^2-x+1\)

接下来介绍两种有代表性的处理思路：

1. 记 \(x^2-x+1=np\) ，从而 \(p-1=n(x+1)\) ，则 \(x^2-x+1=n(n(x+1)+1)\) （ \(p\) 是素数，因此应当消去），则方程 \(x^2-(n^2+1)x-(n^2+n-1)=0\) 有整数解

那么 \(\triangle=(n^4+2n^2+1)+4n^2+4n-4=(n^2+3)^2+4n-12\) 是完全平方数，代入 \(n=1,2,3\) 验证可知 \(n=3\) 满足条件，给出解 \(x=11,p=37\) ，当 \(n\ge 4\) ，有 \((n^2+4)^2-(n^2+3)^2>4n-12\)

2. 可知 \(x+1\mid p-1\) ，设 \(p=n(x+1)+1\) ，\(n(x+1)+1\mid x^2-x+1\mid nx^2-nx+n\) ，从而 \(n(x+1)+1\mid x-3n-2\)

当 \(x\ge 2\) ，有 \(n(x+1)+1\ge 3n-x+2\) 以及 \(n(x+1)+1\ge x-3n-2\) ，从而 \(x=3n+2\) ，代入原方程解得 \(n=11,p=37\)

综上， \(p=2,37\) 是满足条件的所有解

例3

求一切正整数 \(m,n>1\) ，满足 \(n+1\) 是模 \(4\) 余 \(3\) 的素数，且存在素数 \(p\) 和非负整数 \(a\) 满足 \(\frac{m^{2^n-1}-1}{m-1}=m^n+p^a\)

\(n=2\) 给出平凡的解 \(p=m+1\) ，当 \(n\ge 3\) 时，改写为 \(\frac{m^{2^n-1}-1}{m-1}-m^n=p^a\) ，来寻求 \(LHS\) 的因式分解

首先， \(2^n-1\) 不是一个好的指数，我们将左式乘以 \(m\) ，得到 \(\frac{m^{2^n}-1}{m-1}-(m^n+1)\) ，一个关键的想法是令 \(n=2^k\cdot l,2\nmid l\) ，这样就有 \(m^{2^k}+1\mid \frac{m^{2^n}-1}{m-1}-(m^n+1)\) ，也即 \(p=m^{2^k}+1\)

（应当下意识的在这种一边纯素数的不定方程中寻找因子）

接下来可以借助阶分析，显然 \(\delta_p(m)=2^{k+1}\) ，从而 \(2^{k+1}\mid p-1\)

结合 \(m\equiv 2\:(mod~4)\) ，将最开始的方程模 \(4,8\) 分析，可以得到：

\(m^{2^n-2}+...+m^{n+1}+m^{n-1}+...+m^2+m+1\equiv m^2+m+1\equiv p^a\:(mod~8)\)

\(3\equiv m+1\equiv p^a\:(mod~4)\) ，只能有 \(k=0,p=m+1\) ，而 \((m+1)^a\equiv 1,m+1\:(mod~8)\) （注意奇数的平方模8余1），与 \(p^a\equiv m^2+m+1\:(mod~8)\) 矛盾

CP2

素数的无限性相关的问题

证明素数的无限性有很多方法，比如说费马数序列，序列 \(A_{n+1}=A_n^2-A_n\) 使得一项可以表达为前面全部项乘积加上一个常数，从而它们之间两两互素，给出无穷多素数

例1

设 \(P\) 是所有素数的集合， \(\empty \ne M\sub B\) ，满足对 \(M\) 的任意非空子集 \(\{p_1,p_2,...,p_k\}\) ， \(p_1p_2...p_k+1\) 的所有素因子属于 \(M\) ，求证： \(M=P\)

显然 \(M\) 是无限集，设素数 \(p\notin M\) ，将 \(M\) 中所有素数模 \(p\) 分类为 \(M_1,M_2,...,M_{p-1}\)

我们设 \(A=\{x\mid M_x 是无限集\},B=\overline{1,p-1}-A\) ，然后令 \(N=\prod\limits_{i\in B}\prod\limits_{p\in M_i}p\)

记 \(Q=\cup_{x\in A} M_x\)

我们记 \(A\) 中的元素通过乘能够得到的数（模 \(p\) 意义下）组成了集合 \(H\)，形式化地， \(H=\{x\mid \exist a_1,a_2,...,a_k\in Q,a_1a_2...a_k\equiv x\:(mod~p)\}\)

关键是 \(N\cdot p_1p_2...p_k+1\) 的所有素因子都是 \(Q\) 的（当然这里 \(p_1,p_2,...,p_k\) 也是来自 \(Q\) 的），这意味着 \(N\cdot p_1p_2...p_k+1\in Q\)

这里实际上建立了一个一一对应，可知 \(NQ+1=Q\) ，但 \(i^{p-1}\equiv 1\:(mod~p)\) 意味着 \(1\in Q\) ，从而 \(1\in NQ+1\) ，从而 \(0\in Q\) ，矛盾！

注：将 \(p_1p_2..p_k+1\) 改为 \(p_1p_2..p_k-1\) 也是可行的，需要条件 \(|M|\ge 3\) ，先证明 \(M\) 是无限集（稍复杂一些），再对 \(p_1,p_1p_2,...,p_1p_2...p_{p+1}\) 用抽屉原理得到 \(p_i...p_j\equiv 1\:(mod~p)\)

例2

给定序列 \(a_1=1,a_{n+1}=a_n^4-a_n^3+2a_n^2+1\) ，求证：有无穷个素数 \(p\) 不整除于该数列的任何一项

回忆数列 \(A_{n+1}=A_n^2-A_n+1\) 的处理手法，希望能将给出的递推公式变为乘积形式。对原始公式的分析是很难有效的，诸多的尝试可以给出：

\(a_{n+1}^2+1=(a_n^2+1)(a_n^6+4a_n^4-2a_n^3+2a_n^2+2)\)

下面假设 \(\{a_n\}\) 的素因子集合无限，进一步地，我们将证明 \(\{a_n^2+1\}\) 的素因子集合无限

关键是 \(a_{n+1}\equiv a_1\equiv 1\:(mod~a_n)\) ，从而 \(a_{n+2}\equiv a_2\:(mod ~a_n)\) ，归纳可得 \(a_n\mid a_{2n}\) ，进一步地， \(a_n\mid a_{kn},k=1,2,...\)

现在，若 \(p\mid a_t^2+1\) ，找到最小的 \(k\) 使得 \(kn>t\) ，有 \(p\mid a_t^2+1\mid a_{kn}^2+1\) 与 \(p\mid a_{kn}\) ，矛盾

设 \(a_i^2+1\) 的素因子集合是 \(P_i\) ，序列 \(\{P_1,P_2,...,\}\) 满足 \(P_i\sub P_{i+1}\) 且 \(P_i\sub S\) ， \(S\) 是有限集对任意 \(i\) 成立，从而当 \(n\ge N\) ，有 \(P_n=P_{n+1}\)

从而 \(n>N\) 时，\(a_n^6+4a_n^4-2a_n^3+2a_n^2+2=p_1^{\alpha_1}...p_k^{\alpha_k}\cdot 13^s\) ，并且 \(p_1p_2...p_k\mid a_n^2+1\)

那么 \(a_n^6+4a_n^4-2a_n^3+2a_n^2+2\equiv (-1)^3+4\cdot (-1)^2+2a_n-2+2\equiv 2a_n+3\:(mod~p_i)\)

然而 \(4a_n^2\equiv -4\ne 9\:(mod~p_i)\) ，从而 \(\alpha_i=0\) ，只能有 \(a_n^6+4a_n^4-2a_n^3+2a_n^2+2=13^s\)

当 \(2\mid n\) 时，我们有 \(3\mid a_n\) （因为 \(3\mid a_2\) ），两边模 \(3\) ，矛盾

本题的关键点是 \(a_n^2+1\) 的整除关系，并且读者对递推公式中常数项与 \(a_1\) 相同的问题应当立即意识到 \(a_{n+k}\) 与 \(a_k\) 的关系

CP3

有关素数及素数密度的估计，著名的不等式是：

Euler不等式

\(\prod\limits_{p\le n}\frac{p}{p-1}>1+\frac 12+\frac 13+...+\frac 1n\)

关键是 \(\large 1+\frac 1p+\frac 1{p^2}+...+\frac 1{p^N}=\frac{1-\frac{1}{p_i^{N+1}}}{1-\frac1{p_i}}<\frac 1{1-\frac 1{p_i}}=\frac {p_i}{p_i-1}\) （这个估计在 \(\sigma\) 函数的估计也经常用到）

则 \(\prod\limits_{p\le n}\frac{p}{p-1}>\prod\limits_{p\le n}(1+\frac 1{p_i}+\frac 1{p_i^2}+...+\frac 1{p_i^N})\)

展开得 \(\large \prod\limits_{p\le n}\frac{p}{p-1}>\sum\limits_{\alpha_1,\alpha_2,...\in\{1,2,...,N\}}\frac 1{p_1^{\alpha_1}p_2^{\alpha_2}...}\)

右边显然包含了 \(1+\frac 12+...+\frac 1n\)

它的推论是 \(\sum_{p\le n}\frac 1p\ge \ln \ln n-1\)

这利用了 \(\ln n<\prod\limits_{p\le n}\frac{p}{p-1}\le \prod e^{\frac 1{p-1}}=e^{\sum\frac 1{p-1}}\) ，并且显然 \(\sum(\frac 1{p-1}-\frac 1p)<1\)

我们有更强的结果来自 \(Mertens\) ，表明 \(a_n=\sum\limits_{p<n}\frac 1p-\ln\ln n\) 是有界数列，这基于 \(a_n=\sum\limits_{p<n}\frac {\ln p}p-\ln n\) 是有界的（ \((-6,4)\) 当然可以更精细）

因为 \(\ln n!=\sum\limits_{p\le n}v_p(n!)\ln n\) ，根据 \(\frac np-1<v_p(n!)<\frac n{p-1}\) 给出结果

然后考虑令 \(u_k=\frac {\ln k}k\text{ if k is prime}或0\) ，根据 \(S_k\) 的估计及 \(\sum\limits_{p\le n}\frac 1p=\sum S_k(\frac 1{\ln k}-\frac 1{\ln(k+1)})+\frac {S_n}{\ln n}\) 给出

此外，还有一开始就提到的 \(Bentrand\) 假设，也是常用的素数估计

我们知道 \(\lim\limits_{n\rightarrow \infty}\pi(n)/\frac n{\ln n}=1\)

这个结果比较困难，不过一些更弱的结果不是很难给出，比如

\(n^{\pi(2n)-\pi (n)}<\prod\limits_{n\le p\le 2n}p\le 4^n\)

对 \(n=2^k\) 知 \(k(\pi(2^{k+1})-\pi(2^k))\le 2^{k+1}\) ，累加可知 \(n\cdot \pi(2^n)<3\cdot 2^n\) ，直接给出对任意 \(n\) 有 \(n^{\pi(n)}\le 64^n\)

此外 \(n^{\pi(n)}\ge 2^{n-1}\) 因为 \(n^{\pi(n)}\ge [1,2,...,n]\)

根据上面两个结果给出 \(\frac n{\ln 2\ln n}<\pi(n)<6\ln 2\cdot \frac{n}{\ln n}\)

例1

求证：存在无穷个正整数 \(n\) ，对任意正整数 \(a,b\) 满足 \(a+b=n\) ，有 \(a,b\) 中一个的最大素因子超过 \(1394\)

设小于 \(1394\) 的所有素因子是 \(p_1,p_2,...,p_k\) ，我们声称：当 \(n\) 充分大时， \([1,n]\) 内所有可以表示为 \(p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}\) 的数量级不会达到 \(\sqrt n\) ，从而它们的和量级达不到 \(n\) ，完成证明

实际上，将每个数与 \((\alpha_1,\alpha_2,...,\alpha_k)\) 对应起来，对 \([1,2^N]\) 区间内的数， \(\alpha_1+\alpha_2+...+\alpha_k\le N\) ，因此这样的数组不超过 \(C_{N+k}^k\) （再补上一个 \(\alpha_{k+1}=N-\alpha_1-...\) 就是不定方程）

而 \(\lim\limits_{N\rightarrow\infty}\frac{(C_{N+k}^k)^2}{2^N}=0\) ，完成证明

例2

证明：存在常数 \(c\) 满足：若 \(a,b,n\) 是正整数，满足 \((a+i,b+j)>1,\forall i,j\in\{0,1,...,n\}\) ，则 \(\min\{a,b\}>c^n\cdot n^n\)

只需要考虑对每个 \((i,j)\) 作贡献的 \(p\) ，它的贡献至多是 \(\lceil \frac np\rceil^2\) ，并且对于 \(p>n\) 贡献至多是 \(1\) ，从而

\(\sum\limits_{p\le n}(\frac{n+p}p)^2+\sum\limits_{n<p\le n^2} 1=\sum\limits_{p\le n}(n^2\frac 1{p^2}+2n\frac1p+1)+\pi(n^2)-\pi(n)\)

当 \(n\) 充分大，这个数甚至小于 \(\frac 12 n^2\) ，由于 \(c\) 任取我们假设 \(n\) 充分大，所以说对某个 \(a+i\) ，至少一半的 \(b+j\) 与它的某个公素因子大于 \(n^2\) ，它们两两不同，给出 \(a+i>(n^2)^{\frac 12n}\) ，结论成立。

例3

证明：存在无穷多正整数 \(n\) 使得 \(n^2+1\) 无平方因子

方程 \(x^2+1\:(mod~p)\) 在模 \(p\) 意义下至多 \(2\) 个解，每个 \(p\) 至多对 \(2\lceil\frac np\rceil\) 个解，而

\(\sum\limits_{p\le \sqrt n} 2\lceil \frac np\rceil \le\pi(\sqrt n)+\sqrt n\ln\ln \sqrt n+C\sqrt n\)

于是完成了证明。