# 开篇

Zsigmondy’s theorem states that if $$a>b>0$$ and $$n>1$$ are positive integers, then

1. $$a^n+b^n$$ has at least one prime factor that does not divide $$a^k+b^k$$ for all positive integers $$k<n$$, with the exception of $$2^3+1^3$$;
2. if $$(a,b)=1$$, then there is a prime number that divides $$a^n-b^n$$ and does not divide $$a^k-b^k$$ for all positive integer $$k<n$$ unless
•   $$a=2,b=1$$ and $$n=6$$; or
•   $$a+b$$ is a power of $$2$$ and $$n=2$$.

# 历史

Carmichael $$1913$$ 年的文章 $$[2]$$ 很值得一看, 他实际上证明了对 Lucas 序列(Lucas sequence)

$$U_n=\frac{a^n-b^n}{a-b},\,V_n=a^n+b^n$$

Artin 在研究线性群(linear group)的时候, 用初等办法建立了Zsigmondy定理的 $$2$$, 并且允许 $$a,b$$ 可以为负, 见 $$[3]$$.

# 准备工作

$$(a^m-b^m,\,a^n-b^n)=a^{(m,n)}-b^{(m,n)}$$

$$(2)$$ 虽然简单, 却从未在哪本书上见过. 数论书上只有当 $$b=1$$ 时的特殊情形, 所以这里算是一个推广. 至于证明, 可以归纳完成, 也可以选择 Bézout 恒等式(Bézout’s identity), 与 $$b=1$$ 没有本质不同.

$$a^r\equiv-1\pmod m$$

• 若 $$a^n\equiv-1\pmod m, n\in\Bbb N^+$$, 则 $$r|n;$$
• $$\delta_m(a)=\begin{cases}\;r,\quad m=2;\\2r, \quad m\geqslant3.\end{cases}$$

$a^n-b^n=(b+tp^\beta)^n-b^n=\sum_{i=1}^n{n\choose i}b^{n-i}(tp^\beta)^i.$

# 本原因子的定义与性质

$$W_n=a^n-b^n.$$

# $$2$$ 的初等证明

1. Geo. D. Birkhoff and H. S. Vandiver, On the Integral Divisors of $$a^n – b^n$$, The Annals of Mathematics, $$1904, 173-180$$.
2. Carmichael, On the Numerical Factors of  the Arithmetic Forms $$a^n \pm b^n$$, The Annals of Mathematics, $$1913, 30-70$$.
3. Artin, The orders of the linear groups, Communications on pure and applied mathematics, vol 7, $$1955, 355-366$$.

In 1949, Leo Moser gave a proof of  Bertrand’s postulate in the paper “A theorem of the distribution of primes”(American Mathematical Monthly,624-624,1949,vol56). Maybe this proof  is the simplest one among all proofs of  Bertrand’s postulate.

1. If $$n<p\leqslant 2n$$, then $$p$$ occurs exactly once in $${2n\choose n}$$;
2. If $$n\geqslant 3, \frac{2n}3<p<n$$, then $$p$$ doesn’t occurs in $${2n\choose n}$$;
3. If $$p^2>2n$$, then $$p$$ occurs at most once in $${2n\choose n}$$;
4. If $$2^\alpha\leqslant 2n<2^{\alpha+1}$$, then $$p$$ occurs at most $$\alpha$$ times in $${2n\choose n}$$.

If  $$2^\alpha<2n\leqslant 2^{\alpha+1}$$, suppose there is no prime $$p$$ with

$$n<p<2n,$$

then

$${2n\choose n}\leqslant{2a_1\choose a_1}{2a_2\choose a_2}\dotsm{2\choose 1}\bigg({2a_k\choose a_k}{2a_{k+1}\choose a_{k+1}}\dotsm{2\choose 1}\bigg)^\alpha,$$

where $$a_1=\big[\frac{n+1}3\big], k=\big[\frac{\alpha+1}2\big]$$, and $$a_i=\big[\frac{a_{i-1}+1}3\big]$$, for $$i=2,\,3,\,\dotsc\,.$$

By $$1,\,2,\,3$$ and $$(1)$$, every prime which appears on the left-hand side of $$(2)$$ appears also on the right; and those primes which appear with multiplicity greater than $$1$$ on the left appear on the right with multiplicity at least $$2\alpha+1$$, which by $$4$$ is at least equal to the multiplicity with which they appear on the left.

On the other hand, It is obvious that

$$2n>2a_1+2a_2+\dotsb+ 2+\alpha(2a_k+2a_{k+1}+\dotsb+2)$$

for $$n>2^{11}.$$ Hence the inequality in $$(2)$$ should be reversed. So for $$n>2^{11}$$, we have a contradiction which proves Bertrand’s postulate for these values of $$n$$.

Sylvester’s theorem  the binomial coefficient

$${n\choose k}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}$$

has a prime divisor $$p$$ greater than $$k$$. In other words, if $$n\geq 2k$$, then the product of  $$k$$ consecutive integers greater than $$k$$ is divisible by a prime greater than $$k$$. Note that for $$n=2k$$ we obtain precisely Bertrand’s postulate.

Theorem

1. if $$n>6$$ is an integer, then there always exists at least two prime numbers $$p$$, one  is the form $$4k+1$$ and the other $$4k+3$$, such that $$n<p<2n$$.
2. if $$k$$ is a positive  integer, then there always exists a positive  integer $$N$$ such that  for every  integer $$n>N$$,  there exist at least $$k$$ prime numbers $$p$$ such that $$n<p<2n$$.
• 对任意正整数 $$n>6$$ ,  至少存在一个 $$4k+1$$ 型和一个 $$4k+3$$  型素数 $$p$$  使得  $$n<p<2n$$.
• 对任意正整数 $$k$$,  存在正整数 $$N$$,  使得只要正整数 $$n>N$$,  就存在 $$k$$ 个素数 $$p$$ 使得 $$n<p<2n$$.

# 二平方和

$$a^2\equiv-b^2\pmod p,$$

$$(\frac{a^2}{p})= (\frac{-1}{p})(\frac{b^2}{p}).$$

$$(\frac{a^2}{p})=(\frac{b^2}{p})=1$$

$$(\frac{-1}{p})=1.$$

$(a^2)^{2k-1}\equiv(-b^2)^{2k-1}\pmod p,$

$a^{p-1}\equiv-b^{p-1}\pmod p.$

$$p\bigm|(a^2+b^2)$$, 注意到 $$(a^2+b^2)\bigm|(a^{p-1}+b^{p-1})$$(因为 $$p-1=2(2k-1)$$), 于是

$p\bigm|(a^{p-1}+b^{p-1}).$

$$(\frac{a^2}{p})= -(\frac{b^2}{p}).$$

$$(\frac{a^2}{p})= (\frac{b^2}{p})=0.$$

$$a^2+b^2=d^2(a_1^2+b_1^2).$$

$$p\bigm|d^2(a_1^2+b_1^2).$$

$$(p,a_1^2+b_1^2)=1,$$

$$p\bigm|d^2,$$

$$p\bigm|d.$$

$$n=(a+bi)(a-bi).$$

$$a+bi=(a_1+b_1i)(a_2+b_2i)\cdots(a_l+b_li),$$

$$a-bi=(a_1-b_1i)(a_2-b_2i)\cdots(a_l-b_li),$$

$$n=(a_1^2+b_1^2)(a_2^2+b_2^2)\cdots(a_l^2+b_l^2).$$

$$\prod_{i=0}^{n}F_i=F_{n+1}-2.$$

$$a_1=m(m+1)$$

$$a_2=a_1(a_1+1)=m(m+1)(m(m+1)+1)$$

$$n=\prod_{i=1}^{l}p_i.$$

$$\varphi(n)=1.$$

$$\varphi(n)=\prod_{i=1}^{l}(p_i-1)$$

$$\Bbb P := \{2,3,5,7,\dotsc\}.$$

$$\pi(x) := \#\{p\leq x|p\in\Bbb P \}$$

$$n$$ 有下述的分解式

$$n=\prod_{i=1}^{\pi(x)}p_i^{\alpha_i},$$

$$n=u^2v,$$

$$v=\prod_{i=1}^{\pi(x)}p_i^{\beta_i},$$

$$x\leqslant\sqrt{x}2^{\pi(x)},$$

$$\pi(x) \geqslant \frac{\log x}{\log 4},$$

$$\lim_{x\rightarrow\infty}\pi(x)=\infty.$$

$\sum_{i=k+1}^\infty\frac 1{p_i}\leqslant\frac 12.$

$$\sum_{i=k+1}^\infty\frac x{p_i}\leqslant\frac x2.$$

$$N(x)\leqslant\sqrt{x}2^k.$$

$N(x)\geqslant x-\sum_{p=k+1}^\infty\frac xp\geqslant\frac x2,$

$\sqrt{x}2^k\geqslant\frac x2$

$$n!=\prod p^{\sum\left[\frac n{p^i}\right]},$$

$$\sum_{i\geqslant1}\left[\frac n{p^i}\right]<\sum_{i\geqslant1}\frac n{p^i}=\frac{n}{p-1}\leqslant n,$$

$$n!<(\prod p)^n.$$

$\sigma:\{1,2,\dotsc,2^N\}\to\{0,1,2,\dotsc,N\}^l$

$n\mapsto\Big(\alpha_1,\alpha_2,\dotsc,\alpha_l\Big),$

$N\geqslant\log_2n = \sum_{i=1}^l \alpha_i\log_2p_i\geqslant\sum_{i=1}^l\alpha_i\geqslant \max\Big\{\alpha_1,\alpha_2,\dotsc,\alpha_l\Big\},$

Suppose there are a total of  $$N$$ primes, $$2=p_1<p_2<\dotsb<p_N$$, and pick $$K$$ such that $$2^K>(K+1)^N$$. Consider the mapping $$f:\{1,\dotsc,2^K\}\to\{0,\dotsc,K\}^N$$ defined by

$f(x):=(k_1,\dotsc,k_N),$

where $$x=p_1^{k_1}\dotsm p_N^{k_N}$$ is the prime factorization of $$x$$. Here, the fact that $$f(x)\in\{0,\dotsc,K\}^N$$ follows from

$K\geqslant\log_2x=\sum_{n=1}^Nk_n\log_2p_n\geqslant\sum_{n=1}^N k_n \geqslant \max\{k_1,\dotsc,k_N\}.$

Then $$f$$ is injective by the fundamental theorem of arithmetic, which contradicts the pigeonhole principle. $$\Box$$

[2012.10.14 收入Dustin G. Mixon 的证明]

Terence Tao(陶哲轩)$$1$$月$$31$$日, 提交了一篇论文 “Every odd number greater than 1 is the sum of at most five primes“. 这篇文章的主要结果, 正如标题展示的, 每个奇数可以表示为不超过$$5$$个质数之和. 显然, 这个结果和 Goldbach’s conjecture(哥德巴赫猜想)有关, 把奇数情形的哥德巴赫猜想, 即弱哥德巴赫猜想(Goldbach’s weak conjecture)推进了一步, 也改进了 Ramare 的结论: 每个偶数可以表示为不超过$$6$$个质数的和.

Tao 的论文, 有 $$44$$ 页, 这里是pdf . 所采用的工具, 是哈代和立特伍德所创造的圆法（Hardy–Littlewood circle method), 结合了一些另外的技巧.