一个显见的判定准则是

命题 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 算法可以确定性地判断某个整数是否一定是素数.
 

Lemma (Bezout) 对任意整数 $a,b$, 存在整数 $s,t$, 使得
\[
\text{gcd}(a,b)=sa+tb.
\]
即任何两个整数的最大公因子可由它们整线性表示.

Blankinship 方法

References:

W. Edwin Clark, Elementary Number Theory. Chapter 9

当 $x\geq 2$ 时,

\[0.2\frac{x}{\log x}\leqslant\pi(x)\leqslant 5\frac{x}{\log x}\]

这是闵嗣鹤、严士健编著的《初等数论》上的一个定理, 叫做切比雪夫不等式. 证明了 $\pi(x)$ 与 $\frac{x}{\log x}$ 是同阶的.

我们断言, 当 $n\geqslant 51$ 时, 有

\[\log 2\frac{x}{\log x}<\pi(x)+1\]