Strong induction 允许当前 case 使用此前的每一个 case，而不只使用紧邻的前一项。当一个整数分解成大小不确定的 factors 时，这种方法尤其有用。

Strong induction

设 $P(n)$ 对每个整数 $n\ge n_0$ 都有定义。一个 strong induction 证明包含两部分：

1. 证明 base case $P(n_0)$；
2. 对任意 $n>n_0$，假设每个满足 $n_0\le k<n$ 的整数 $k$ 都有 $P(k)$ 成立，再证明 $P(n)$。

Strong induction hypothesis 是

$$P(n_0)\land P(n_0+1)\land\cdots\land P(n-1).$$

最初几步的结构是

$$\begin{aligned} P(n_0)&\Rightarrow P(n_0+1),\\ P(n_0)\land P(n_0+1)&\Rightarrow P(n_0+2),\\ P(n_0)\land P(n_0+1)\land P(n_0+2)&\Rightarrow P(n_0+3). \end{aligned}$$

“此前所有 cases”只指 theorem 已声明 domain 内的 earlier cases，并不包括 $P(n)$ 本身。Ordinary induction 与 strong induction 能证明同一类 natural-number statements，但 strong induction 有时能让论证更直接。

Divisibility

对于整数 $a$、$b$，如果 $b$ 是 $a$ 的整数倍，就说 $a$ divides $b$，记作 $a\mid b$：

$$\boxed{a\mid b\iff \exists k\in\mathbb Z\text{ such that }b=ak.}$$

表达式 $a\mid b$ 是一个 proposition，只有 true 或 false，不是 fraction。当 $a\ne0$ 时，可以用 quotient 作等价判断：

$$a\mid b\iff \frac ba\in\mathbb Z.$$

条件 $a\ne0$ 不能省略，因为 division by zero 没有定义，而原来的 divisibility definition 仍然能处理零。

例如，

$$3\mid42, \qquad6\mid42, \qquad-7\mid42, \qquad5\nmid42,$$

因为 $42=3(14)=6(7)=(-7)(-6)$，但不存在整数乘以 $5$ 得到 $42$。

对每个整数 $x$，

$$x\mid x, \qquad x\mid0, \qquad0\mid x\iff x=0.$$

前两个结论分别来自 $x=x(1)$ 和 $0=x(0)$。若 $0\mid x$，则对某个整数 $k$ 有 $x=0k=0$。反过来，$0=0k$ 对任意整数 $k$ 都成立，所以 $0\mid0$。

Divisibility 的三个基本性质

设 $a,b,c\in\mathbb Z$。下面每个性质都能直接从 definition 证明。

乘上任意整数

若 $a\mid b$，则存在 $r\in\mathbb Z$，使 $b=ar$。于是

$$bc=(ar)c=a(rc).$$

因为 $rc\in\mathbb Z$，所以

$$a\mid b\quad\Longrightarrow\quad a\mid bc.$$

对可整除的数作加减

若 $a\mid b$ 且 $a\mid c$，写成 $b=ar$、$c=as$，其中 $r,s\in\mathbb Z$。则

$$b\pm c=ar\pm as=a(r\pm s).$$

因为 $r\pm s\in\mathbb Z$，所以

$$a\mid b\text{ and }a\mid c \quad\Longrightarrow\quad a\mid(b+c)\text{ and }a\mid(b-c).$$

Transitivity

若 $a\mid b$ 且 $b\mid c$，取整数 $r,s$，写成 $b=ar$、$c=bs$。于是

$$c=bs=(ar)s=a(rs).$$

因此

$$a\mid b\text{ and }b\mid c \quad\Longrightarrow\quad a\mid c.$$

这三个证明都不要求 $a$、$b$ 或 $c$ 非零。

Prime 与 composite integers

整数 $p\ge2$ 如果只有两个 positive divisors，也就是 $1$ 和 $p$，就称为 prime。最初几个 primes 是

$$2,3,5,7,11,13,17,19,23,\ldots.$$

整数 $n\ge2$ 若不是 prime，就称为 composite。等价地，它可以写成

$$n=ab \qquad\text{with}\qquad 2\le a,b<n.$$

整数 $0$ 和 $1$ 既不是 prime，也不是 composite。

每个不小于二的整数都有 prime divisor

用 strong induction 证明：每个整数 $n\ge2$ 都有一个 prime divisor。

Base case。 $2=2\cdot1$，而 $2$ 是 prime，所以 $n=2$ 时成立。

Strong induction hypothesis。 任取 $n>2$，假设每个满足 $2\le k<n$ 的整数 $k$ 都有 prime divisor。

分成两种情况。

• 若 $n$ 是 prime，则 $n=n\cdot1$，所以 $n$ 本身就是一个 prime divisor。

• 若 $n$ 是 composite，写成 $n=ab$，其中 $2\le a,b<n$。Induction hypothesis 可以用于 $a$，所以 $a=pr$，其中 $p$ 是 prime，$r$ 是整数。因此

  $$n=ab=(pr)b=p(rb).$$

  因为 $rb\in\mathbb Z$，prime $p$ divides $n$。

两种情况都证明了当前的 $n$，所以每个整数 $n\ge2$ 都有 prime divisor。

这还不是 Fundamental Theorem of Arithmetic。Prime factorization 的 uniqueness 是后续内容。

Goldbach's conjecture

Conjecture 是被认为正确、但还没有证明的 statement。Goldbach's conjecture 说：

每个大于 $2$ 的 even integer 都能写成两个 primes 的和。

例如，

$$42=19+23.$$

例子只能展示 pattern，不能完成证明。Goldbach's conjecture 目前仍是 open problem。

Euclid's theorem：primes 有无限多个

假设相反，所有 primes 可以列成一个 finite list：

$$p_1,p_2,\ldots,p_k.$$

定义

$$N=p_1p_2\cdots p_k+1.$$

整数 $N$ 大于 $1$，所以它要么 prime，要么 composite。

Case 1：$N$ 是 prime。 它比每个 $p_i$ 都大，因此是一个没有出现在 supposedly complete list 中的 prime，产生 contradiction。

Case 2：$N$ 是 composite。 由前面证明的 prime-divisor theorem，存在 prime $p$ divides $N$。既然 list 假设已经包含全部 primes，就有 $p=p_i$ 对某个 $i$ 成立，因此

$$p\mid p_1p_2\cdots p_k.$$

同时 $p\mid N$。利用 difference property，

$$p\mid\left(N-p_1p_2\cdots p_k\right),$$

所以 $p\mid1$。但 prime 至少为 $2$，不可能整除 $1$，再次产生 contradiction。

两种情况都与最初 assumption 冲突，所以 primes 有无限多个。这个证明没有说 $p_1p_2\cdots p_k+1$ 总是 prime；它为 composite 时，只需要取其中一个 prime divisor。

Prime gaps

Primes 并不是 evenly spaced。

两个 primes 相差 $2$ 时称为 twin primes。例如，

$$(3,5), \qquad(11,13), \qquad(4241,4243).$$

Twin Prime Conjecture 说 twin-prime pairs 有无限多对。它目前仍是 open problem。

另一方面，consecutive primes 之间的 gaps 可以任意大。

对每个 natural number $n$，存在 consecutive primes $p<q$，使 $q-p\ge n$。

当 $n\ge2$ 时，考虑下面 $n-1$ 个 consecutive integers：

$$n!+2,n!+3,\ldots,n!+n.$$

对每个 $k=2,3,\ldots,n$，$k$ 同时整除 $n!$ 和 $k$，所以

$$k\mid(n!+k).$$

并且 $1<k<n!+k$，因此 $k$ 是 nontrivial divisor，这个 block 中的每个数都是 composite。

令 $p$ 是这个 block 左侧最大的 prime，$q$ 是右侧最小的 prime。Euclid's theorem 说明 primes 无上界，所以这样的 $q$ 一定存在。$p$ 与 $q$ 之间没有其他 prime，因此它们是 consecutive primes。又有

$$p\le n!+1, \qquad q\ge n!+n+1,$$

所以

$$q-p\ge(n!+n+1)-(n!+1)=n.$$

当 $n=0$ 或 $n=1$ 时，consecutive primes $2$、$3$ 已经符合要求。

Prime Number Theorem

定义 prime-counting function

$$\pi(n)=\#\{p\le n\mid p\text{ is prime}\}.$$

Prime Number Theorem 描述它的长期增长：

$$\boxed{\pi(n)\sim\frac{n}{\ln n}}.$$

符号 $\sim$ 表示两者的 ratio 趋近于 $1$：

$$\lim_{n\to\infty} \frac{\pi(n)}{n/\ln n}=1.$$

这是 asymptotic approximation，不是 exact equality。Prime Number Theorem 是已经证明的 theorem，但它的 proof 超出本课程范围。