Module 1 · Lesson 1

Number Theory: Primes, divisibility, and Euclid's proof that the primes never run out

You'll meet the oldest branch of mathematics still being actively researched: the study of whole numbers. You'll work with primes, factorization, and remainders, and you'll follow a proof from about 300 BCE that there is no largest prime.

What you will be able to do

Use divisibility and modular arithmetic to reason about whole numbers, including why there are infinitely many primes.

0% of this lesson · 9 items · 1h 3m total · 48m without the optional problem set

Contents of this lesson9 items

ReadingIs There a Largest Prime Number?3 min
ReadingQuestions About Whole Numbers from Euclid and Sunzi to Fermat, Euler, and Gauss4 min
ReadingDivisibility, Prime Numbers, and Factorization into Primes4 min
ReadingClock Arithmetic: Remainders and Modular Arithmetic4 min
ReadingEuclid's Proof That the Primes Never Run Out4 min
Guided ReadingWorked Example: Running Euclid's Argument on Real Lists of Primes7 min
Guided ConversationFind a Prime Missing From Any List12 min
Problem Set · optionalPrimes, Factors, and Remainders15 min
Knowledge CheckPrimes, divisibility, and Euclid's proof that the primes never run out10 min

Report an issue on this page

Reading 3 min Done

Is There a Largest Prime Number?

Here is a list you can check with pencil and paper. It holds every prime number up to 50. A prime is a whole number greater than 1 that no whole number divides evenly except 1 and itself.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Count them in blocks of ten. There are four primes from 1 to 10 and four from 11 to 20. Then come two, two, and three. Further out, the thinning continues. Between 1,000 and 2,000 there are 135 primes, roughly one number in every seven.

So here is the puzzle. If the primes keep getting rarer, do they eventually stop? Is there a largest prime, after which every whole number splits into smaller factors? Before you go on, decide what you think, and decide what would convince you.

The natural first move is to check. You could test every number up to a million, or a billion, and you would keep finding primes. But no amount of checking settles the question. There are infinitely many whole numbers, so any search, however long, ends somewhere. For all the search shows, the primes could run out just past the point where you stopped. Thinning out fits a story in which primes stop and a story in which they never do.

The question was settled about 2,300 years ago, with no computer and no large numbers checked. Euclid's Elements, a Greek text compiled about 300 BCE, contains a short argument that the primes never run out (O'Connor and Robertson 2018). In David Joyce's translation, the statement says that prime numbers "are more than any assigned multitude of prime numbers" (Euclid, Elements IX.20). In plain terms, hand over any finite list of primes, and there is a prime that isn't on it.

The argument doesn't measure how big the primes are or where they fall. It takes whatever list someone might offer and shows how to build, from that list, a number that forces a new prime into view. Because it works the same way on every possible list, it covers all of them at once, including lists far too long to write down.

That is the kind of reasoning number theory trades in. Number theory is the study of whole numbers: which ones divide which, how they break into primes, and what patterns their remainders follow. Its questions are often easy to state and hard to answer. Its best answers do something checking can't do. They tell you about every whole number, infinitely many of them, from an argument short enough to read in a few minutes.

Some of the field's questions about primes are still open after centuries of effort. This one isn't. The primes never stop, and the reason needs nothing more than multiplication, addition, and division with remainders.

References

Euclid. Elements. Edited and translated by David E. Joyce, after T. L. Heath's edition. Worcester, MA: Clark University, 1996–2013.
- Free: Euclid's Elements, Book IX, Proposition 20 (Joyce)
O'Connor, J. J., and E. F. Robertson. 2018. "Prime Numbers." MacTutor History of Mathematics Archive, University of St Andrews. Last updated January 2018.
- Free: MacTutor: Prime numbers

Reading 4 min Done

Questions About Whole Numbers from Euclid and Sunzi to Fermat, Euler, and Gauss

Introduction

Number theory has no founding date and no single founder. It grew out of questions that people in different places and centuries asked about whole numbers, and it took its modern shape only around 1800. This reading follows that growth through five texts and people, from Greek geometry to a book published in 1801. Euclid's Elements is cited by book and proposition, so IX.20 means Book IX, Proposition 20.

Euclid's Books on Number

Number theory is the branch of mathematics that studies whole numbers and their properties, such as which numbers divide which. A whole number (an integer, in mathematicians' language) is a number with no fractional part, such as 0, 7, or −3. Most of the questions in this reading concern the positive ones.

Euclid's Elements, a Greek text compiled about 300 BCE, is mostly geometry. Books VII to IX, though, deal with numbers (Katz 2018, chap. 3). In Joyce's translation, Euclid defines a prime number as one "measured by a unit alone" (Euclid, Elements VII, def. 11). In modern terms, a prime is a whole number greater than 1 whose only positive divisors are 1 and itself. The books go on to prove that there are infinitely many primes (Elements IX.20).

They also study perfect numbers. A perfect number is a positive whole number equal to the sum of its divisors other than itself. The divisors of 6 other than 6 are 1, 2, and 3, which add up to 6. The divisors of 28 other than 28 are 1, 2, 4, 7, and 14, which add up to 28. Euclid gives a recipe. Add up 1, 2, 4, 8, and so on, doubling each time. If the total is prime, multiply it by the last number you added, and the result is perfect (Elements IX.36). For example, $1 + 2 + 4 = 7$ is prime, and $7 \times 4 = 28$ .

A Remainder Puzzle in China

A different kind of question appears in the Chinese Sunzi suanjing (Master Sun's Mathematical Manual). Its date is uncertain; it's often placed in the 3rd to 5th century CE (Katz 2018, chap. 7). One problem asks for a number of things that leaves 2 over when counted in threes, 3 over when counted in fives, and 2 over when counted in sevens.

You can try it. The smallest answer is 23. Divide 23 by 3 and the remainder is 2. Divide it by 5 and the remainder is 3. Divide it by 7 and the remainder is 2. The text gives a method that works for other remainders too. The question isn't about which numbers divide which. It's about what remainders a number leaves, which turned out to be just as rich a subject.

Fermat and Euler

In 17th-century France, Pierre de Fermat found results about primes that are still taught. One, now called Fermat's little theorem, says that if $p$ is a prime and $a$ is any whole number, then $a^p$ and $a$ leave the same remainder on division by $p$ (O'Connor and Robertson 2018). Take $p = 5$ and $a = 2$ : $2^5 = 32$ , and 32 and 2 both leave remainder 2 when divided by 5. Fermat also guessed that numbers of the form $2^n + 1$ are prime whenever $n$ is a power of 2.

In the 18th century, Leonhard Euler proved and extended much of Fermat's work. He showed that $2^{32} + 1 = 4{,}294{,}967{,}297$ is divisible by 641, which refuted Fermat's guess. He extended the little theorem. In 1747 he proved that every even perfect number has the form Euclid's recipe produces (O'Connor and Robertson 2018).

Gauss Organizes the Field

In 1801 Carl Friedrich Gauss published Disquisitiones Arithmeticae (Arithmetical Investigations). It gathered results on whole numbers into one systematic treatment and gave the subject a shared language (Katz 2018, chap. 21). It opens with the idea of congruence: two whole numbers are congruent relative to a third number when they leave the same remainder on division by it. Gauss wrote this with a new symbol, ≡, which is still in use.

Who or what	When	Where	Question asked
Euclid's Elements, Books VII–IX	About 300 BCE	Greek world	Which numbers are prime or perfect, and how many primes are there?
Sunzi suanjing	Uncertain; often 3rd–5th century CE	China	Which number leaves given remainders on division by 3, 5, and 7?
Fermat	1600s	France	What patterns hold for primes and their powers?
Euler	1700s	Europe	Which of those patterns can be proved, and which fail?
Gauss	1801	Germany	How do all these results fit into one theory?

Conclusion

No single person founded number theory. Greek, Chinese, and European mathematicians asked separate questions about divisibility, remainders, and primes over roughly two thousand years. Gauss's 1801 book joined those threads, and its notation for congruence is still the field's working language.

Key Terms

Number theory: The branch of mathematics that studies whole numbers and their properties, such as which numbers divide which.
Whole number (integer): A number with no fractional part, such as 0, 7, or −3.
Prime: A whole number greater than 1 whose only positive divisors are 1 and itself.
Perfect number: A positive whole number equal to the sum of its divisors other than itself, such as 6 or 28.
Congruence: The relation between two whole numbers that leave the same remainder on division by a given number, written with Gauss's symbol ≡.

References

Euclid. Elements. Edited and translated by David E. Joyce, after T. L. Heath's edition. Worcester, MA: Clark University, 1996–2013.
- Free: Euclid's Elements, Book IX, Proposition 20 (Joyce)
Katz, Victor J. 2018. A History of Mathematics: An Introduction. 3rd ed., Classic Version. New York: Pearson.
- Free: None
- Publisher: Pearson
- Free companion: O'Connor and Robertson 2018
O'Connor, J. J., and E. F. Robertson. 2018. "Prime Numbers." MacTutor History of Mathematics Archive, University of St Andrews. Last updated January 2018.
- Free: MacTutor: Prime numbers

Reading 4 min Done

Divisibility, Prime Numbers, and Factorization into Primes

Introduction

Every whole number greater than 1 can be built by multiplying primes, and there is only one way to do it. That fact is why primes sit at the center of number theory. This reading defines divisibility, primes, and composite numbers, shows how to break a number into primes, and states the theorem that makes the breakdown unique. Euclid's Elements is cited by book and proposition, so VII.30 means Book VII, Proposition 30.

When One Number Divides Another

Start with whole numbers, the numbers with no fractional part. One whole number divides another when the second is the first times some whole number. In symbols, $a$ divides $b$ when $b = a \times k$ for some whole number $k$ . Here $a$ , $b$ , and $k$ are letters standing for whole numbers.

For example, 3 divides 12, because $12 = 3 \times 4$ . But 5 doesn't divide 12, because no whole number times 5 gives 12. When $a$ divides $b$ , you call $a$ a divisor of $b$ , and you call $b$ a multiple of $a$ . The positive divisors of 12 are 1, 2, 3, 4, 6, and 12. The positive multiples of 3 are 3, 6, 9, 12, and so on without end.

Primes, Composites, and the Odd Case of 1

A prime is a whole number greater than 1 whose only positive divisors are 1 and itself. The first few are 2, 3, 5, 7, 11, and 13. A composite number is a whole number greater than 1 that has at least one divisor other than 1 and itself. So 12 is composite, since 3 divides it, and 91 is composite, since $91 = 7 \times 13$ .

That leaves 1, which is neither prime nor composite. The reason is a choice, not an accident. If 1 counted as prime, you could write 6 as $2 \times 3$ , or $1 \times 2 \times 3$ , or $1 \times 1 \times 2 \times 3$ , with as many 1s as you like. The breakdown of a number into primes would stop being unique. Leaving 1 out keeps the theorem below true without exceptions.

Breaking a Number into Primes

The prime factorization of a number is that number written as a product of primes. You can find it by repeated division. Divide by the smallest prime that goes in evenly, and keep going until only 1 is left.

Take 360. It's even, so divide by 2 and get 180. Divide by 2 again to get 90, and again to get 45. Now 45 is odd, so 2 no longer divides it. Try 3: 45 divided by 3 is 15, and 15 divided by 3 is 5. What remains, 5, is itself prime. You divided by 2 three times, by 3 twice, and by 5 once.

A small exponent records how many times a factor repeats: $2^3$ means $2 \times 2 \times 2$ . So the result reads:

360 = 2^3 \times 3^2 \times 5

Multiply it back to check: $8 \times 9 \times 5 = 360$ .

One Way Only

The fundamental theorem of arithmetic says that every whole number greater than 1 is either prime or a product of primes, and that this product is unique apart from the order of the factors. However you break 360 down, you will always end with three 2s, two 3s, and one 5.

The existence half is the easier part. Euclid shows that every composite number is divisible by some prime (Elements VII.31). The uniqueness half rests on a key step that Euclid also proves: if a prime divides the product of two numbers, it divides at least one of them (Elements VII.30). Historians differ on whether Euclid's propositions amount to the full theorem, since he never states uniqueness in general; the MacTutor history credits him with a proof (O'Connor and Robertson 2018).

This is why primes are often called the atoms of multiplication. Every other whole number is a molecule built from them, with a fixed recipe. To understand how numbers behave under multiplication, you mostly need to understand primes.

Conclusion

Divisibility sorts whole numbers greater than 1 into primes and composites, and 1 is set apart so that factorization stays unique. Repeated division finds any number's prime factorization, and the fundamental theorem of arithmetic guarantees there is only one. Euclid proved the key step more than two thousand years ago.

Key Terms

Divisor: A whole number $a$ is a divisor of $b$ when $b = a \times k$ for some whole number $k$ .
Multiple: A whole number $b$ is a multiple of $a$ when $b = a \times k$ for some whole number $k$ .
Prime: A whole number greater than 1 whose only positive divisors are 1 and itself.
Composite: A whole number greater than 1 that has at least one divisor other than 1 and itself.
Prime factorization: A whole number written as a product of primes, such as $360 = 2^3 \times 3^2 \times 5$ .
Fundamental theorem of arithmetic: The theorem that every whole number greater than 1 is prime or a product of primes, in exactly one way apart from order.

References

Euclid. Elements. Edited and translated by David E. Joyce, after T. L. Heath's edition. Worcester, MA: Clark University, 1996–2013.
- Free: Euclid's Elements, Book IX, Proposition 20 (Joyce)
O'Connor, J. J., and E. F. Robertson. 2018. "Prime Numbers." MacTutor History of Mathematics Archive, University of St Andrews. Last updated January 2018.
- Free: MacTutor: Prime numbers

Reading 4 min Done

Clock Arithmetic: Remainders and Modular Arithmetic

Introduction

If it's 9 o'clock now, what time will it be in 5 hours? You answer "2 o'clock" without thinking of 14. That everyday move is a whole branch of arithmetic. This reading explains remainders, modular arithmetic, and the notation Gauss introduced in 1801, with two short examples you can check.

The Clock as a Model

A 12-hour clock ignores everything except where you are in the cycle. Adding 5 hours to 9 o'clock gives 14 hours in ordinary arithmetic. The clock wraps around after 12, so it shows 2. Adding 12 hours, or 24, or any multiple of 12, brings you back to the same place.

What the clock keeps is a remainder. Divide 14 by 12: it goes in once, with 2 left over. In symbols, $14 = 1 \times 12 + 2$ . The remainder is the amount left over when one whole number is divided by another, and it is always smaller than the number you divide by. The clock reading is the remainder on division by 12.

Same Remainder, Same Position

Modular arithmetic is arithmetic that keeps only remainders on division by a fixed whole number. That fixed number is called the modulus. On a clock the modulus is 12. For days of the week it's 7. For the last digit of a number it's 10, since the last digit is the remainder on division by 10. Because a remainder is always smaller than the modulus, modulo 12 there are exactly 12 possible remainders, 0 through 11, and every whole number lands on one of them.

Two whole numbers are congruent modulo a number when they leave the same remainder on division by it. So 14 and 2 are congruent modulo 12, and so are 26 and 2. "Modulo 12" means "counting remainders on division by 12."

Questions about remainders are old. The Chinese Sunzi suanjing, often dated to the 3rd to 5th century CE, asks for a number that leaves given remainders on division by 3, 5, and 7 (Katz 2018, chap. 7). The systematic language came much later.

Remainders Add and Multiply

Here is the property that makes modular arithmetic useful. To find the remainder of a sum, you can add the remainders and then take the remainder of that. The same holds for products. You never need the full numbers, only what they leave over.

Here is the sum rule on a clock. On division by 12, 38 leaves 2 and 47 leaves 11. Adding the remainders gives 13, which leaves 1. So $38 + 47$ should leave remainder 1, and it does: $85 = 7 \times 12 + 1$ . The rule works because whole multiples of the modulus contribute nothing to a remainder.

Take a day-of-the-week question. Today is Monday; what day is it 100 days from now? Days repeat every 7, so the modulus is 7. Divide 100 by 7: $100 = 14 \times 7 + 2$ . The 14 full weeks bring you back to Monday, and the remainder, 2, moves you two days on. The answer is Wednesday.

Now a product. What is the last digit of $47 \times 38$ ? The last digits are 7 and 8, and $7 \times 8 = 56$ , which ends in 6. So the product ends in 6. Check: $47 \times 38 = 1{,}786$ .

Gauss's Notation

In his Disquisitiones Arithmeticae of 1801, Carl Friedrich Gauss introduced a compact way to write congruence (Katz 2018, chap. 21). Here it is for the clock example:

14 \equiv 2 \pmod{12}

Read it aloud as "14 is congruent to 2, modulo 12." The three-bar symbol $\equiv$ means "leaves the same remainder as." The part in parentheses names the modulus. In general, $a \equiv b \pmod n$ says that $a$ and $b$ leave the same remainder when divided by $n$ , where $a$ , $b$ , and $n$ stand for whole numbers.

The notation made remainder questions look like equations, so they could be manipulated with familiar moves. Older results fit the new language too. Fermat's little theorem, for instance, says that for a prime $p$ , $a^p \equiv a \pmod p$ (O'Connor and Robertson 2018).

Conclusion

Modular arithmetic replaces numbers with their remainders, the way a clock replaces 14 with 2. Sums and products can be worked out from remainders alone, which turns large calculations into small ones. Gauss's 1801 notation, $a \equiv b \pmod n$ , is still the standard way to write it.

Key Terms

Remainder: The amount left over when one whole number is divided by another; it is always smaller than the number you divide by.
Modular arithmetic: Arithmetic that keeps only remainders on division by a fixed whole number.
Modulus: The fixed whole number whose remainders modular arithmetic keeps, such as 12 on a clock.
Congruent: Leaving the same remainder on division by a given modulus, written $a \equiv b \pmod n$ .

References

Katz, Victor J. 2018. A History of Mathematics: An Introduction. 3rd ed., Classic Version. New York: Pearson.
- Free: None
- Publisher: Pearson
- Free companion: O'Connor and Robertson 2018
O'Connor, J. J., and E. F. Robertson. 2018. "Prime Numbers." MacTutor History of Mathematics Archive, University of St Andrews. Last updated January 2018.
- Free: MacTutor: Prime numbers

Reading 4 min Done

Euclid's Proof That the Primes Never Run Out

Introduction

Primes get rarer as numbers grow, so it's reasonable to wonder whether they eventually stop. No search can answer that, because there are always more numbers to check. This reading follows Euclid's argument that settles it, and explains why a short proof about any list counts as a landmark. Euclid's Elements is cited by book and proposition, so IX.20 means Book IX, Proposition 20.

What Euclid Claims

A proof is an argument that shows a statement must be true, step by step, from facts already established. A prime is a whole number greater than 1 whose only positive divisors are 1 and itself.

In David Joyce's translation, Euclid states that prime numbers "are more than any assigned multitude of prime numbers" (Euclid, Elements IX.20). An assigned multitude is a finite list: a list with a definite number of entries that you could, at least in principle, write out in full. The claim is that no such list contains every prime. Equivalently, there are infinitely many primes, meaning more than any finite count.

The Argument in Words

Take any finite list of primes. Multiply all of them together, then add 1. Call the result $N$ .

Divide $N$ by any prime on the list. The product part divides evenly, so what's left over is the 1 you added. Every listed prime leaves remainder 1 when it divides $N$ . So no prime on the list divides $N$ .

Now $N$ is bigger than 1, and every whole number bigger than 1 is either prime or divisible by some prime (Euclid proves this in Elements VII.32). That gives two cases:

If $N$ is prime, it is a prime not on the list, since it leaves remainder 1 when divided by each listed prime.
If $N$ isn't prime, some prime divides it. That prime can't be on the list, because no listed prime divides $N$ .

Either way, there's a prime missing from the list. Since the list was any finite list, no finite list of primes is complete.

The argument doesn't promise the next prime after the largest one on the list, or any particular prime. It promises only that something is missing. That is enough, because a complete list would have nothing missing.

Try it on small lists. From {2, 3} you get $2 \times 3 + 1 = 7$ , which is prime and new. From {3, 5} you get $3 \times 5 + 1 = 16$ , which isn't prime. Its only prime factor is 2, and 2 isn't on the list. The argument doesn't promise that $N$ is prime. It promises a new prime somewhere among its factors.

How Euclid Wrote It

Euclid's own version uses three primes, labeled A, B, and C, as stand-ins for any number of them. Instead of their product, he takes the least number they all divide, then adds one unit. Joyce's commentary notes that for distinct primes this least number is the product, though Euclid doesn't say so (Euclid, Elements IX.20). The argument is often retold as a proof by contradiction, as in the MacTutor history (O'Connor and Robertson 2018). Read closely, Euclid's text builds a new number and argues by contradiction at only one step, to show that its prime factor can't be A, B, or C (Euclid, Elements IX.20). Both readings reach the same conclusion.

Why It Is a Landmark

A landmark result is a finding that changed what a field could do or how it reasons. This proof qualifies because a finite argument settles an infinite question. It never examines a large prime. It shows that the act of listing primes always leaves a gap, whatever the list.

That pattern recurs throughout mathematics. Instead of checking cases, you find a property that every case shares. The question about primes was easy to ask and impossible to settle by searching. A few lines of reasoning about remainders settled it for good.

Conclusion

Euclid's argument shows that any finite list of primes leaves at least one prime out, so the primes never run out. The number formed from the list need not be prime, but it always has a prime factor missing from the list. More than two thousand years later, it's still the standard first example of a proof about infinitely many numbers.

Key Terms

Proof: An argument that shows a statement must be true, step by step, from facts already established.
Finite list: A list with a definite number of entries that could, in principle, be written out in full.
Infinitely many: More than any finite count; no finite list contains them all.
Landmark result: A finding that changed what a field could do or how it reasons.

References

Euclid. Elements. Edited and translated by David E. Joyce, after T. L. Heath's edition. Worcester, MA: Clark University, 1996–2013.
- Free: Euclid's Elements, Book IX, Proposition 20 (Joyce)
O'Connor, J. J., and E. F. Robertson. 2018. "Prime Numbers." MacTutor History of Mathematics Archive, University of St Andrews. Last updated January 2018.
- Free: MacTutor: Prime numbers

Guided Reading 7 min Done

Worked Example: Running Euclid's Argument on Real Lists of Primes

Introduction

Euclid's argument says that from any finite list of primes, you can find a prime that isn't on it. Following the argument in words is one thing. Running it on actual numbers shows what it does and doesn't promise. This worked example applies the argument to two lists, checks every result by hand, and ends with a table of what each list produced.

The Problem

A prime is a whole number greater than 1 whose only positive divisors are 1 and itself. Euclid's argument goes like this. Multiply all the primes on a list together, then add 1. The new number leaves remainder 1 when divided by each listed prime, so none of them divides it. Either the new number is prime, or it has a prime factor. Either way, that prime is missing from the list (Euclid, Elements IX.20). The locator IX.20 means Book IX, Proposition 20.

Here are the two lists:

List A: {2, 3, 5}
List B: {2, 3, 5, 7, 11, 13}

For each list, the task is to form the product plus 1, decide whether it's prime, and find at least one prime that isn't on the list. Then you'll say what the two results together show.

Working It Through

Step 1: Multiply the first list and add 1

Multiply the primes in List A: $2 \times 3 \times 5 = 30$ . Add 1 to get 31.

Before testing 31, check the remainders. Dividing 31 by 2 gives 15 with 1 left over. Dividing by 3 gives 10 with 1 left over. Dividing by 5 gives 6 with 1 left over. Every listed prime leaves remainder 1, as the argument says it must. That happens because 30 is a multiple of each listed prime, so the only thing left after dividing is the 1 you added.

Step 2: Check 31 by trial division up to its square root

Trial division means dividing by each prime in turn to see whether any of them goes in evenly. You don't have to try every number below 31. If 31 were a product of two whole numbers, both bigger than 1, at least one of them would be no bigger than the square root of 31. The square root of a number is the value that, multiplied by itself, gives that number. Since $5 \times 5 = 25$ and $6 \times 6 = 36$ , the square root of 31 lies between 5 and 6.

So you only need to test the primes 2, 3, and 5. You've already seen that each leaves remainder 1. None divides 31, so 31 is prime. It isn't on List A. The argument found a new prime directly.

Step 3: Multiply the second list and add 1

Multiply the primes in List B:

2 \times 3 \times 5 \times 7 \times 11 \times 13 = 30{,}030

You can build it up in stages: $30 \times 7 = 210$ , then $210 \times 11 = 2{,}310$ , then $2{,}310 \times 13 = 30{,}030$ . Add 1 to get 30,031.

Step 4: Trial division finds that 30,031 is composite

A composite number is a whole number greater than 1 with a divisor other than 1 and itself. To test 30,031, you need primes up to its square root. Since $173 \times 173 = 29{,}929$ and $174 \times 174 = 30{,}276$ , the square root lies between 173 and 174. So you test primes up to 173.

The primes on List B can't divide 30,031, by the argument. So start with 17, the first prime not on the list. Working upward through 17, 19, 23, 29, 31, 37, 41, 43, 47, and 53, each leaves a remainder. Then try 59:

30{,}031 = 59 \times 509

Check it by multiplying: $59 \times 500 = 29{,}500$ and $59 \times 9 = 531$ , and $29{,}500 + 531 = 30{,}031$ . So 30,031 is composite. The product plus 1 is not prime this time.

Is 509 prime? Its square root lies between 22 and 23, since $22 \times 22 = 484$ and $23 \times 23 = 529$ . Test the primes 2, 3, 5, 7, 11, 13, 17, and 19. None divides 509, so it's prime. And 59 is prime, since no prime up to 7 divides it ( $7 \times 7 = 49$ and $8 \times 8 = 64$ ).

Step 5: Check that the new primes are missing from the list, and that each listed prime leaves remainder 1

Neither 59 nor 509 appears on List B, which stops at 13. So the argument still delivered, twice over.

Now confirm the remainders. Because 30,030 is a multiple of every prime on List B, dividing 30,031 by any of them leaves 1. Dividing 30,030 by 2, 3, 5, 7, 11, and 13 gives 15,015, 10,010, 6,006, 4,290, 2,730, and 2,310, all whole numbers. So, for instance, $30{,}031 = 15{,}015 \times 2 + 1$ and $30{,}031 = 2{,}310 \times 13 + 1$ . The other four divisions work the same way. That's exactly why none of 2, 3, 5, 7, 11, or 13 could be a factor of 30,031.

Step 6: State what the example shows

The two lists behave differently. List A gave a number that is itself prime. List B gave a number that isn't prime, but whose prime factors are both new. That is all Euclid's argument claims. The product plus 1 need not be prime. It always supplies at least one prime missing from the list.

Key Considerations

The common mistake is believing that "the product plus one is always prime." It's an easy slip, because small lists such as {2}, {2, 3}, {2, 3, 5}, and {2, 3, 5, 7} all give primes: 3, 7, 31, and 211. List B is the counterexample. Its product plus 1, 30,031, equals $59 \times 509$ . Euclid never claimed the number is prime, and the argument doesn't need it to be. It needs only that the number has some prime factor, and that no listed prime is that factor.

A second point concerns trial division. You only need to test primes up to the square root, and only primes, not every number. If a composite number divides your number, so does each of its prime factors, and you'd have found one of those already. Without the square-root limit, testing 30,031 would mean trying primes all the way up. With it, you stop at 173.

The lists here happen to be the first few primes in order. Nothing in the argument requires that. Any finite list of primes works, in any order, with gaps or without.

Finally, the argument doesn't tell you which new prime you'll get, and it needn't be the next prime after the list. List A produced 31, skipping every prime from 7 to 29. List B produced 59 and 509, skipping 17 through 53. The argument guarantees that some prime is missing, not which one.

Summary

Running the argument on two lists shows both outcomes it allows: a new number that is prime, and a new number that is composite with new prime factors.

List Product plus 1 Prime or composite New prime(s) found
{2, 3, 5} 31 Prime 31
{2, 3, 5, 7, 11, 13} 30,031 Composite ( $59 \times 509$ ) 59 and 509

List	Product plus 1	Prime or composite	New prime(s) found
{2, 3, 5}	31	Prime	31
{2, 3, 5, 7, 11, 13}	30,031	Composite ( $59 \times 509$ )	59 and 509

Each row's product plus 1 leaves remainder 1 when divided by every prime on its list.
Trial division up to the square root confirmed each verdict.
In both rows, at least one prime missing from the list appears.

References

Euclid. Elements. Edited and translated by David E. Joyce, after T. L. Heath's edition. Worcester, MA: Clark University, 1996–2013.
- Free: Euclid's Elements, Book IX, Proposition 20 (Joyce)

Guided Conversation 12 min Done

Find a Prime Missing From Any List

In this conversation you'll pick a few primes of your own and test what happens when you multiply them and add 1. With hints when you want them, you'll work your way to an argument that no list of primes can ever be complete. You'll leave with that argument stated in your own words.

You'll have this conversation with an AI assistant, using your own account. Choose a button to open a new chat with the prompt already filled in, then press send to start. If the chat opens empty, copy the prompt and paste it in.

Run this conversation in whichever assistant you already use:

Open in Claude Open in ChatGPT

Claude desktop app

To use another LLM, simply copy and paste the prompt into its chat window.

Show the full prompt (it lists misreadings to watch for, so skip it if you would rather come to the conversation fresh)

Guided Conversation: Find a Prime Missing From Any List (about 12 minutes)

Note to the learner: press send to start. Everything below is facilitator guidance for the AI. It lists misconceptions to watch for, so skip it if you'd rather come to the conversation fresh.

Please facilitate a coached problem session with me. I'm an adult who is comfortable with basic high-school algebra but may be rusty or uneasy with math, exploring what number theory is and whether to study it further. I'm studying primes, divisibility, and the proof that the primes never run out. Follow this guidance for the whole conversation.

GOAL
Use divisibility and remainders to reason about whole numbers, reaching, through my own attempts, the argument that for any finite list of primes there is a prime not on the list.

HOW TO RUN THE CONVERSATION
- Ask one question at a time, then wait for my reply. Keep each of your turns under about 120 words.
- Don't lecture. Explain a point only when I need it to continue, then return to my numbers.
- Be curious, collegial, and patient. Give hints and ask questions; don't solve the problem for me. Define terms briefly on first use (prime, divisor, remainder, composite). Welcome disagreement when I give a reason.
- Coaching rules: always ask for my approach before giving any hint. Give one hint at a time, and only after I've tried. Never state the general argument or a final answer before I've attempted it.
- Plain conversation only: don't search the web or create files or documents.
- Aim for about 12 minutes. Spend most of the time on topics 2 and 3. If my replies are brief, offer one concrete prompt, such as "try dividing your number by each prime on your list and tell me what's left over," and move on. If I seem uncertain, shorten the conversation to 5-7 minutes. Always reach the final topic.
- Start now. Open with one or two warm sentences: this is a conversation, not a quiz; trying things and noticing patterns matters more than being right; I can ask you to clarify anything. Then ask me to pick any three prime numbers I like (a prime is a whole number greater than 1 whose only divisors are 1 and itself).

TOPICS, IN ORDER
1. My own list. Ask me to multiply my three primes and add 1, and before I check, to predict whether the result is prime. Then ask how I'd check. If I'm stuck, hint that I only need to try dividing by primes up to the square root. Follow-up: was my prediction right?
2. Remainders. Ask me what remainder each of my listed primes leaves when it divides my new number, and why. Hint, if needed: the product is a multiple of each listed prime, so what's left over is the 1. Ask me to put it in clock terms (on a clock with that many hours, the product lands back at 12, and the extra 1 moves it one step on). Follow-up: so can any prime on my list divide the new number?
3. A composite case. Give me the list 2, 3, 5, 7, 11, 13 and ask me to predict whether the product plus 1 (30031) is prime. If I want help checking, hint that 59 is worth trying. Once I've found 30031 = 59 x 509, ask what I can still conclude about my list. Follow-up: are 59 and 509 on the list, and could they have been?
4. Closing. Ask me to state, in two sentences, why no finite list of primes can be complete. Coach me toward covering both cases: the new number is prime, or it has a prime factor, and either way that prime isn't on the list. This is something I can take into practice with divisibility and remainders.

CORRECT METHOD AND ANSWER
- For any finite list of primes, form N = (product of the list) + 1.
- Each listed prime leaves remainder 1 when it divides N, so no listed prime divides N.
- N is greater than 1, so it is either prime or has a prime factor. In either case that prime is not on the list.
- So every finite list of primes is missing at least one prime, and there are infinitely many primes. This is Euclid's argument, Elements Book IX, Proposition 20, from about 300 BCE.
- Examples: 2 x 3 x 5 + 1 = 31, which is prime. 2 x 3 x 5 x 7 x 11 x 13 + 1 = 30031 = 59 x 509, which is composite; 59 and 509 are both prime and not on the list.
- To test whether a number is prime, it's enough to try dividing by primes up to its square root.

MISCONCEPTIONS TO CORRECT GENTLY
When one appears, name the accurate version briefly, then return to my numbers.
- "The product plus one is always prime": it isn't; 30031 = 59 x 509. The argument only needs a prime factor that's not on the list.
- "Primes eventually stop because they get rare": they do thin out, but they never stop; any finite list leaves one out.
- "You'd need a computer to check": the argument covers every possible list at once, with no checking of large numbers.

LIMITS
- Don't bring in twin primes, the Riemann Hypothesis, or encryption.
- Don't give me the argument before I've tried at least one list of my own.
- Don't introduce notation beyond plain arithmetic.

TO FINISH
After my two-sentence closing statement, close in one short turn:
- Affirm one specific thing I worked out, in my own words where possible.
- Suggest one or two next steps that fit how the conversation went. Possible steps: try a list of four primes and find the new prime it produces; test whether 2 x 3 x 5 x 7 + 1 is prime; review how to find a remainder by hand.
- Restate my two-sentence argument on its own line, labeled "My argument", so I can copy it.

Problem Set 15 minOptional Done

Primes, Factors, and Remainders

Overview

This optional problem set gives you five short problems on divisibility, prime factorization, and clock arithmetic. A prime is a whole number greater than 1 whose only divisors are 1 and itself. Work each problem on paper, showing the division or remainder you used, and check each answer by multiplying back. Then compare your work with the answers and methods given.

Problems

Problem 1

Is 91 prime? If not, write it as a product of two smaller whole numbers.

Once you've tried the problem, check your work against the solution.Show the solution to Problem 1Hide the solution

Answer: No. 91 = 7 × 13.

Method:

To test whether a number is prime, divide by primes up to its square root. Since $9 \times 9 = 81$ and $10 \times 10 = 100$ , the square root of 91 is between 9 and 10. So try 2, 3, 5, and 7.
91 is odd, so 2 doesn't divide it. Its digits add to 10, which isn't a multiple of 3, so 3 doesn't divide it (a whole number is divisible by 3 exactly when its digits add to a multiple of 3). It doesn't end in 0 or 5, so 5 doesn't divide it.
Try 7: $7 \times 13 = 91$ . So 91 is composite.
Check by multiplying back: $7 \times 13 = 70 + 21 = 91$ .

Most common error: deciding 91 is prime because it isn't even and doesn't end in 5. Those checks only rule out 2 and 5.

Problem 2

Write 360 as a product of primes.

Once you've tried the problem, check your work against the solution.Show the solution to Problem 2Hide the solution

Answer: 2^3 × 3^2 × 5 (that is, 2 × 2 × 2 × 3 × 3 × 5).

Method:

Divide by 2 until the result is odd: 360, 180, 90, 45. That's three divisions by 2.
Divide 45 by 3: 15. Divide 15 by 3: 5. That's two divisions by 3.
What remains, 5, is prime.
So $360 = 2^3 \times 3^2 \times 5$ . Check: $8 \times 9 \times 5 = 72 \times 5 = 360$ .

Most common error: stopping at a composite factor, such as writing $360 = 8 \times 45$ . Every factor in a prime factorization must itself be prime.

Problem 3

Today is Monday. What day of the week will it be 100 days from now?

Once you've tried the problem, check your work against the solution.Show the solution to Problem 3Hide the solution

Answer: Wednesday.

Method:

Days of the week repeat every 7 days, so only the remainder on division by 7 matters.
Divide 100 by 7: $100 = 14 \times 7 + 2$ . The remainder is 2.
Fourteen full weeks bring you back to Monday. Two more days take you to Wednesday.
Check: $14 \times 7 = 98$ , and $98 + 2 = 100$ .

Most common error: counting Monday itself as one of the 2 days and answering Tuesday. Day 1 from Monday is Tuesday, and day 2 is Wednesday.

Problem 4

Compute $2 \times 3 \times 5 \times 7 + 1$ and decide whether the result is prime.

Once you've tried the problem, check your work against the solution.Show the solution to Problem 4Hide the solution

Answer: 211, which is prime.

Method:

Multiply: $2 \times 3 = 6$ , $6 \times 5 = 30$ , $30 \times 7 = 210$ . Add 1 to get 211.
Find how far trial division must go. Since $13 \times 13 = 169$ and $17 \times 17 = 289$ , which is more than 211, you need to test primes up to 13.
Each of 2, 3, 5, and 7 leaves remainder 1, because 210 is a multiple of each.
Test 11: $11 \times 19 = 209$ , remainder 2. Test 13: $13 \times 16 = 208$ , remainder 3. No prime up to 13 divides 211, so it's prime.

This doesn't contradict Euclid's argument. The argument says the product plus 1 always has a prime factor not on the list. Here the number is prime itself, and 211 isn't on the list {2, 3, 5, 7}. A product plus 1 can also be composite, such as $2 \times 3 \times 5 \times 7 \times 11 \times 13 + 1 = 30{,}031 = 59 \times 509$ .

Most common error: concluding from this one case that the product plus 1 is always prime.

Problem 5

What is the remainder when $2^{10}$ is divided by 7?

Once you've tried the problem, check your work against the solution.Show the solution to Problem 5Hide the solution

Answer: 2.

Method:

Look for a small power of 2 that leaves remainder 1 on division by 7: $2^3 = 8 = 7 + 1$ . So $2^3$ leaves remainder 1. In modular notation, $2^3 \equiv 1 \pmod 7$ , read "2 cubed is congruent to 1, modulo 7."
Remainders multiply, so $2^9 = 2^3 \times 2^3 \times 2^3$ leaves remainder $1 \times 1 \times 1 = 1$ .
Then $2^{10} = 2^9 \times 2$ leaves remainder $1 \times 2 = 2$ .
Check directly: $2^{10} = 1{,}024$ , and $1{,}024 = 146 \times 7 + 2$ .

Most common error: dividing 10 by 7 and giving remainder 3. The question is about $2^{10}$ , which is 1,024, not about the exponent.

Self-Check

When you're done, check that:

Each factorization multiplies back to the original number.
Each remainder is less than the number you divided by.
You can say in one sentence why your answer to Problem 4 doesn't contradict Euclid's argument.

Knowledge Check 10 min Done

Primes, divisibility, and Euclid's proof that the primes never run out

This ungraded knowledge check assesses your understanding of how number theory reasons about whole numbers. You'll be asked about the history of number theory from Euclid to Gauss, divisibility and prime factorization, modular arithmetic, and Euclid's argument that there are infinitely many primes.

Note: Use this to test yourself, review the feedback on any questions you miss, and retry until you feel confident before moving forward.

5 questions · ungraded · retry as often as you like