184 Normat 58:4, 184 (2010)
Euclid’s Lemma Revisited
Marc Bezem
Department of Informatics, University of Bergen
P.O. Box 7803, N-5020 Bergen, Norway
bezem@ii.uib.no
In [2], Peter Walker rightly underlines the importance of a self-contained proof of
Euclid’s lemma [1], which states that a prime divides at least one of two integers
when dividing their product. Walker proposes an inductive proof of Euclid’s lemma,
not using Bezout’s identity. Walker’s proof is interesting since it uses induction
on the prime. His proof actually contains several other inductions, namely the
induction behind division with remainder, behind existence of factorisation and
behind cancellation of an unknown number of common factors.
Here we take a further step by giving an inductive argument that bypasses
all of the above inductions and auxiliary results. Our proof only uses elementary
arithmetic and logic, in addition to one main induction in the natural numbers,
based on a seemingly original induction value. The base case holds vacuously.
Let p | ab with p a prime and a, b positive integers. We will call the value of
the expression pab + min(a, b) the induction value of p | ab, or i-value for short.
We will prove by well-founded induction on the i-value that p | ab implies p | a or
p | b. Let p | ab with p prime and assume Euclid’s lemma holds for all p
0
| a
0
b
0
, p
0
prime, with i-value smaller than that of p | ab. Without loss of generality we can
assume that 1 < a ≤ b, as both Euclid’s lemma and the i-value are symmetric in
a and b. If a > p we are done since p | (a − p)b has smaller i-value than p | ab,
and p | a − p implies p | a. The case p = a is trivial, so assume 1 < a ≤ p − 1.
We distinguish two cases: a is composite and a is prime. If a is comp osite, that is,
a = a
1
a
2
with 1 < a
1
, a
2
< a, then p | a
1
(a
2
b) has a smaller i-value than p | ab, since
min(a
1
, a
2
b) < min(a, b). If p | a
1
, then p | a and we are done, so assume p | a
2
b. In
turn, p | a
2
b has a smaller i-value than p | ab. In both cases, p | a
2
(which implies
p | a) or p | b, we are done. It remains to treat the case that a is prime. Let q be
such that pq = ab and assume a ≤ p − 1 is prime. Then we have a | pq, with i-value
apq+min(p, q) ≤ (p−1)pq+min(p, q) = ppq−pq+min(p, q) ≤ pab < pab+min(a, b).
It follows that a | q since a | p is impossible. Let q
0
be such that q = aq
0
, then we
have paq
0
= pq = ab, so pq
0
= b, which means p | b.
References
[1] Euklid, The Elements. Book VII, Proposition 30,
http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/propVII30.html
[2] Peter Walker, A Lemma on Divisibility. American Mathematical Monthly
115(4):338.
