Level 4: GCD, LCM and Euclid

Number theory · level 4 of 8 · rough age 11-12 (a guide for parents; anyone can start anywhere)

In level 3 you broke numbers into primes. In this level you compare two numbers: the biggest number that divides both (the greatest common divisor) and the smallest number both divide (the least common multiple). You meet a method from Euclid's Elements, written around 300 BC, that finds the greatest common divisor without factorizing anything and still runs inside computers today, and his proof that the primes never run out. The level ends with perfect numbers, where a question from ancient Greece is still unanswered.

Lesson	You will be able to
Greatest common divisor	Find the GCD by listing factors and from prime factorizations, and use it to simplify fractions and solve sharing problems
Least common multiple	Find the LCM by listing multiples and from prime factorizations, and use it for repeating cycles and adding fractions
GCD × LCM = the product	Explain why gcd(a, b) × lcm(a, b) = a × b, and use it to find one from the other
Euclid's algorithm	Find the GCD of big numbers by repeated division, explain why it works, and draw it as cutting squares from a rectangle
There is no biggest prime	Follow and explain Euclid's proof that the primes go on forever, and say exactly what it does and does not show
Perfect, abundant and deficient numbers	Classify numbers by the sum of their factors, build perfect numbers from Mersenne primes, and know what is still unknown

Previous: Level 3: divisibility · Next: Level 5: clock arithmetic · Number theory topic page