History of primes and factors: Euclid and Eratosthenes

Lessons and exercises follow the school system and stay in its language.Les leçons et les exercices suivent le système scolaire et restent dans sa langue.Lektionen und Übungen folgen dem Schulsystem und bleiben in seiner Sprache.

About this lesson

Grade 6 › Rational numbers

To save a PDF, choose “Save as PDF” in the print dialog.

Sources and credits

Written with this source as a starting point:

sedifier rewrote the text and added its own examples and exercises.

Written with AI assistance; every answer is checked by our math engine. Not yet reviewed by a teacher.

This lesson: CC BY-SA 4.0, © sedifier · All credits

History of primes and factors: Euclid and Eratosthenes

Rational numbers. negative numbers, absolute value, coordinate plane, quadrants, greatest common factor, least common multiple

Discover

To find all primes up to 100, Eratosthenes (276–194 BC) had a simple trick. What do you think it was?

  1. Cross out the multiples of 2, then of 3, of 5, of 7…: what is left is prime
  2. Test every number by dividing it by all smaller numbers

Key idea

Primes, factors and multiples in history.

350 BCE300 BCE250 BCE200 BCE150 BCEc. 300 BCEEuclidc. 300 BCEEuclid
  1. Step 1350 BCE300 BCE250 BCE200 BCE150 BCEc. 300 BCEEuclidc. 300 BCEEuclidEuclid c. 300 BCImagined portraitUnknown artist. Public domainAbout 300 BC: Book VII of the Elements and the Euclidean algorithm.
  2. Step 2350 BCE300 BCE250 BCE200 BCE150 BCEc. 300 BCEEuclidc. 235 BCEEratosthenesc. 300 BCEEuclidc. 235 BCEEratosthenesEratosthenes c. 276 – c. 194 BCImagined portraitUnknown artist. Public domainEratosthenes (276–194 BC): the prime number sieve.

Book VII of Euclid's Elements (about 300 BC) is an introduction to number theory and contains the Euclidean algorithm for the greatest common divisor. Eratosthenes of Cyrene (276–194 BC), who also measured the Earth, is remembered for his prime number sieve.

Source

Prime numbers are more than any assigned multitude of prime numbers.

Euclid, Elements, book IX, proposition 20, about 300 BC, in the translation by T. L. Heath (1908, public domain)

What does Euclid claim here?

  1. There is no largest prime: the primes never run out
  2. There are exactly as many primes as he listed

Worked example

Euclid's algorithm for the GCF of 84 and 36.

replace (84, 36) by (36, 12)
84=2×36+1284 = 2 \times 36 + 12.
GCF =12= 12
36=3×12+036 = 3 \times 12 + 0.

Practice ★

  1. What is Eratosthenes remembered for in number theory?
    1. His prime number sieve
    2. The algorithm for the GCF
    3. Negative numbers
  1. First step of Euclid's algorithm: find the remainder when 42 is divided by 9.
  2. First step of Euclid's algorithm: find the remainder when 271 is divided by 33.
  1. Sieve of Eratosthenes on the numbers 1 to 42: after crossing out the multiples of 2 (except 2 itself), how many numbers are left?

Summary card

Primes and factors today

  • Online payments are protected by codes built from huge primes.
  • Fractions are simplified by dividing by the GCF.
  • Calendars and gears repeat after an LCM.

Sources: MacTutor biographies of Euclid and Eratosthenes (see "Sources and credits").

End of the lesson

Sources and credits

Written with this source as a starting point:

sedifier rewrote the text and added its own examples and exercises.

Written with AI assistance; every answer is checked by our math engine. Not yet reviewed by a teacher.

This lesson: CC BY-SA 4.0, © sedifier · All credits