证明 $n,n+2,n+4$ 中必有一个是 3 的倍数.

$n,n+6,n+12,n+18,n+24$ 中必有一个是 5 的倍数.

给定 $k$ 个数 $a_1 < a_2 < \cdots < a_k$, 如果对所有 $n$, 素数 $p$ 至少整除 $n+a_1$, $n+a_2$, $\ldots$, $n+a_k$ 中的一个, 则称 $p$ 是一个障碍(obstruction).

换句话说, 素数 $p$ 整除

\[
\mathcal{P}(n)=(n+a_1)(n+a_2)\cdots(n+a_k),\quad\forall\ n.
\]

此等价于 $a_1,a_2,\ldots,a_k(\text{mod}\ p)$ 包含模 $p$ 的所有剩余类.

【Def】如果这 $k$ 个数 $a_1 < a_2 < \cdots < a_k$, 没有一个素数是其障碍, 则称 $x+a_1,\ldots,x+a_k$ 是一个 admissible set of forms.

[注意] 由于 $a_1,a_2,\ldots,a_k(\text{mod}\ p)$ 顶多含有 $k$ 个模 $p$ 剩余类, 因此如果素数 $p>k$, 则它不可能成为这 $k$ 个数的障碍. 因此要检验含有 $k$ 个数的集合 $A$ 是否是 admissible 的, 我们只要对于 $p\leq k$, 找到一个剩余类  $b_p(\text{mod}\ p)$, 不包含 $A$ 中任一元素即可.

References:

Andrew Granville, Primes in intervals of bounded length.

Farey 序列是指集合

\[
\mathcal{F}_n=\{\frac{a}{b}\mid 0\leq a\leq b\leq n,\ (a,b)=1\}
\]

按从小到大顺序排列而得的一个分数序列. Farey 序列形如:

$\mathcal{F}_1$ 为

\[\frac{0}{1}\quad\frac{1}{1}\]

$\mathcal{F}_2$ 为

\[\frac{0}{1}\quad\frac{1}{2}\quad\frac{1}{1}\]

$\mathcal{F}_3$ 为

\[
\frac{0}{1}\quad\frac{1}{3}\quad\frac{1}{2}\quad\frac{2}{3}\quad\frac{1}{1}
\]

$\mathcal{F}_4$ 为

\[
\frac{0}{1}\quad\frac{1}{4}\quad\frac{1}{3}\quad\frac{1}{2}\quad\frac{2}{3}\quad\frac{3}{4}\quad\frac{1}{1}
\]

$\mathcal{F}_5$ 为

\[
\frac{0}{1}\quad\frac{1}{5}\quad\frac{1}{4}\quad\frac{1}{3}\quad\frac{2}{5}\quad\frac{1}{2}\quad\frac{3}{5}\quad\frac{2}{3}\quad\frac{3}{4}\quad\frac{4}{5}\quad\frac{1}{1}
\]

易见,

\[
\begin{array}{rcl}
\mathcal{F}_n&\rightarrow&\mathcal{F}_n\\
\frac{h}{k}&\mapsto&\frac{k-h}{k}
\end{array}
\]

是一一映射, 并将 $\mathcal{F}_n$ 中的元素进行了逆序排列.

如果不考虑 $\mathcal{F}_n$ 中的 0, 并把任何数 $\frac{a}{b}$ 的倒数也放在其中, 组成一个序列, 记为 $\mathcal{G}_n$, 则它们形如

$\mathcal{G}_1$ 为

\[\frac{1}{1}\]

$\mathcal{G}_2$ 为

\[\frac{1}{2}\quad\frac{1}{1}\quad\frac{2}{1}\]

$\mathcal{G}_3$ 为

\[
\frac{1}{3}\quad\frac{1}{2}\quad\frac{2}{3}\quad\frac{1}{1}\quad\frac{3}{2}\quad\frac{2}{1}\quad\frac{3}{1}
\]

$\mathcal{G}_4$ 为

\[
\frac{1}{4}\quad\frac{1}{3}\quad\frac{1}{2}\quad\frac{2}{3}\quad\frac{3}{4}\quad\frac{1}{1}\quad\frac{4}{3}\quad\frac{3}{2}\quad\frac{2}{1}\quad\frac{3}{1}\quad\frac{4}{1}
\]

$\mathcal{G}_5$ 为

\[
\frac{1}{5}\quad\frac{1}{4}\quad\frac{1}{3}\quad\frac{2}{5}\quad\frac{1}{2}\quad\frac{3}{5}\quad\frac{2}{3}\quad\frac{3}{4}\quad\frac{4}{5}\quad\frac{1}{1}\quad\frac{5}{4}\quad\frac{4}{3}\quad\frac{3}{2}\quad\frac{5}{3}\quad\frac{2}{1}\quad\frac{5}{2}\quad\frac{3}{1}\quad\frac{4}{1}\quad\frac{5}{1}
\]

证明:

(1) 如果 $\frac{a}{b}< \frac{c}{d}$ 是 Farey 序列中两个相邻的分数, 则有 $ad-bc=-1$. (逆命题不成立.)

(2) 如果 $\frac{a}{b}< \frac{x}{y}< \frac{c}{d}$ 是 Farey 序列中的三个相邻的分数, 则有

\[\frac{x}{y}=\frac{a+c}{b+d}\]

并且 (1) 和 (2) 是等价的.

(3) 若 $\frac{a}{b}< \frac{c}{d}$ 是 $\mathcal{F}_n$ 中相邻的两个分数, 则 $b+d>n$.

(4) 如果 $n>1$, 则 $\mathcal{F}_n$ 中不存在具有相同分母的两个相邻的项(既约分数).

(5) $\mathcal{F}_{n-1}\subset\mathcal{F}_n$, 并且多出的部分是下面的集合

\[\biggl\{\frac{k}{n}\biggl| 1\leq k\leq n-1,\quad (k,n)=1\biggr\}.\]

因此若记 $f(n)$ 为 $\mathcal{F}_n$ 所含元素的个数, 则 $f(n)=f(n-1)+\varphi(n)$, 其中 $\varphi(n)$ 指 1 到 $n$ 中与 $n$ 互素的正整数个数. 从而

\[f(n)=1+\sum_{k=1}^{n}\varphi(k).\]

若记 $g(n)$ 为 $\mathcal{G}_n$ 所含元素的个数, 则 $g(1)=1$, $g(2)=3$, $g(3)=7$, $g(4)=11$, $g(5)=19$. 求 $g(n)$ 的表达式.

References:

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. (《哈代数论》张明尧，张凡 译)

http://en.wikipedia.org/wiki/Farey_sequence

一个显见的判定准则是

命题 1([1]). 设 $c$ 是正实数, 令 $0\leq R_n < 1$ 是由带余除法定义的余数:

\[nc=\lfloor nc\rfloor+R_n.\]

则 $c$ 是无理数当且仅当 $R_n > 0$ 对所有 $n\in\mathbb{N}$ 成立.

Remark: W. Koepf 和 D. Schmersau 在[1]中利用这个最基本的判定准则给出了 e 为无理数的另一个直接证明. 并且其方法可以应用到一系列满足特定条件的形如 $a=\sum_{k=0}^{\infty}\frac{d_k}{k!}$ 的数上, 证明它们是无理数. 进而证明了 $\cosh 1=(e+e^{-1})/2$ 和 $\sinh 1=(e-e^{-1})/2$ 为无理数.

下面是比较难以理解的准则, 它们有多种形式, 但彼此等价.

命题 2([2]). 设 $\vartheta$ 是一实数, 则下面各条件等价.

(i) $\vartheta$ 是无理数.

(ii) 对任意 $\epsilon>0$, 存在有理数 $\frac{p}{q}$, 使得

\[0< \biggl|\vartheta-\frac{p}{q}\biggr|< \frac{\epsilon}{q}.\]

(iii) 对任意 $\epsilon>0$, 存在两个线性无关的双线性形式 $L_0, L_1$,

\[
L_0(X_0,X_1)=a_0X_0+b_0X_1,\quad L_1(X_0,X_1)=a_1X_0+b_1X_1,
\]

其中系数 $a_0,b_0,a_1,b_1$ 均为有理整数(rational integer, 即整数), 使得

\[\max\{|L_0(1,\vartheta)|,\ |L_1(1,\vartheta)|\}< \epsilon.\]

(iv) 对任意实数 $Q > 1$, 存在整数 $q$ ($1\leq q < Q$) 以及整数 $p$, 使得

\[
0 < \biggl|\vartheta-\frac{p}{q}\biggr|< \frac{1}{qQ}.
\]

(v) 存在无穷多的有理数 $\frac{p}{q}$, 使得

\[
\biggl|\vartheta-\frac{p}{q}\biggr| < \frac{1}{\sqrt{5}q^2}.
\]

(vi) 存在无穷多的有理数 $\frac{p}{q}$, 使得

\[
\biggl|\vartheta-\frac{p}{q}\biggr| < \frac{1}{q^2}.
\]

Def(好的有理数逼近) 对于数 $\beta$, 如果存在有理数 $\frac{p}{q}$, 使得

\[\biggl|\beta-\frac{p}{q}\biggr|<\frac{1}{q^2}\]

则称 $\beta$ 有好的有理数逼近(good rational approximations).

(vi) 比 (v) 弱, 但还是和其他所有的断言都等价. (vi) 说的就是, 如果数 $\beta$ 存在无穷多的好的有理数逼近, 则 $\beta$ 必定是无理数.

References:

[1] Wolfram Koepf, Dieter Schmersau, Irrationality of certain infinite series, Analysis 30, 27–34 (2010) / DOI 10.1524/anly.2010.0933

[2] Michel Waldschmidt, Criteria for irrationality, linear independence, transcendence and algebraic independence [PDF]

1. 设 $a$ 和 $b > 2$ 是正整数, 证明 $2^b-1\nmid 2^a+1$.

2. 若 $2^n+1=xy$, 这里 $x,y$ 是大于 1 的两个整数, 且 $n > 0$. 证明 $2^a\mid(x-1)\Leftrightarrow 2^a\mid(y-1)$.

3. 若 $2^n+1$ 是素数, 则 $n=2^m$.

4. 若 $2^n-1$ 是素数, 则 $n$ 自身一定是一个素数.

5. $2^n-1$ 的素因子个数少于 $n$ 个.

References:

Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery, An Introduction to the theory of numbers. (fifth edition), by John Wiley & Sons, Inc.

求 $\text{gcd}(2^n+1,2^m+1)$, where $n > m$.

类似的, 讨论

$\text{gcd}(2^n\pm 1,2^m\pm 1)$, where $n > m$.

Example:

$\text{gcd}(2^6+1,2^2+1)=5$.

注意有这样一个引理

Lemma: 设 $a,b\in\mathbb{Z}^+$, $x\in\mathbb{Z}$, 则有

\[
\text{gcd}(x^a-1,x^b-1)=\Bigl|x^{\text{gcd}(a,b)}-1\Bigr|.
\]

(1) $(n-1)!$ 不能被 $n$ 整除, 这样的 $n$ 是什么?

(2) $(n-1)!$ 不能被 $n^2$ 整除, 这样的 $n$ 是什么?

Wilson 定理:

一个正整数 $n$ ($n > 1$) 是素数的充要条件是 $n$ 满足 $(n-1)!\equiv -1\ (\text{mod}\ n)$.

即: $p$ 是素数当且仅当 $p$ 能整除 $(p-1)!+1$.

如果 $p$ 不是素数, 则 $p\mid (p-1)!$.

定理(Euclid). 如果 $2^p-1$ 是素数, 则 $2^{p-1}(2^p-1)$ 是一个完全数.

在 Euclid 给出此定理的 2000 年后, Leonhard Euler 证明了此定理的逆命题, 即,

定理(Euler). 每个偶完全数均形如 $2^{n-1}(2^n-1)$. 这里 $2^n-1$ 是素数.

Open question:

是否存在奇完全数?

设 $f(N)$ 满足下面的递推公式

\[
f(N)=\frac{2}{N}\Bigl[\sum_{j=0}^{N-1}f(j)\Bigr]+cN,
\]

其中 $c$ 是某个常数, 且已知 $f(0)=f(1)=0$, 求 $f(N)$ 的表达式.

在数据结构中会用到这个公式

Claim: $\binom{n}{k}\equiv 0 (\mod n)$ 对所有 $0 < k < n$ 成立当且仅当 $n$ 是素数.

利用此性质, Fermat 小定理及二项式展开, 容易证明:

定理: 设 $n\geqslant 2$, $0 < a < n$, 且 $a$ 与 $n$ 互素, 则

\[
n \mbox{是素数}\Leftrightarrow (x+a)^n\equiv x^n +a \pmod n
\]


(注意: 这里, $x$ 是一个自由的变量, 它不能用数去代入, 而必须将多项式展开, 并比较系数.)

Remark:

这个定理是 AKS 算法所依赖的定理. AKS 算法可以确定性地判断某个整数是否一定是素数.