218 METHODS OF MATHEMATICAL PROOF, PART II Chapter 6One such axiom is the least upper bound axiom for R, stated in Exercise 10.
Another axiom is the well-ordering principle for the set N of all positive
integers. This axiom asserts that every nonempty subset of N has a smallest
element. One interesting and nontrivial application of the well-ordering
principle is the proof that any pair of integers m and n, not both zero, have
a greatest common divisor.EXAMPLE 10 An integer d is called a greatest common divisor of integers
m and n if and only if (i) d 2 0, (ii) d 1 m and d 1 n, and (iii) for all c E Z, if
c 1 m and c 1 n, then c 1 d. Prove that if m and n are integers, not both zero,
then a greatest common divisor of m and n exists.
Solution Consider the set S consisting of all integers of the form mx + ny,
where x and y are integers. Clearly S must contain some positive integers
and so, by the well-ordering principle, must contain a smallest positive
integer, let us call it d. Since d E S, then d = mx, + ny, for some integers
x, and y,. Our claim is that d satisfies conditions (i), (ii), and (iii) of the
definition of greatest common divisor of m and n.
Now property (i) is true by definition of d and (iii) is proved easily as
follows. If c 1 m and c 1 n, then c 1 mx, and c 1 ny, so that c l(mx, + ny,) = d,
thus cld (recall the results of Example 2 and Exercise 2, Article 6.1).
Property (ii) is the most difficult to prove, since its proof depends on the
well-known division algorithm for the set Z of integers (which states
"given any integers m and d with d > 0, there exist unique integers q
and r such that m = dq + r, with 0 5 r < d.") To prove that d lm, apply
this theorem to the integers m and d at hand to get integers q and r such
that m = dq + r, 0 I r < d. But then m = (mx, + ny,)q + r, so that r =
m(l - x,q) + n(-qy,), which is the appropriate form for membership in
S. Hence r E S; but 0 I r < d and d is the smallest positive element of
S, so that r = 0. Hence m = dq so that d lm, as desired. An identical
argument establishes that d 1 n.
We conclude that this d, constructed from the set S by means of the
well-ordering principle, is a greatest common divisor of m and n.-- - In Exercise 9 you are asked to show that the greatest common divisor
of two integers is unique. If m and n are integers, not both zero, this unique
positive integer corresponding to m and n is usually denoted by the symbol
(m, 4.
Study the proof in Example 10 carefully. The proof is, on the one hand,
direct [i.e., (m, n) is derived directly from m and n, without recourse to any
argument by indirect method] and yet is abstract, in that an actual greatest
common divisor for the given m and n is not produced explicitly [i.e., the
proof does not tell us how to calculate the value of (m, n) for given specific
values of m and n.]. The crux of the proof is the idea of considering the
set S and applying the well-ordering principle to it. Keep this approach
in mind when doing exercises such as 9(d), 10(a), and 1 l(a).