Strong induction lets the current case use every earlier case, not just the one immediately before it. That extra reach is useful when an integer breaks into factors of unpredictable sizes.

Strong induction

Let $P(n)$ be defined for every integer $n\ge n_0$. A proof by strong induction has two parts:

1. prove the base case $P(n_0)$;
2. for an arbitrary $n>n_0$, assume $P(k)$ for every integer $k$ with $n_0\le k<n$, then prove $P(n)$.

The strong induction hypothesis is

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

The first few links look like

$$\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}$$

“All earlier cases” means earlier cases inside the theorem's stated domain. It does not include $P(n)$ itself. Ordinary and strong induction prove the same kinds of natural-number statements, but strong induction can make a proof much more direct.

Divisibility

For integers $a$ and $b$, we say that $a$ divides $b$, written $a\mid b$, when $b$ is an integer multiple of $a$:

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

The expression $a\mid b$ is a proposition: it is true or false. It is not a fraction. When $a\ne0$, a quotient gives an equivalent test:

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

The condition $a\ne0$ matters because division by zero is undefined, while the original definition still handles zero.

Examples include

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

because $42=3(14)=6(7)=(-7)(-6)$, while no integer multiplied by $5$ equals $42$.

For every integer $x$,

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

Indeed, $x=x(1)$ and $0=x(0)$. If $0\mid x$, then $x=0k=0$ for some integer $k$. Conversely, $0=0k$ for every integer $k$, so $0\mid0$.

Three basic divisibility properties

Let $a,b,c\in\mathbb Z$. Each property follows directly from the definition.

Multiplying a divisible number

If $a\mid b$, write $b=ar$ for some $r\in\mathbb Z$. Then

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

Since $rc\in\mathbb Z$, we have

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

Adding or subtracting divisible numbers

If $a\mid b$ and $a\mid c$, write $b=ar$ and $c=as$ for integers $r,s$. Then

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

Since $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

If $a\mid b$ and $b\mid c$, write $b=ar$ and $c=bs$. Then

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

Therefore

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

None of these proofs requires $a$, $b$, or $c$ to be nonzero.

Prime and composite integers

An integer $p\ge2$ is prime when its only positive divisors are $1$ and $p$. The first primes are

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

An integer $n\ge2$ that is not prime is composite. Equivalently, it has a factorization

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

The integers $0$ and $1$ are neither prime nor composite.

Every integer at least two has a prime divisor

We prove by strong induction that every integer $n\ge2$ has a prime divisor.

Base case. Since $2=2\cdot1$ and $2$ is prime, the claim holds at $n=2$.

Strong induction hypothesis. Let $n>2$ and assume every integer $k$ with $2\le k<n$ has a prime divisor.

There are two cases.

• If $n$ is prime, then $n=n\cdot1$, so $n$ itself is a prime divisor.

• If $n$ is composite, write $n=ab$ with $2\le a,b<n$. The induction hypothesis applies to $a$, so $a=pr$ for some prime $p$ and integer $r$. Therefore

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

  Since $rb\in\mathbb Z$, the prime $p$ divides $n$.

Both cases establish the claim for $n$. Thus every integer $n\ge2$ has a prime divisor.

This is not yet the Fundamental Theorem of Arithmetic. Unique prime factorization is later material.

Goldbach's conjecture

A conjecture is a statement believed to be true but not yet proved. Goldbach's conjecture says:

Every even integer greater than $2$ is the sum of two primes.

For example,

$$42=19+23.$$

Examples support the pattern but do not prove it. Goldbach's conjecture remains open.

Euclid's theorem: there are infinitely many primes

Suppose, for contradiction, that all primes form a finite list

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

Define

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

The integer $N$ is greater than $1$, so it is prime or composite.

Case 1: $N$ is prime. It is larger than every $p_i$, so it is a prime missing from the supposedly complete list. This is a contradiction.

Case 2: $N$ is composite. By the prime-divisor theorem, some prime $p$ divides $N$. Since the list supposedly contains every prime, $p=p_i$ for some $i$, and therefore

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

We also have $p\mid N$. The difference property gives

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

so $p\mid1$. But a prime is at least $2$ and cannot divide $1$. This is another contradiction.

Both cases contradict the assumption, so there are infinitely many primes. The proof does not claim that $p_1p_2\cdots p_k+1$ is always prime; if it is composite, one of its prime divisors is enough.

Prime gaps

Prime numbers are not evenly spaced.

Two primes whose difference is $2$ are twin primes, such as

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

The Twin Prime Conjecture says that infinitely many twin-prime pairs exist. It remains open.

In the other direction, gaps between consecutive primes can be arbitrarily large.

For every natural number $n$, there are consecutive primes $p<q$ such that $q-p\ge n$.

For $n\ge2$, consider the $n-1$ consecutive integers

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

For each $k=2,3,\ldots,n$, the integer $k$ divides both $n!$ and $k$, so

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

Also $1<k<n!+k$, so this divisor is nontrivial. Every number in the block is therefore composite.

Let $p$ be the greatest prime below the block and $q$ the least prime above it. Such a $q$ exists because Euclid's theorem makes the primes unbounded. No prime lies between $p$ and $q$, so they are consecutive. Moreover,

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

and hence

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

For $n=0$ or $n=1$, the consecutive primes $2$ and $3$ already work.

The Prime Number Theorem

Define the prime-counting function

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

The Prime Number Theorem describes its long-run growth:

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

The symbol $\sim$ means that the ratio tends to $1$:

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

This is an asymptotic approximation, not an exact equality. The theorem is proved mathematics, but its proof is beyond the scope of this course.