Jul 042012
 

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

\begin{equation}n<p<2n,\end{equation}

then

\begin{equation}{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,\end{equation}

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

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

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\).

Jun 262012
 

Sylvester’s theorem  the binomial coefficient

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

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\).

注意, 定理 \(2\) 已经隐含在 Ramanujan 给出的 Bertrand’s postulate 的证明中 Ramanujan’s proof of Bertrand’s postulate.

Jun 232012
 

二平方和

引理 \(1\)正整数 \(a, b\) 互质, \((a,b)=1, p>2\) 是质数,并且 \(p\bigm|(a^2+b^2)\), 则 \(p\equiv1\pmod4\).

证明  不难用二次剩余(Quadratic residue)来给出证明:

由 \(p\bigm|(a^2+b^2)\) 得

\begin{equation}a^2\equiv-b^2\pmod p,\end{equation}

故而

\begin{equation}(\frac{a^2}{p})= (\frac{-1}{p})(\frac{b^2}{p}).\end{equation}

这里 \((\frac{n}{p})\) 是 Legendre symbol. 由于  \((a,b)=1\), 因之 \((p,a)=(p,b)=1\), 于是

\begin{equation}(\frac{a^2}{p})=(\frac{b^2}{p})=1\end{equation}

成为事实, 所以必定有

\begin{equation}(\frac{-1}{p})=1.\end{equation}

换句话说, 我们已经得到了所要的 \(p\equiv1\pmod4\).

 

下面换一个办法, 可能是最简单的, 工具是 Fermat 小定理(Fermat’s little theorem

用反证法.

假定有正整数 \(k\) 使得 \(p=4k-1\), 由 \((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}).\]

一样是不可能的.

 

引理 \(1\) 虽然简单, 但是隐含了下面的事实:

引理 \(2\)    质数 \(p\equiv3\pmod4\), 并且 \(p\bigm|(a^2+b^2)\), 这里 \(a,b\) 是整数, 则 \(p\bigm|a,  p\bigm|b.\)

照样可以使用二次剩余来得到欲证的结果: 同样由 \((1)\), 我们又得出 \((2)\)! 注意 \( (\frac{-1}{p})=-1\), 所以

\begin{equation}(\frac{a^2}{p})= -(\frac{b^2}{p}).\end{equation}

这又迫使下面的等式成为事实:

\begin{equation}(\frac{a^2}{p})= (\frac{b^2}{p})=0.\end{equation}

这也就是 \(p\bigm|a,  p\bigm|b.\)

 

下面直接借用引理 \(1\) 来完成引理 \(2\) 的证明. 事实上, 记 \(d=(a,b)\)为 \(a,b\) 的最大公约数, 则有整数 \(a_1,b_1\) 使得 \(a=a_1d, b=b_1d\), 并且 \((a_1,b_1)=1\). 于是

\begin{equation}a^2+b^2=d^2(a_1^2+b_1^2). \end{equation}

由 \(p\bigm|(a^2+b^2)\), 得

\begin{equation}p\bigm|d^2(a_1^2+b_1^2).\end{equation}

根据引理 \(1\), 可以知道

\begin{equation}(p,a_1^2+b_1^2)=1,\end{equation}

于是

\begin{equation}p\bigm|d^2,\end{equation}

从而

\begin{equation}p\bigm|d.\end{equation}

我们得到了需要的 \(p\bigm|a,  p\bigm|b.\)

 

现在, 假定 \(n\) 是正整数, 并且有整数 \(a,b\), 使得 \(n=a^2+b^2\). 质数 \(p\equiv3\pmod4\), 并且 \(p\bigm|n\).  根据 \((7), (9), (10),\) \(n\) 的质因数分解式中的 \(p\) 全部出现在 \(d^2\) 的质因数分解式中,因此 \(n\) 的质因数分解式中 \(p\) 的指数等于 \(d^2\) 的质因数分解式中 \(p\) 的指数,是 \(d\) 的质因数分解式中 \(p\)  的指数的 \(2\) 倍, 当然是偶数, 故而有了引理 \(3\):

引理 \(3\)   正整数 \(n\) 是二平方和, 即有整数 \(a,b\), 使得 \(n=a^2+b^2\). 质数 \(p\equiv3\pmod4\), 并且 \(p\bigm|n\), 则 \(n\) 的质因数分解式中, \(p\) 的指数是偶数.

 

至此, 我们也就得出了下述的二平方和定理

正整数 \(n\)  能写成两个整数的平方和的充分必要条件是, 所有 \(n\) 的质因数分解式中形如 \(4k-1\) (\(k\) 为正整数)的质数的指数皆为偶数.

 

利用 \(\Bbb Z[i]\) 的唯一分解定理, 也可以证明引理 \(3\):

事实上, 假定 \(n\) 是正整数, 并且有 \(a,b\in\Bbb Z\), 使得 \(n=a^2+b^2\), 则

\begin{equation}n=(a+bi)(a-bi).\end{equation}

假定 \(a+bi\) 在 \(\Bbb Z[i]\) 中有分解式

\begin{equation}a+bi=(a_1+b_1i)(a_2+b_2i)\cdots(a_l+b_li),\end{equation}

\begin{equation}a-bi=(a_1-b_1i)(a_2-b_2i)\cdots(a_l-b_li),\end{equation}

于是

\begin{equation}n=(a_1^2+b_1^2)(a_2^2+b_2^2)\cdots(a_l^2+b_l^2).\end{equation}

若有 \(b_k=0(1\leq k \leq l)\), 则 \(a_k^2\) 即为\(\Bbb Z\) 中的平方数; 如果 \(b_k\neq0(1\leq k \leq l)\), 则 \(a_k^2+b_k^2\) 就是\(\Bbb Z\) 中的质数: 这是因为, 假若不是如此, 则有 \(\neq\pm1\) 的整数 \(s, t\) 使得 \(a_k^2+b_k^2=st\). 将 \(s, t\) 在 \(\Bbb Z[i]\) 中分解, 就得到了一种不同于 \((a_k+b_ki)(a_k-b_ki)\) 的, 是两个有理整数或三个以上质因数的积的分解式. 这与 \(\Bbb Z[i]\) 的唯一分解定理是矛盾的.

既然 \(a_k^2+b_k^2\) 是\(\Bbb Z\) 中的质数, 那么 \(a_k^2+b_k^2\) 要么是 \(2\), 要么 \(\equiv1\pmod4\), 肯定不是 \(p\). 至此已经知道, 在\(n\) 的质因数分解式中, \(p\) 的指数是偶数.

Jun 092012
 

Bertrand’s postulate states that if \(x\geq4\), then there always exists at least one prime \(p\) with\(x<p<2x-2\). A weaker but more elegant formulation is: for every \(x>1\) there is always at least one prime p such that \(x<p<2x\).

In 1919, Ramanujan used properties of  the  Gamma function to give a simple  proof  that  appeared as  a  paper “A proof of Bertrand’s postulate” in the  Journal of the Indian Mathematical Society \( 11: 181–182\).

Let’s begin with the  Chebyshev function :

The  first  Chebyshev  function \(\vartheta(x)\)  is defined with

\begin{equation}\vartheta(x)=\sum_{p\leqslant x}\log p,\end{equation}

The second Chebyshev function \(\psi(x)\) is given by

\begin{equation}\psi(x)=\sum_{i\geqslant 1}\vartheta(x^{\frac1i}),\end{equation}

so

\begin{equation}\log \left[x\right]!=\sum_{i\geqslant 1}\psi(\frac1ix) ,\end{equation}

where \(\left[x\right]\)denotes as usual the greatest integer \(\leqslant x\).

From \((2)\) we have

\begin{equation}\psi(x)-2\psi(\sqrt{x})=\vartheta(x)-\vartheta(x^\frac12)+\vartheta(x^\frac13)-\dotsb,\end{equation}

and from \((3)\)

\begin{equation}\log\left[x\right]!-2\log\left[\frac12x\right]!=\psi(x)-\psi(\frac12x)+\psi(\frac13x)-\dotsb .\end{equation}

Remembering  that \(\vartheta(x)\) and \(\psi(x)\) are steadily increasing functions, from \((4)\) and \((5)\) we get that

\begin{equation}\psi(x)-2\psi(\sqrt{x})\leqslant\vartheta(x)\leqslant\psi(x);\end{equation}

and

\begin{equation}\psi(x)-\psi(\frac12x)\leqslant \log \left[x\right]!-2\log \left[\frac12x\right]!\leqslant\psi(x)-\psi(\frac12x)+\psi(\frac13x). \end{equation}

But it is easy to see that

\begin{equation}\begin{split}\log \Gamma(x)-2\log \Gamma(\frac12x+\frac12)&\leqslant \log \left[x\right]!-2\log \left[\frac12x\right]!\\&\leqslant\log \Gamma(x+1)-2\log \Gamma(\frac12x+\frac12).\end{split}\end{equation}

Now using Stirling’s approximation we deduce from \((8)\) that

\begin{equation}\log \left[x\right]!-2\log \left[\frac12x\right]!<\frac34x, \text{if}  x>0;\end{equation}

and

\begin{equation}\log \left[x\right]!-2\log \left[\frac12x\right]!>\frac23x, \text{if}  x>300.\end{equation}

It follows from \((7)\), \((9)\) and  \((10)\) that

\begin{equation}\psi(x)-\psi(\frac12x)<\frac34x, \text{if}  x>0;\end{equation}

and

\begin{equation}\psi(x)-\psi(\frac12x)+\psi(\frac13x)>\frac23x, \text{if } x>300. \end{equation}

Now changing \(x\) to \(\frac12x\), \(\frac14x\), \(\frac18x\), \(\dotsc\) in \((11)\) and adding up all the results, we obtain

\begin{equation}\psi(x)<\frac32x,\text{if}  x>0.\end{equation}

Again we have

\begin{equation}\begin{split}\psi(x)-\psi(\frac12x)+\psi(\frac13x)&\leqslant\vartheta(x)+2\psi(\sqrt{x})-\vartheta(\frac12x)+\psi(\frac13x)\\&<\vartheta(x)-\vartheta(\frac12x)+\frac12x+3\sqrt{x},\end {split}\end{equation}

in virtue of  \((6)\) and \((13)\).

It  follow from \((12)\) and \((14)\) that

\begin{equation}\vartheta(x)-\vartheta(\frac{1}{2}x)>\frac{1}{6}x-3\sqrt{x}\text{, if }x>300.\end{equation}

But it is obvious that

\begin{equation}\frac16x-3\sqrt{x}\geqslant 0\text{, if } x\geqslant 324,\end{equation}

Hence

\begin{equation}\vartheta(2x)-\vartheta(x)>0, \text{if } x\geqslant162.\end{equation}

In other words there is at least one prime between \(x\) and \(2x\) if  \(x\geq162\). Thus Bertrand’s postulate is proved for all values of  \(x\) not less than \(162\); and, by actual verification, we find that it is true for smaller values.

 

It is obvious that

\begin{equation}\vartheta(x)-\vartheta(\frac12x)\leqslant(\pi(x)-\pi(\frac12x))\log x,\end{equation}

for all values of  \(x\). It follows from \((15)\) and \((18)\) that

\begin{equation}\pi(x)-\pi(\frac12x)>\frac1{\log x}(\frac16x-3\sqrt{x})\text{, if}  x>300.\end{equation}

From this we easily deduce that

\begin{equation}\pi(x)-\pi(\frac12x)\geqslant1,2,3,4,5,\dotsc\text{, if } x\geqslant2,11,17,29,41,\dotsc\end{equation}

respectively.

Jun 082012
 

第一个证明是哥德巴赫(Goldbach)给出的,这个证明涉及的所谓 Fermat 数总会使得人们联想起费尔马(Fermat)高斯(Gauss)

我们的目的是指出任意两个 Fermat 数 \(F_n=2^{2^n}+1, n=0,1,2,\dotsc\) 互质. 下述关系式足以

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

 

下面是Filip Saidak \(2005\) 年的证明, 发表在 “美国数学月刊” (Amer.Math.Monthly) \(2006\)年第\(113\)卷第\(10\)期\(937-938\):

任取不是 \(1\) 的自然数 \(m\), 由于 \(m\) 与 \(m+1\) 互质, 即 \((m,m+1)=1\), 于是

\begin{equation}a_1=m(m+1)\end{equation}

至少有 \(2\) 个不同的质因子.

同理, \((m(m+1),m(m+1)+1)=1\), 于是 \(m(m+1)\) 与 \(m(m+1)+1\) 有不同的质因子, 故而

\begin{equation}a_2=a_1(a_1+1)=m(m+1)(m(m+1)+1)\end{equation}

至少有 \(3\) 个不同的质因子.

很明显, 这个过程可以无限的继续下去, \(a_n=a_{n-1}(a_{n-1}+1)\), 于是 \(a_n\) 至少有 \(n+1\)个不同的质因子, 当然也就有 \(n+1\) 个不同的质数. \(n\) 可以是任意自然数, 因此也就有无限多个质数.

 

第三个证明Euler 的 \(\varphi\)  函数有关:

采用反证法.

假定只有有限个质数 \(p_1,p_2,\dotsc,p_l\), 考虑

\begin{equation}n=\prod_{i=1}^{l}p_i.\end{equation}

在所有不超过 \(n\) 的自然数中, 只有 \(1\) 与 \(n\) 是互质的, 其余的数都与 \(n\) 有共同的质因子, 于是

\begin{equation}\varphi(n)=1.\end{equation}

但是, 由 \(\varphi\) 的性质

\begin{equation}\varphi(n)=\prod_{i=1}^{l}(p_i-1)\end{equation}

不可能是 \(1\). 矛盾说明我们的假设不成立!

 

定义\(1\) 用 \(\Bbb P\) 表示全体质数所成的集合, 即

\begin{equation}\Bbb P := \{2,3,5,7,\dotsc\}.\end{equation}

定义\(2\)  \(x>0\), 命

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

为不大于 \(x\) 的质数个数.

 

与前面的途径不同, 下面这个证明是对 \(\pi(x)\) 进行估计, 直接讨论数量的多寡, 此乃解析数论(analytic number theory)常用.

设 \(x\) 是一个正整数, 记 \(\leqslant x\) 的质数是 \(p_1,p_2,\dotsc,p_{\pi(x)}\). 考察不超过 \(x\) 的正整数 \(n\). 由算术基本定理,

\(n\) 有下述的分解式

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

其中 \(\alpha_1,\alpha_2,\dotsc,\alpha_{\pi(x)}\) 是非负整数. 于是有正整数 \(u,v\) 使得

\begin{equation}n=u^2v,\end{equation}

其中 \(v\) 无平方因子, 即

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

这里每个 \(\beta_i\) 只能是 \(0\) 或 \(1\)(\(i=1,2,\dotsc,\pi(x)\)).

由 \(n\leqslant x\) 得 \(u\leqslant \sqrt x\), 所以 \(u\) 的种数 \(\leqslant \sqrt x\); 显而易见, \(v\) 的种数 \(\leqslant 2^{\pi(x)}\).

进而

\begin{equation}x\leqslant\sqrt{x}2^{\pi(x)},\end{equation}

这也就是

\begin{equation}\pi(x) \geqslant \frac{\log x}{\log 4},\end{equation}

所以

\begin{equation}\lim_{x\rightarrow\infty}\pi(x)=\infty.\end{equation}

 

把这个证明稍作修改, 就可以证明: \(\sum\limits_{p\in\Bbb P}\frac 1p\) 发散.

用反证法. 令 \(p_1,p_2,\dotsc\) 表示升序排列的质数. 假定相反的结论成立, 则存在一个 \(k\in\Bbb N^+\), 使得

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

于是, 只要 \(x>0\), 必定

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

用 \(N(x)\) 表示 \(<x\) 且其质因子都在\(p_1,p_2,\dotsc,p_k\) 中的那些正整数的个数. 与上个证明同理, 应该有

\begin{equation}N(x)\leqslant\sqrt{x}2^k.\end{equation}

另一方面, \(<x\) 且可被 \(p_l\) 整除的正整数的个数 \(\leqslant\frac x{p_l}(l=k+1,k+2,\dotsc)\), 故而

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

最后的不等式用到了 \((15)\). 结合 \((16)\), 可得

\[\sqrt{x}2^k\geqslant\frac x2\]

对任意 \(x>0\) 成立, 这显然不可能.

 

下一个证明, 从 matrix67的博客看到:

用反证法. 假定质数有限, 则对于任意正整数 \(n\), 有

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

这里 \(p\) 取遍所有质数. 注意

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

所以

\begin{equation}n!<(\prod p)^n.\end{equation}

但是, \(\prod\limits_{p\in\Bbb P}p\) 是一个常数, 当 \(n\) 足够大的时候, \((19)\) 不可能成立. 因之, 质数不可能有限.

 

接下来的的想法是普林斯顿大学(Applied and Computational Mathematics, Princeton University) 的 Dustin G. Mixon 发现的, 发表在 The American Mathematical Monthly, Vol.119, No.9 (November 2012), pp. 811
假定只有 \(l\) 个质数 \(p_1=2<p_2<\dotsb<p_l\), 选择正整数 \(N\) 使得 \(2^N>(N+1)^l\). 考察映射
\[\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=p_1^{\alpha_1}p_2^{\alpha_2}\dotsm p_l^{\alpha_l}\) 是 \(n\) 的质因数分解. 由

\[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\},\]

可见 \(\sigma\) 确是到 \(\{0,1,2,\dotsc,N\}^l\) 的映射. 再根据算术基本定理, \(\sigma\) 为单射, 但这显然是不可能的, 因为有抽屉原理(the pigeonhole principle)的存在. \(\Box\)

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 的证明]

Jun 072012
 

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), 结合了一些另外的技巧.

次日, Tao 在他的博客 之中, 写了一篇日志 描述了证明的大概轮廓.

这个事情最近上了新闻. 这是意料当中的情事! 这篇论文已提交学术刊物, 专家们正在审查. 英国《自然》杂志网站\(5\)月\(14\)日报道说, 陶哲轩在研究“弱哥德巴赫猜想”上取得突破, 有望最终解决这个世纪难题, 详细的报道在这个Mathematicians come closer to solving Goldbach’s weak conjecture.