Primes and Euclid's proof: Arithmetic, Round 1

1 Learn

You will be able to

Classify a number as prime or composite by finding a divisor other than 1 and itself.
Write Euclid's proof that no finite list of primes is complete as numbered steps.
State what IX.20 claims in Euclid's wording and what the construction does not do.
Use one counterexample to refute a claim about all n, and say why successful cases do not prove it.

LabInfinitely many primesEuclid's proof step by step, what IX.20 actually states, and the worked case 30031 = 59 x 509.
LibraryProof and Precise Reasoning: From Arguments to Theorems · The main proof formsPlaces IX.20 among the proof forms and notes that Euclid's own version is constructive.2 min glance · 6 min
LibraryProof and Precise Reasoning: From Arguments to Theorems · What a proof is, and is notWhy an example or a computation can refute a claim about all numbers but never establish one.2 min glance · 6 min
LibraryProof and Precise Reasoning: From Arguments to Theorems · Counterexample and falsificationA single valid counterexample refutes a universal claim.2 min glance · 6 min
LibraryThe Seven Liberal Arts, Hands-On: Logic, Proof and the Quadrivium · The quadrivium in practiceEuler's polynomial n squared plus n plus 41: forty prime values in a row, then 1681 = 41 squared.2 min glance · 7 min

2 Practise

Answer each card from memory, then grade yourself honestly. The cards join your review deck and come back just before you would forget them.

recall
In Euclid's proof (Elements IX.20) that no finite list of primes is complete, what number is formed from a list p₁, …, pₙ, and why must its prime divisor be missing from the list?

Show answer
N = (p₁ · p₂ · … · pₙ) + 1. N is greater than 1, so it has a prime divisor q. If q were on the list it would divide both the product and N, hence their difference, 1, which no prime divides.
recall
Euclid's Elements IX.20 is usually summarised as 'there are infinitely many primes'. What does it actually state?

Show answer
That the primes are more than any assigned multitude of primes, so no finite list of primes can be complete. Euclid avoids speaking of a completed infinity and claims only what the construction shows.
apply
Apply Euclid's prime construction to the primes 2, 3, 5, 7, 11 and 13. What is N, is it prime, and what does the result show about the method?

Show answer
N = 30030 + 1 = 30031 = 59 × 509, so it is composite. Its factors are new primes, as the proof promises, but neither is the next prime, 17. The construction proves new primes exist without finding them: existence is not a method.
apply
A student finds that a formula gives a prime for every whole number from 0 to 20 and is ready to claim it always does. What does the page advise, and what does its Euler example show?

Show answer
Passing cases is not proof: testing refutes quickly but never proves, so keep testing and seek a proof. Euler's n squared plus n plus 41 gives a prime for every n from 0 to 39, yet n = 40 gives 1681, which is 41 squared.
apply
A classmate checks a formula for n = 1, 2, 3 and 4 and concludes it holds for every positive integer n. Why is that not a proof, and which proof form on the page is built to cover every n?

Show answer
Checking particular cases can refute a universal claim but cannot establish it; the next case could fail, as "every odd number is prime" fails at 9. Induction can cover every n: prove a base case, then prove that if the formula holds for n, it holds for n + 1.
connect
This page says the counterexample habit underlies the testing habit in 'Hypotheses, Predictions and Tests'. What asymmetry drives that habit, and how does it shape the way you test an explanation?

Show answer
One valid counterexample refutes a universal claim, while checking some cases cannot prove it. So you ask "what would refute this?" and design tests whose result could show the explanation wrong, writing the prediction down before you look.

3 Prove it: the mastery check

5 questions drawn from a pool of 12. The pass mark is 80%. There is no time limit, and you can retake it with new questions; your best result counts.

4 Prove it: the performance task

Euclid's argument, rebuilt and tested

Without looking at the page, write Euclid's proof that no finite list of primes is complete as numbered steps in your own words. Then run the construction on three lists: 2, 3, 5; a list of four or more primes that you choose; and a list that you choose and expect to give a composite N. For each list, record the product, N, the prime factorisation of N, and which prime factors of N are missing from the list. Finish with two sentences: what the proof establishes, in Euclid's wording, and one thing the construction does not do.

What to hand in: One page, typed or handwritten and photographed: the numbered proof, a table with three rows (list, product, N, prime factorisation of N, missing primes) and the two closing sentences.

Check your work against the rubric The proof has numbered steps, each a single declarative sentence, in this order: choose a list, form N, take a prime divisor q of N, show q is not on the list, conclude. The step showing q is not on the list says that q would divide both the product and N, so would divide 1, and that no prime divides 1. The table has three rows. Each N is correct, and multiplying the prime factors you give returns N. At least one row has a composite N, and the write-up names the prime factors of that N that are missing from the list. The closing sentences say that the primes are more than any assigned multitude of primes, and name one thing the construction does not do, such as find the next prime.

Your work Or a link to it (optional)

Saved only in this browser. To keep a copy, download it or export your progress.

5 Discuss: the seminar

Read the text, then think, write or talk through the question with someone. There is no answer key: the aim is a better question.

Arithmetic · Round 1

Nicomachus of Gerasa, Introduction to Arithmetic, translated by Martin Luther D'Ooge (Macmillan, 1926), Book I, chapters 7 to 13Chapter 7 divides number into even and odd. Chapters 8 to 10 divide the even. Chapters 11 to 13 divide the odd into the prime and incomposite, the secondary and composite, and the kind that is composite in itself but prime and incomposite relative to another. Chapter 13 also describes the sieve of Eratosthenes and a test by repeated subtraction for whether two odd numbers have a common measure. D'Ooge's translation was published in 1926, so it entered the public domain in the United States on 1 January 2022. This Zenodo record holds a full PDF scan of the 1926 volume. Cite by book and chapter, not by page.
Euclid, Elements, Book VII (David Joyce's online edition, Clark University), Definitions 1 to 16; Propositions 1 and 2Definitions 11 to 14 define prime, relatively prime, composite and relatively composite numbers by what measures them. Propositions 1 and 2 are linked from the same page. Proposition 2 finds the greatest common measure of two numbers by repeated subtraction; Elements X.2 applies the same idea to magnitudes.

Euclid calls a prime a number 'measured by a unit alone' (Book VII, Definition 11), while Nicomachus calls it 'prime and incomposite' and files it among the odd numbers (I.11). What does each way of defining a prime make you notice, and what does each hide?

On Euclid's Definition 11, does the number 2 count as prime? Where would Nicomachus put it, given that he sorts primes among the odd numbers?
Nicomachus describes a sieve (I.13) that separates primes from composites by a procedure. Does knowing how to find primes tell you what a prime is?
In VII.1 and VII.2 Euclid subtracts the smaller number from the larger again and again. What does he assume about what it means for one number to 'measure' another?

Keep notes on the seminars page →

Primes and Euclid's proof