Back to the on-screen lesson ·
Euclid's proof and what it does not give, the sieve that lists the primes, and runs of composite numbers of any length you like.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to give Euclid's proof as a construction rather than as a proof by contradiction, say why the number it builds need not itself be prime, run the sieve of Eratosthenes and explain why striking starts at each prime's square and stops at the square root of the limit, and construct a run of consecutive composite numbers of any length.
Unique factorisation rested on a small observation that was made in passing: every integer above $1$ has a prime factor. Its smallest divisor above $1$ cannot factor further, so it is prime.
That one sentence is the engine of Euclid's proof. Build a number that no prime on a given list divides; it still has some prime factor; therefore there is a prime off the list. Nothing else is needed, and the argument has not been improved on in two thousand years.
The sieve of Eratosthenes lists the primes up to a bound by striking out multiples.
$\pi(x)$ is the prime counting function: how many primes are at most $x$. So $\pi(10) = 4$ and $\pi(100) = 25$.
A prime gap is the difference between consecutive primes. Twin primes are a pair differing by $2$; whether there are infinitely many of them is open.
A primorial $p_k\#$ is the product of the first $k$ primes — the number Euclid's proof adds one to.
Euclid's theorem. No finite list of primes contains every prime.
Take any finite list $p_1, \ldots, p_k$ and set $N = p_1p_2\cdots p_k + 1$. Then $N > 1$, so $N$ has a prime factor $q$. If $q$ were on the list it would divide the product, and it divides $N$, so it would divide $N$ minus the product, which is $1$ — impossible. So $q$ is off the list.
Two details are usually misremembered. It is not a proof by contradiction: no assumption is made that the primes are finite, and the argument runs on any list at all. And $N$ need not be prime: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$. What the proof extracts is a prime factor.
The sieve of Eratosthenes. List $2$ to $n$; repeatedly take the smallest unused survivor, which is prime, and strike out its multiples from its square upwards. Stop when that survivor exceeds $\sqrt n$. What remains is the primes.
Starting at the square is right because every smaller multiple has a smaller prime factor and was struck already. Stopping at $\sqrt n$ is right because a composite $m \le n$ factors as $ab$ with $\min(a, b) \le \sqrt m \le \sqrt n$.
Arbitrarily long gaps. The $n - 1$ consecutive numbers $$n! + 2,\; n! + 3,\; \ldots,\; n! + n$$ are all composite, since $k \mid n!$ and $k \mid k$ for each $k$ in range. So there are runs of composites of any length.
The two facts coexist: the primes never run out, and they can be missing for a million consecutive integers. What neither settles is the average behaviour, which is the next lesson, or whether small gaps keep recurring — the twin prime conjecture, still open, though Zhang proved in 2013 that some gap size recurs infinitely often.
Another way: steps
Another way: example
Sieve to $50$. $\sqrt{50} \approx 7.07$, so only $2, 3, 5, 7$ need striking. Strike multiples of $2$ from $4$; of $3$ from $9$; of $5$ from $25$; of $7$ from $49$. Fifteen numbers survive, so $\pi(50) = 15$. The next prime, $11$, has square $121 > 50$, so it strikes nothing.
Euclid's theorem is an existence statement, and it is worth being exact about how little it says beyond that — because the gap between there are infinitely many and here is where they are is the whole of the rest of the subject.
It does not generate the next prime. Running the argument on $\{2, 3, 5, 7, 11, 13\}$ produces $59$ and $509$, and skips over $17, 19, 23, \ldots$ entirely. As a way of finding primes it is hopeless.
It gives no bound worth having. It does show that the $k$-th prime is at most $p_1\cdots p_{k-1} + 1$, which grows doubly exponentially — a bound so weak as to be useless.
It says nothing about density. Whether the primes thin out quickly or slowly is untouched by the argument.
Euler's proof, two thousand years later, does better on the last point. Consider $$\prod_{p \text{ prime}} \left(1 - \frac1p\right)^{-1} = \prod_p \left(1 + \frac1p + \frac1{p^{2}} + \cdots\right).$$ Expanding the product gives $\sum_n 1/n$ exactly once for each $n$, by unique factorisation — so the product is the harmonic series, which diverges. A finite product of finite terms cannot diverge, so there are infinitely many primes.
That argument gives much more: since the product diverges, $$\sum_{p} \frac1p = \infty.$$ The primes are dense enough that their reciprocals diverge — unlike the squares, whose reciprocals converge. So there are, in a precise sense, more primes than squares. And the rate of divergence, $\sum_{p \le x} 1/p \approx \ln\ln x$, is a quantitative statement about density that Euclid's proof could never reach.
Euler's identity is also the doorway to everything modern. Written with an exponent $s$ it becomes $$\zeta(s) = \sum_{n \ge 1}\frac1{n^{s}} = \prod_p\left(1 - p^{-s}\right)^{-1},$$ and the analytic behaviour of that function is what proves the prime number theorem in the next lesson.
Calling it a proof by contradiction. It is a construction. The usual retelling assumes the primes are finite, which is unnecessary and obscures that the argument hands over a new prime each time it is run.
Claiming $N$ is prime. It very often is not. $30031 = 59 \cdot 509$. The proof extracts a prime factor of $N$ and says nothing about $N$ itself.
Expecting the next prime. The new prime can be anywhere above the list. There is no ordering claim in the argument at all.
Sieving from the prime rather than its square. Striking multiples of $7$ from $14$ wastes work — everything below $49$ has already gone. It is not wrong, only slower.
Reading long gaps as the primes running out. Arbitrarily long gaps and infinitely many primes are both true. Density is a question about averages, and neither fact settles it.
Take the list $\{2, 3, 5\}$. Form $N = 2 \cdot 3 \cdot 5 + 1 = 31$.
Any finite list will do.
$31$ leaves remainder $1$ on division by each of $2$, $3$ and $5$, so none of them divides it — and $31$ is itself prime.
Here the number happens to be prime.
Run it again on $\{2, 3, 5, 7, 11, 13\}$: $N = 30031$, which is not prime — it is $59 \cdot 509$. Both factors are off the list, which is all the proof ever claimed.
The second run is the one worth remembering.
Want a hundred consecutive composite numbers. Take $n = 101$ and the numbers $101! + 2$ through $101! + 101$.
The construction is explicit, not an existence argument.
For each $k$ from $2$ to $101$, $k$ divides $101!$ and divides $k$, so $k$ divides $101! + k$ — which is far larger than $k$, hence composite.
One divisor, supplied by construction.
That is $100$ consecutive composites. They sit around a number with $160$ digits, which is the price: the construction proves long gaps exist and finds them nowhere near where they first occur. The first gap of length $100$ starts at $370\,261$.
Existence is cheap; location is not.
Suppose $q_1, \ldots, q_k$ are primes of that form, and set $N = 4q_1\cdots q_k - 1$, which is itself $3$ modulo $4$.
Adapt the construction rather than the conclusion.
$N$ is odd, and its prime factors cannot all be $1$ modulo $4$ — a product of such numbers is $1$ modulo $4$, and $N$ is $3$. So some prime factor is $3$ modulo $4$.
The parity argument is what replaces the plain divisibility.
That factor divides none of the $q_i$, since it would then divide $1$. So the list can always be extended.
Build Euclid's proof that no finite list of primes contains them all.
This task has no paper form; do it on a device.
How many primes are there up to $140$?
Answer:
Is this true: the primes eventually stop because they get too sparse?
You are sieving the numbers up to $200$. Give the integer part of the square root of $200$, the largest prime whose multiples have to be struck out, and how many primes survive.
| Value | |
|---|---|
| Integer part of the square root | |
| Largest prime to strike multiples of | |
| Primes up to the limit |
Put the steps of sieving the numbers up to $200$ into the order they are carried out.
Number the steps in order (write the number in the box):
Every one of the numbers $7! + 2,\; 7! + 3,\; \ldots,\; 7! + 7$ is composite. How many consecutive composite numbers is that?
how many a
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Is this true: the proof needs an assumption that the list of all primes is finite?
You can prove that the primes never run out and list the primes up to a bound. Say in your own words what Euclid's argument gives you and what it does not. Next: how thickly the primes are spread, on average.
9. Your turn: show there are infinitely many primes of the form $4k + 3$, step 3