The Art and Craft of Problem Solving

7.1 PRIMES AND DIVISIBILITY 225

Let a and b be positive integers, b 2 a. Then there exist integers q, r satis­

fying q 2 1 and 0 ::; r < a such that

b = qa +r.

(a) If you haven't proven this yet, do so now (use the extreme principle).

(b) Show by example that the division algorithm does not hold in the number system

E defined in Example 7.1. 2 on page 223. Why does it fail? What is E missing

that Z has?

7.1. 5 An important consequence of the division algorithm, plus 7.1 .3(d), is that

The greatest common divisor of a and b is the smallest positive linear com­
bination of a and b.
For example, ( 8 ,1 0 ) = 2, and sure enough, if x, y range through all integers (pos­
itive and negative), the smallest positive value of 8x + 10 y is 2 (when, for example,
x = - 1 ,y = 1). Another example: 7 .-l 11 , which means there exist integers x, y such
that 7 x + lly = 1. It is easy to find possible values of x and y by trial and error;
x = -3, y = 2 is one such pair.

Let's prove 7.1.5; it is rather dry but a great showcase for the use of the extreme
principle plus argument by contradiction. Define u to be the smallest positive linear
combination of a and b and let g := (a,b). We know from 7.1 .3(d) that g divides any
linear combination of a and b, and so certainly g divides u. This means that g ::; u. We
would like to show that in fact, g = u. We will do this by showing that u is a common
divisor of a and b. Since u is greater than or equal to g, and g is the greatest common
divisor of a and b, this would force g and u to be equal.
Suppose, on the contrary, that u is not a common divisor of a and b. Without loss
of generality, suppose that u does not divide a. Then by the division algorithm, there
exists a quotient k 2 1 and positive remainder r < u such that

a = ku +r.

But then r = a -ku is positive and less than u. This is a contradiction, because r is also
a linear combination of a and b, yet u was defined to be the smallest positive linear
combination! Consequently, u divides a, and likewise u divides b. So u is a common
divisor; thus u = g. •

This linear combination characterization of the GCD is really quite remarkable,
for at first one would think that PPFs are needed to compute the GCD of two numbers.
But in fact, computing the GCD does not rely on PPFs; we don't need 7 .1.3(b) but can
use 7.1. 5 instead. In other words, we do not need to assume the truth of the FTA in
order to compute the GCD.

7.1.6 Here is another consequence of 7.1.5:

If p is a prime and plab, then pia or plb.

We shall prove this without using the FTA. Let us argue by contradiction. Assume

that p divides neither a nor b. If p does not divide a, then p .-l a, since p is a prime.