Divisibility, Euclid's algorithm and unique factorisation

Builds on

Required prerequisites, all the way down: 11

You will learn to

• Compute gcd(a, b) with Euclid's algorithm and express it as ax + by.
• Prove Euclid's lemma: if a prime p divides ab, then p divides a or p divides b.
• Prove the existence and uniqueness of prime factorisation.

Definition

• a | b means b = ak for some integer k.
• gcd(a, b), for a and b not both zero, is the greatest integer dividing both.
• Integers a and b are coprime if gcd(a, b) = 1.

Theorem

• Bézout: if a and b are not both zero, there are integers x and y with ax + by = gcd(a, b).
• Euclid's lemma holds for every prime p.
• Fundamental theorem of arithmetic: every integer n > 1 is a product of primes, uniquely apart from order.
• Euclid's algorithm terminates because the remainders strictly decrease.

Common misconceptions

• Thinking unique factorisation is obvious; it fails in some number systems and needs proof.
• Assuming that if d divides ab then d divides a or b when d is not prime; 4 divides 2 · 2 but not 2.
• Confusing the greatest common divisor with the least common multiple.

Leads to

Optional discoveries

• Rings, ideals and fields Euclid's algorithm works in any Euclidean domain, such as polynomials over a field or the Gaussian integers ℤ[i], which therefore also have unique factorisation.
• Algorithms, correctness and efficiency Lamé's theorem: the number of division steps in Euclid's algorithm is at most five times the number of decimal digits of the smaller number.

Further reading

• G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers (1938)
• Ivan Niven, Herbert S. Zuckerman and Hugh L. Montgomery, An Introduction to the Theory of Numbers