Level 6: Equations in whole numbers

Number theory · level 6 of 8 · rough age 13-14 (a guide for parents; anyone can start anywhere)

This level solves equations where only whole numbers are allowed as answers. One tool does almost all the work: Bézout's identity, which says the gcd of two numbers can be built from them by adding and subtracting, and which you get by running Euclid's algorithm backwards. With it you will pay exact amounts with stamps and coins, divide on a clock, solve a puzzle from a Chinese book written over 1500 years ago, and finally prove that every number has only one prime factorisation.

Lesson	You will be able to
Bézout's identity	Write \(\gcd(a, b)\) as \(ax + by\) with extended Euclid, prove that this is always possible, and say which numbers \(ax + by\) can make
Linear Diophantine equations	Decide whether \(ax + by = c\) has whole-number solutions, find one, and write down all of them
The coin problem	Find which amounts two coprime coins can pay, prove the largest impossible amount is \(ab - a - b\), and count the impossible ones
Inverses mod n	Find inverses on a clock, know exactly when they exist, solve \(ax \equiv b \pmod n\), and meet Wilson's theorem
The Chinese remainder theorem	Solve several clock equations at once in three ways, and explain why the answer is unique mod the product
Unique factorisation, proved	Prove Euclid's lemma from Bézout, prove the fundamental theorem of arithmetic, and use it to show \(\sqrt 2\) is irrational

Previous: Level 5: Clock arithmetic · Next: Level 7: Powers on a clock · Number theory topic page