Content

Euclid’s theorem

There are infinitely many prime numbers.

Euclid’s proof

假设一个有限的素数集合

$$P=\{p_1,p_2,p_3,\ldots,p_n\}$$

令 $A=p_1p_2p_3\ldots p_n+1$，由算术基本定理可知存在素数集合

$$Q=\{q_1,q_2,\ldots,q_r\}$$

使得

$$A=q_1^{k_1}q_2^{k_2}\ldots q_r^{k_r}$$

假如 $A$ 是素数那么证明完毕；假如 $A$ 是合数，可以断言至少存在一个素因子 $q_i\not\in P$；否则，假设

$$\forall q_i\in Q\to q_i\in P$$

那么取任意一个 $q\in Q$，

$$\begin{aligned} &q\mid q_1^{k_1}q_2^{k_2}\ldots q_r^{k_r}\implies q\mid A\\ &q\mid p_1p_2p_3\ldots p_n\implies q\mid A-1 \end{aligned}\bigg\}\implies q\mid 1$$

但 $1$ 不是素数，这与 $q$ 是素数矛盾。因此总能通过构造整数 $A$ 找到一个新的素数 $q$，即存在无穷多个素数。

Primes $3\pmod 4$ Theorem

There are infinitely many prime numbers are congruent to $3$ modulo $4$.

证明过程与上面的类似，区别在于

1. 从素数列表中排除 $3$
2. 构造 $A=4p_1p_2\ldots p_n+3=q_1^{k_1}q_2^{k_2}\ldots q_r^{k_r}$
3. 利用 $q_i\equiv 1\pmod 4\implies q_1^{k_1}q_2^{k_2}\ldots q_r^{k_r}\equiv1\pmod 4$ 的逆否命题

但是这个方法不能用在 无穷多个素数模 $4$ 和 $1$ 同余 的证明上，因为 $q_i\equiv 3\pmod 4\implies q_i^{k_i}\equiv 1\text{ or }3\pmod 4$.

Dirichlet’s Theorem on Primes in Arithmetic Progressions

Let $a$ and $m$ be integers with $\gcd(a,m)=1$. Then there are infinitely many primes that are congruent to $a$ modulo $m$. That is, there are infinitely many prime numbers satisfying

$$p\equiv a\pmod m$$

Mersenne Primes

根据等比数列的求和公式

$$1+x+x^2+\ldots+x^{n-1}=\frac{x^n-1}{x-1}$$ $$x^n-1=(x-1)(x^{n-1}+x^{n-2}+\ldots+x+1)$$

考察形如 $x^n-1$ 的素数可以作出以下推断：

第一， $x=2$，否则 $x-1\ge 2$ 整除 $x^n-1$。

第二， $n$ 必须是素数。否则令 $n=ab\text{, } a\ge 2\text{, }b\gt2$，

$$2^{ab}-1=(2^a)^b-1=(2^a-1)((2^a)^{b-1}+(2^a)^{b-2}+\ldots+2^a+1)$$

这表示 $2^a-1$ 整除 $2^{ab}-1$。第二点表示如果 $n$ 是合数，$2^n-1$ 也是合数。从命题逻辑的逆否命题出发，换句话说，假如 $2^p-1$ 是一个素数，那么 $p$ 也是素数；“$p$ 是素数”是“$2^p-1$ 是素数”的必要条件，而不是充分条件。形如 $2^p-1$ 的素数称为梅森素数。

Perfect number

A perfect number is a number that is equal to the sum of its proper divisors.

Euclid’s Perfect Number formula

If $2^p-1$ is a prime, then $2^{p-1}(2^p-1)$ is a perfect number.

Sigma function formulas

$$\sigma(n)=\text{sum of all divisors of }n\text{ including }1\text{ and }n$$

这个表述是下面的除数函数(Divisor function)

$$\sigma_x(n)=\sum_{d\mid n}d^x$$

在 $x=1$ 时的特例。后面只涉及 $\sigma_1(n)$，因此简单记为 $\sigma(n)$。

• $\sigma(p^k)=1+p+\ldots+p^k=\dfrac{p^{k+1}-1}{p-1}$
• $\gcd{(m,n)}=1\implies\sigma(mn)=\sigma(m)\sigma(n)$

先通过归纳法证明当 $p_i$ 为素数而且 $p_i\not=p_j$ 时， $\sigma(p_1^{s_1}p_2^{s_2}\ldots p_n^{s_n})=\sigma(p_1^{s_1})\sigma(p_2^{s_2})\ldots\sigma(p_n^{s_n})$。

基础：当 $n=1$ 成立。

归纳假设：假设命题对 $n=k$ 时成立，即

$$\sigma(p_1^{s_1}p_2^{s_2}\ldots p_k^{s_k})=\sigma(p_1^{s_1})\sigma(p_2^{s_2})\ldots\sigma(p_k^{s_k})$$

同时令

$$X=\Big\{x\Big\vert x\mid (p_1^{s_1}p_2^{s_2}\ldots p_k^{s_k})\text{ and }x\in\mathbb{Z^\ge}\Big\}$$

因此

$$\sigma(p_1^{s_1}p_2^{s_2}\ldots p_k^{s_k})=\sigma(p_1^{s_1})\sigma(p_2^{s_2})\ldots\sigma(p_k^{s_k})=\sum_{x\in X}x$$

递推：那么当 $n=k+1$ 时，

$$\begin{aligned} &\sigma(p_1^{s_1}p_2^{s_2}\ldots p_k^{s_k}\cdot p_{k+1}^{s_{k+1}})\\ =&\sum_{x\in X}x+\sum_{x\in X}x\cdot p_{k+1}+\sum_{x\in X}x\cdot p_{k+1}^2+\ldots+\sum_{x\in X}x\cdot p_{k+1}^{s_{k+1}}\\ =&\sum_{x\in X}x\Big(1+p_{k+1}+p_{k+1}^2+\ldots+p_{k+1}^{s_{k+1}}\Big)\\ =&\sum_{x\in X}x\cdot \sigma(p_{k+1}^{s_{k+1}})\\ =&\sigma(p_1^{s_1})\sigma(p_2^{s_2})\ldots\sigma(p_k^{s_k})\cdot\sigma(p_{k+1}^{s_{k+1}}) \end{aligned}$$

所以命题对 $n=k+1$ 时也成立，因此 $\sigma(p_1^{s_1}p_2^{s_2}\ldots p_n^{s_n})=\sigma(p_1^{s_1})\sigma(p_2^{s_2})\ldots\sigma(p_n^{s_n})$。

由算术基本定理，令 $m=p_1^{s_1}p_2^{s_2}\ldots p_a^{s_a}, n=q_1^{t_1}q_2^{t_2}\ldots q_b^{t_b}$。因为 $\gcd{(m,n)}=1$，所以

$$\{p_1,p_2,\ldots,p_a\}\cap\{q_1,q_2,\ldots,q_b\}=\emptyset$$ $$\begin{aligned} \sigma(mn)&=\sigma(p_1^{s_1}p_2^{s_2}\ldots p_a^{s_a}\cdot q_1^{t_1}q_2^{t_2}\ldots q_b^{t_b})\\ &=\sigma(p_1^{s_1})\sigma(p_2^{s_2})\ldots\sigma(p_a^{s_a})\cdot\sigma(q_1^{t_1})\sigma(q_2^{t_2})\ldots\sigma(q_b^{t_b})\\ &=\sigma(m)\sigma(n) \end{aligned}$$

Euclid’s Perfect Number Theorem

If $n$ is an even perfect number, then $n$ looks like $n=2^{p-1}(2^p-1)$

where $2^p-1$ is a Mersenne prime.

设 $n=2^k\cdot d\text{ with }\gcd{(2,d)}=1$.

$$\sigma(n)=\sigma(2^k)\sigma(d)=(2^{k+1}-1)\sigma(d)$$

已知 $n$ 是偶完全数，那么

$$\sigma(n)=2n=2^{k+1}d$$

所以

$$(2^{k+1}-1)\sigma(d)=2^{k+1}d$$

因为 $\gcd{(2^{k+1}-1, 2^{k+1})}=1$，$\exists x,y\in \mathbb{N}\text{ s.t.}$

$$(2^{k+1}-1)x+2^{k+1}y=1$$ $$(2^{k+1}-1)\sigma(d)x+2^{k+1}y=\sigma(d)\\$$

这表示 $2^{k+1}\mid\sigma(d)$，所以令 $\sigma(d)=2^{k+1}\cdot c\text{ with }c\ge1$，进一步得到 $d=(2^{k+1}-1)c$。假设 $c>1$，从 $d=(2^{k+1}-1)c$ 可知以下互不相等的整数

$$1, 2^{k+1}-1,c,(2^{k+1}-1)c$$

都能整除 $d$. 所以

$$\sigma(d)\ge1+2^{k+1}-1+c+(2^{k+1}-1)c=(2^{k+1}+1)c$$

这与 $\sigma(d)=2^{k+1}c$ 矛盾，所以 $c=1$ 而且

$$\begin{array}{} d=2^{k+1}-1&\text{ and }&n=2^k(2^{k+1}-1) \end{array}$$

此外，由于 $\sigma(d)=2^{k+1}=1+(2^{k+1}-1)$，这表示 $d=2^{k+1}-1$ 是一个素数，即梅森素数。

Fermat number

• 如果对于两个整数 $a\ge2$ 和 $n\ge1$， $a^n+1$ 是素数，求证 $n$ 是底数为 $2$ 的幂。

令整数 $n=2^k\cdot (2d+1)\text{, }k\ge 0\text{, }d\in\mathbb{Z^\ge}$。

$$\begin{aligned} a^n+1&=a^{2^k\cdot(2d+1)}+1\\ &=(a^{2^k})^{2d+1}+1^{2d+1}\\ &=(a^{2^k}+1)((a^{2^k})^{2d}-(a^{2^k})^{2d-1}+(a^{2^k})^{2d-2}-\ldots-a^{2^k}+1)\\ \end{aligned}$$

因为 $a^n+1$ 是素数，所以 $d=0$。因此 $n=2^k$。

Fermat number and Fermat primes

形如 $F_k=2^{2^k}+1$ 的整数称为费马数；如果 $F_k$ 是素数，那么 $F_k$ 称为费马素数。

• 证明对于任意两个正整数 $m\not=n$，$\gcd{(F_m,F_n)}=1$.

令 $n=m+k$，考虑 $F_n-2$ 的值

$$\begin{aligned} F_n-2&=2^{2^n}-1=2^{2^m\cdot 2^k}-1\\ &=(2^{2^m}-1)\cdot\Big((2^{2^m})^{2^k-1}+(2^{2^m})^{2^k-2}+\ldots+(2^{2^m})+1\Big)\\ \end{aligned}$$

由于 $(2^{2^m})^{2^k-1}+(2^{2^m})^{2^k-2}+\ldots+(2^{2^m})+1$ 一共有偶数项($2^k-1+1=2^k$)，因此

$$\begin{aligned} F_n-2&=(2^{2^m}-1)\cdot\Big((2^{2^m}+1)\cdot(2^{2^m})^{2^k-2}+(2^{2^m}+1)\cdot(2^{2^m})^{2^k-4}+\ldots+(2^{2^m}+1)\Big)\\ &=(2^{2^m}-1)\cdot(2^{2^m}+1)\cdot((2^{2^m})^{2^k-2}+(2^{2^m})^{2^k-4}+\ldots+1)\\ &=F_m \cdot C \end{aligned}$$

令 $d=\gcd{(F_m,F_n)}$，因此 $d\mid {(F_n-F_m\cdot C)}\implies d\mid 2$。又 $F_k$ 为奇数，因此 $d=1$，$\gcd{(F_m,F_n)}=1$。

---

• Previous
  A Friendly Introduction to Number Theory Chapter 10~11
• Next
  String searching

---