Engineering / Mathematics — Integer Foundations
Ideals and Greatest Common Divisors of Integers
Greatest common divisors defined through ideals, Bezout's identity, and why the ideal-theoretic view is the one that generalises.
Executive summary
The greatest common divisor can be defined in two ways: as the largest common divisor, or as the generator of the ideal formed by all integer combinations. The second definition looks more abstract and is considerably more useful.
It yields Bezout's identity immediately, it makes the key lemma about primes dividing products almost trivial, and it is the definition that survives when one moves from the integers to polynomial rings and beyond.
Learning objectives
- Define ideals in the integers and prove every such ideal is principal.
- Derive Bezout's identity from the ideal characterisation.
- Apply Euclid's lemma and explain its role in unique factorisation.
01Ideals of the integers
Ideal
A subset I of Z is an ideal if it is closed under addition and under multiplication by arbitrary integers: if x, y ∈ I and c ∈ Z then x + y ∈ I and cx ∈ I.
The set of all integer combinations {ax + by : x, y ∈ Z} for fixed a, b is an ideal, and it is the object that defines the gcd.
Every ideal of Z is principal
Every ideal I of Z has the form dZ for a unique d ≥ 0.
Proof sketch. If I = {0} take d = 0. Otherwise I contains a positive element; let d be the least. Division with remainder writes any x ∈ I as x = dq + r with 0 ≤ r < d, and r = x − dq ∈ I, so minimality forces r = 0.
02The greatest common divisor
Greatest common divisor
gcd(a, b) is the unique non-negative generator d of the ideal {ax + by : x, y ∈ Z}.
Equivalently, d is a common divisor of a and b divisible by every common divisor.
The equivalence of the two descriptions is worth pausing on. The ideal definition makes d a common divisor because a and b lie in the ideal, and makes every common divisor divide d because d is an integer combination of a and b.
Bezout's identity
For any integers a, b there exist integers s, t with
as + bt = gcd(a, b).
Bezout's identity is a direct restatement of the ideal characterisation, not a separate theorem. Its computational content — actually producing s and t — is supplied by the extended Euclidean algorithm.
03Euclid's lemma
Euclid's lemma
If p is prime and p | ab, then p | a or p | b.
Proof. Suppose p ∤ a. Since p is prime, gcd(p, a) = 1, so by Bezout there are s, t with ps + at = 1. Multiplying by b gives psb + abt = b. Now p divides both terms on the left — the first visibly, the second because p | ab — so p | b.
This lemma is the crux of unique factorisation. Without it, one can prove that every integer factors into primes but not that the factorisation is unique, and the two-line proof above is only available because the gcd was defined ideal-theoretically.
| Property | Statement |
|---|---|
| Commutativity | gcd(a, b) = gcd(b, a) |
| Associativity | gcd(a, gcd(b, c)) = gcd(gcd(a, b), c) |
| Identity | gcd(a, 0) = |a| |
| Scaling | gcd(ca, cb) = |c| · gcd(a, b) |
| Coprime shift | gcd(a, b) = gcd(a, b + ka) for any integer k |
The coprime shift property is what licenses the Euclidean algorithm: replacing b by its remainder modulo a leaves the gcd unchanged while strictly reducing size.
04Frequently asked questions
Why define the gcd through ideals rather than as the largest common divisor?
Because the ideal definition proves Bezout's identity for free, and Bezout is what makes Euclid's lemma provable. The 'largest common divisor' definition is easier to state but leaves unique factorisation genuinely difficult to establish.
Does the ideal definition still work when one argument is zero?
Yes, and this is one of its advantages. The ideal generated by a and 0 is aZ, so gcd(a, 0) = |a| falls out of the definition rather than needing a special case.
Are the Bezout coefficients unique?
No. If as + bt = d then so does (s + kb/d, t − ka/d) for any integer k. The extended Euclidean algorithm returns a particular pair with small magnitude, which is the useful normalisation in practice.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 4-8.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.