Discrete Mathematics: Elementary and Beyond

100 6. Integers, Divisors, and Primes

The trouble with this method is that it is very difficult to find the prime
factorization of large integers. The algorithm to be discussed in this sec-
tion will compute the greatest common divisor of two integers in a much
faster way, without finding their prime factorizations. This algorithm is an
important ingredient of almost all other algorithms involving computation
with integers. (And, as we see it from its name, it goes back to the great
Greek mathematician Euclid!)

6.6.1Show that ifaandbare positive integers witha|b, then gcd(a, b)=a.

6.6.2 (a) Prove that gcd(a, b) = gcd(a, b−a).

(b) Letrbe the remainder if we dividebbya. Then gcd(a, b) = gcd(a, r).

6.6.3 (a) Ifais even andbis odd, then gcd(a, b) = gcd(a/ 2 ,b).

(b) If bothaandbare even, then gcd(a, b) = 2gcd(a/ 2 ,b/2).

6.6.4How can you express the least common multiple of two integers if you
know the prime factorization of each?

6.6.5Suppose that you are given two integers, and you know the prime factor-
ization of one of them. Describe a way of computing the greatest common divisor
of these numbers.

6.6.6Prove that for any two integersaandb,

gcd(a, b)lcm(a, b)=ab.

6.6.7Three integersa,b, andcform aPythagorean tripleifa^2 +b^2 =c^2.

(a) Choose any three integersx,y, andz, and leta=2xyz,b=

x^2 −y^2



z,

c=

x^2 +y^2



z. Check that (a, b, c) is a Pythagorean triple.

(b) Prove that all Pythagorean triples arise this way: Ifa, b, care integers such

thata^2 +b^2 =c^2 , then there are other integersx,y, andzsuch thata,b,

andccan be expressed by the formulas above.

[Hint: First, show that the problem can be reduced to the case where

gcd(a, b, c)=1,ais even, andb,care odd. Second, writea^2 =(b−c)(b+c)

and use this to argue that (b+c)/2 andb−c)/2 are squares.]

Now we turn to the Euclidean Algorithm. It is based on two simple facts,
already familiar as Exercises 6.6.1 and 6.6.2.
Suppose that we are given two positive integersaandb, and we want to
find their greatest common divisor. Here is what we do:

1. Ifa>bthen we interchangeaandb.


2. Ifa>0, dividebbya, to get a remainderr. Replacebbyr and
   return to 1.