考虑如下无限矩阵, 每一行都是等差数列, 公差依次是 3,5,7,9,11,...
\begin{matrix} 4&7&10&13&16&\cdots\\ 7&12&17&22&27&\cdots\\ 10&17&24&31&38&\cdots\\ 13&22&31&40&49&\cdots\\ 16&27&38&49&60&\cdots\\ \vdots&\vdots&\vdots&\vdots&\vdots& \end{matrix} 证明 $2n+1$ 是素数当且仅当 $n$ 不在上面的矩阵中.

• 设 $\{p_i\}_{i\geq 1}$ 是一递增素数列. 则对每个 $i$, 有 $p_{i+1}\leq 2p_i$.
• 任给素数 $p$, 总存在一个素数 $q$ 使得 $p < q < p^2$.

 

特别的, 当 $p_i > 3$, 根据 Bertrand 假设(见问题661), $(p_{i},2p_i-2)$ 之间至少存在一个素数, 因此 $p_{i+1} < 2p_i$.

也就是说, 满足 $p_{n+1}=2p_n-1$ 的只有两个例子:

\[
2\times 2-1= 3 =p_2,\quad 2\times 3-1= 5 =p_3.
\]

1845年, Bertrand 给出了这个猜测, 5 年后, 也就是1850年, Tchebycheff 给出了证明. 参见

G.H.Hardy and E.M.Wright, An Introduction to the Theory of Numbers. Oxford Science Publications, 5th edition (1979). pp.343-344.

$d_n$ 成周期分布, 可以证明存在递推关系. 周期为r \[ \prod_{\text{prime } k \leq p}(k-1). \]

$d_n$ 的周期为 (2-1)(3-1)(5-1)(7-1)(11-1)=480. 周期的构成为:

4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 14 4 6 2 10 2 6 6 4 2 4 6 2 10 2 4 2 12 10 2 4 2 4 6 2 6 4 6 6 6 2 6 4 2 6 4 6 8 4 2 4 6 8 6 10 2 4 6 2 6 6 4 2 4 6 2 6 4 2 6 10 2 10 2 4 2 4 6 8 4 2 4 12 2 6 4 2 6 4 6 12 2 4 2 4 8 6 4 6 2 4 6 2 6 10 2 4 6 2 6 4 2 4 2 10 2 10 2 4 6 6 2 6 6 4 6 6 2 6 4 2 6 4 6 8 4 2 6 4 8 6 4 6 2 4 6 8 6 4 2 10 2 6 4 2 4 2 10 2 10 2 4 2 4 8 6 4 2 4 6 6 2 6 4 8 4 6 8 4 2 4 2 4 8 6 4 6 6 6 2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10 2 6 4 6 2 6 4 2 4 6 6 8 4 2 6 10 8 4 2 4 2 4 8 10 6 2 4 8 6 6 4 2 4 6 2 6 4 6 2 10 2 10 2 4 2 4 6 2 6 4 2 4 6 6 2 6 6 6 4 6 8 4 2 4 2 4 8 6 4 8 4 6 2 6 6 4 2 4 6 8 4 2 4 2 10 2 10 2 4 2 4 6 2 10 2 4 6 8 6 4 2 6 4 6 8 4 6 2 4 8 6 4 6 2 4 6 2 6 6 4 6 6 2 6 6 4 2 10 2 10 2 4 2 4 6 2 6 4 2 10 6 2 6 4 2 6 4 6 8 4 2 4 2 12 6 4 6 2 4 6 2 12 4 2 4 8 6 4 2 4 2 10 2 10 6 2 4 6 2 6 4 2 4 6 6 2 6 4 2 10 6 8 6 4 2 4 8 6 4 6 2 4 6 2 6 6 6 4 6 2 6 4 2 4 2 10 12 2 4 2 10 2 6 4 2 4 6 6 2 10 2 6 4 14 4 2 4 2 4 8 6 4 6 2 4 6 2 6 6 4 2 4 6 2 6 4 2 4 12 2 12

$d_n$ 成周期分布: 每个周期是 (2-1)(3-1)(5-1)(7-1)=48 个数, 具体为

2 4 2 4 6 2 6 4 2 4 6 6 2 6 4 2 6 4 6 8 4 2 4 2 4 8 6 4 6 2 4 6 2 6 6 4 2 4 6 2 6 4 2 4 2 10 2 10

$u_n$:
7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97,101
$d_n$:
4 2 4 2 4 6 2 6 | 4 2 4 2 4 6 2 6 | 4 2 4 2 4 6 2 6 | 4 ...

\[ \begin{cases} u_{2k+1}=u_{2k}+4,\\ u_{2k}=u_{2k-1}+2, \end{cases} \] 其中 $k=1,2,\ldots,$

设 $m$ 是大于 1 的整数, $(a,m)=1$(即$a$与$m$互素), 则有 \[ a^{\varphi(m)}\equiv 1(\text{mod}\ m) \]