"Prove the GCD Exists" or "Factorisation is Unique" — Cue Well-Ordering or Induction

Some number theory questions sound bizarre at first. "Prove the greatest common divisor of two positive integers exists." Doesn't it obviously exist? You can just find it. "Prove prime factorisation is unique." Of course 12 = 2 \cdot 2 \cdot 3 and there's no other way. But when you try to prove these statements without invoking intuition, you hit a wall. What you need is a foundational principle — one of two closely related tools: the well-ordering principle or induction (including strong induction). Recognising when a problem is secretly asking for one of these is a reflex worth cultivating. Once you see the cue, the proof structure almost writes itself.

The cue: "exists" or "unique" over the integers

Here's the signature. Any of these phrasings is a strong hint that well-ordering or induction is the right tool:

"Prove there exists a smallest / largest / greatest positive integer such that ..."
"Show that the GCD of two positive integers exists."
"Prove that every integer n \geq 2 can be factored into primes."
"Show that prime factorisation is unique."
"Prove every non-empty set of positive integers has a smallest element."
"Show that the algorithm terminates — some counter eventually hits zero."

The word "exists" or "every" over the positive integers is the giveaway. So is "prove uniqueness". These are not computational questions — they are structural questions about \mathbb{Z}_{>0}. The structural guarantee you lean on is:

Well-Ordering Principle

Every non-empty set of positive integers has a smallest element.

That is the axiom. It sounds almost too obvious to be useful, but it is precisely the statement that distinguishes the integers from, say, the positive rationals (where the set \{1, \tfrac{1}{2}, \tfrac{1}{3}, \ldots\} has no smallest element). Every existence proof in elementary number theory ultimately rests on it.

Tool A: Well-ordering to prove existence

When to use it: you need to prove that some positive integer with a desired property exists. Show the set of such integers is non-empty, then apply well-ordering to pick the smallest.

Template:

Let S be the set of positive integers with property P.
Exhibit at least one element of S (so S \neq \emptyset).
By well-ordering, S has a smallest element d.
Show d has whatever additional property the problem asks for.

Example: GCD exists

Prove that every pair of positive integers a, b has a greatest common divisor.

This is exactly the pattern. Define

S = \{ax + by : x, y \in \mathbb{Z}, \; ax + by > 0\}.

S is non-empty (take x = 1, y = 0 so a \in S), and all its elements are positive integers. By well-ordering, S has a smallest element d. Two things must be shown: (i) d divides both a and b (so d is a common divisor), and (ii) any common divisor of a and b divides d (so d is the greatest).

Why (i): divide a by d to write a = qd + r with 0 \leq r < d. Then r = a - qd = a - q(ax + by) = a(1 - qx) + b(-qy), so r is a linear combination of a and b. If r > 0, then r \in S and r < d — contradicting that d is the smallest element. So r = 0, i.e. d \mid a. Same for b.

Why (ii): if e \mid a and e \mid b, then e divides every linear combination ax + by, so e \mid d. Hence d \geq e, which means d is the greatest.

Existence + maximality — both fall out of one well-ordering argument. Bezout's identity (d = ax + by) comes as a bonus, because d was defined as such a combination.

Tool B: Strong induction to prove "every n has property P"

When to use it: you need to prove a statement for every integer n \geq n_0, and the truth of the statement at n depends on smaller values. Strong induction (also called complete induction) lets you assume the statement holds for all values less than n, then prove it at n.

Template:

Base case: verify P(n_0) holds.
Inductive step: assume P(k) holds for every k with n_0 \leq k < n, and prove P(n).
Conclude: P(n) holds for every n \geq n_0.

Example: Existence part of the Fundamental Theorem

Prove that every integer n \geq 2 is a product of primes.

Base: n = 2 is prime, so it is a product of primes (trivially, a product of one prime).

Inductive step: suppose every integer k with 2 \leq k < n is a product of primes. Consider n.

If n is prime, it is its own product of primes. Done.
If n is composite, n = ab with 2 \leq a, b < n. By the inductive hypothesis, both a and b are products of primes. Their product n = ab is also a product of primes.

By strong induction, the statement holds for every n \geq 2.

That is a complete, rigorous proof in six lines. Without the strong-induction reflex, it looks like a hard problem. With the reflex, it is a template exercise.

Example: Uniqueness part of the Fundamental Theorem

Uniqueness needs a different kind of induction — it uses Euclid's lemma plus induction on the number of primes in a hypothetical second factorisation. The cue is the same ("prove uniqueness") but the induction is applied to the length of a factorisation rather than to n itself. When a uniqueness problem has this shape — "two representations must coincide" — try induction on the size (length / number of terms / maximum exponent) of the representation.

Well-ordering and induction are two sides of the same coin

They are logically equivalent. In practice:

Use well-ordering when the natural move is to pick the smallest element of a set and derive a contradiction or a property.
Use (strong) induction when the natural move is to propagate a property from smaller values to larger.

Many proofs can be written either way. The one on GCD existence above is a well-ordering proof; you could rewrite it as induction on \max(a, b). Pick whichever frame feels lighter for the particular problem.

step:

A compact worked example

Problem: Show that $\sqrt{2}$ is irrational, using well-ordering

A square root irrationality proof is a classic well-ordering argument.

Assume for contradiction that \sqrt{2} = p/q with p, q positive integers. Let

S = \{n \in \mathbb{Z}_{>0} : n \sqrt{2} \in \mathbb{Z}\}.

S is non-empty (it contains q, since q \sqrt{2} = p \in \mathbb{Z}). By well-ordering, S has a smallest element m. Let k = m \sqrt{2} \in \mathbb{Z}.

Now consider m' = k - m = m(\sqrt{2} - 1). Since 1 < \sqrt{2} < 2, we have 0 < \sqrt{2} - 1 < 1, so 0 < m' < m.

Why: \sqrt{2} \approx 1.414, so \sqrt{2} - 1 \approx 0.414. Multiplying by m gives a positive number strictly less than m.

And m' \sqrt{2} = m(\sqrt{2} - 1)\sqrt{2} = 2m - m\sqrt{2} = 2m - k \in \mathbb{Z}.

So m' \in S and m' < m — contradicting that m is the smallest. Hence \sqrt{2} cannot be rational.

The proof is short, slick, and uses well-ordering as the engine. The cue — "prove \sqrt{2} is irrational", an existence-style claim (no p/q exists) — is what pointed us to well-ordering.

What to not do

Don't try to compute the GCD or factorisation by hand and declare "therefore it exists". A single example is not a proof for all inputs. Use well-ordering or induction.
Don't forget the inductive hypothesis. Many students write the inductive step without carefully stating what they're assuming about smaller values.
Don't neglect the base case. Induction without a base case is a chain with no anchor.

The one-line mental trigger

See "exists" or "every" or "unique" over the positive integers? Reach for well-ordering if you're picking a smallest element, or strong induction if you're propagating a property from smaller values. Both rest on the same foundation — the well-ordering of \mathbb{Z}_{>0}.