Definition. The greatest common divisor of two integers (not both zero) is the largest integer which divides both of them.
If a and b are integers (not both 0), the greatest common divisor of
a and b is denoted .
(The greatest common divisor is sometimes called the greatest common factor or highest common factor.)
Here are some easy examples:
You were probably able to do the last examples by factoring the
numbers in your head. For instance, to find , you see that 2 is
the only integer bigger than 1 which divides both 4 and 6.
The problem with this approach is that it requires that you factor the numbers. However, once the numbers get too large --- currently, "too large" means "on the order of several hundred digits long" --- this approach to finding the greatest common divisor won't work. Fortunately, the Euclidean algorithm computes the greatest common divisor of two numbers without factoring the numbers. I'll discuss it after I state and prove some elementary properties.
Proposition. Let a and b be integers, not both 0.
(a) .
(b) .
(c) for any integer k.
Proof. (a) Since and
,
must
be at least as big as 1.
(b) if and only if
; that is, a and
have
the same factors. But
is either a or
, so a and
have
the same factors. Likewise, b and
have the same factors. Therefore,
x is a common factor of a and b if and only if it's a common factor
of
and
. Hence,
.
(c) First, if x is a common factor of a and b, then
and
. Then
, so
. Thus, x is a
common factor of
and b.
Likewise, if x is a common factor of and b, then
and
. Hence,
Thus, x is a common factor of a and b.
Therefore, these two sets are the same:
Since the two sets are the same, their largest elements are the same.
The largest element of the first set is , while the largest
element of the second set is
. Therefore,
.
Example. Use the property to
compute
.
Part (c) of the proposition says that the greatest common divisor remains unchanged if you add or subtract a multiple of one of the numbers from the other. You can often use this to simplify computations of greatest common divisors. For example,
Now , and the only positive integers which divide 2 are 1
and 2. So
is either 1 or 2. But 2 and 996 are obviously both
divisible by 2, so
. Therefore,
.
Example. Prove that if , then
.
By part (c) of the proposition,
Now , but the only positive integer which divides 1 is 1.
So
, and hence
.
Definition. a and b are
relatively prime if .
For example, 49 and 54 are relatively prime, but 25 and 105 are not.
Proposition. If , then
.
Proof. Suppose and
. Then
Suppose that and
,
. Then I can find e and f such
that
Thus,
This shows that is a common factor of m and n. Since d is the
greatest common factor,
. Therefore,
,
so
(since p was a positive integer).
I've proven that 1 is the only positive common factor of a and b. Therefore, 1 is the greatest common factor of a and b:
Euclidean Algorithm. Begin with a pair of
nonnegative integers , not both 0.
(The absolute value property I stated earlier shows that there's no harm in assuming the integers are nonnegative.)
1. If one of the numbers is 0, the other is the greatest common divisor of the pair. (Stop.)
2. Otherwise, apply the Division Algorithm to write , where
.
3. Replace the pair with the pair
.
4. Go to step 1.
At each step, both elements are , and each pass through step 3
decreases the second element. Since the second element always gets
smaller, but can't be negative, Well-Ordering implies that algorithm
must terminate in an
pair (in step 2) after a finite number of
steps.
I get the next pair of numbers by subtracting a multiple of one of the previous numbers from the other. Therefore, each pair of numbers has the same greatest commmon divisor as the previous pair. Considering the whole chain of pairs, it follows that the original pair of numbers and the last pair of numbers have the same greatest common divisor.
The original pair of numbers is , and their greatest common
divisor is
. The last pair of numbers is
and
. Thus,
--- in words, the greatest common divisor is the
last nonzero remainder.
Example. Use the Euclidean algorithm to
compute .
Here what the algorithm above says. You start with the original numbers. Think of them as the first two "remainders". At each step, you divide the next-to-the-last remainder by the last remainder. You stop when you get a remainder of 0. Here are the divisions:
(Start by dividing the bigger number by the smaller number, or else you'll just waste a step.)
It's easier to remember this visually by arranging the computations in a table. Compare the numbers above to the numbers in the following table:
(The next remainder is 0, so I didn't write it.) The successive remainders go in the a-column. The successive quotients go in the q-column.
The greatest common divisor is the last nonzero
remainder, so .
Later on, I'll add another column to this table when I discuss the
Extended Euclidean algorithm.
Example. Compute .
From the table, I see that .
To compute the greatest common divisor of more than two divisors, just compute the greatest common divisor two numbers at a time.
Example. Compute .
The next result is extremely important, and is often used in proving things about greatest common divisors. First, I'll recall a definition from linear algebra.
Definition. If x and y are numbers, a linear combination of x and y (with integer coefficients) is a number of the form
For instance, shows that 29 is a linear
combination of 10 and 9.
shows that 7 is a
linear combination of 10 and 9 as well.
Theorem. is the smallest positive linear
combination of m and n. In particular, there are integers a and b
(not necessarily unique) such that
For example, I showed above that . The theorem says that
there are integers a and b such that
In fact,
This combination is not unique. For example,
We'll discuss later how you find numbers which give a linear combination.
I'll give a few easy corollaries before proving the theorem.
Corollary. The set of all linear combinations
of integers m and n is the set of all multiples of .
Proof. On the one hand,
So every linear combination of m and n is a multiple of .
On the other hand,
That is, every multiple of is a linear combination of m and
n.
Let's look at some specific numbers. I have , so the
theorem asserts that the set of all linear combinations of 42 and 105
--- that is, the set of all numbers of the form
--- is the
set of all multiples of 21:
Notice that the greatest common divisor is the smallest positive element of this set.
If you know a little group theory, you may recognize this as the result that subgroups of cyclic groups are cyclic.
Corollary. If and
, then
.
Proof.
Therefore, and
, then
.
This says that the greatest common divisor is not only "greatest" in terms of size; it's also "greatest" in the sense that any other common factor must divide it.
Corollary. m and n are relatively prime if and only if
Proof. ( ) Suppose m and
n are relatively prime. Then
. By the theorem,
Therefore,
( ) Suppose
Since and
,
The only positive integer that divides 1 is 1, so .
Example. Prove that if , then
.
I'll produce a linear combination of and
which is equal to
1. An easy thing to try is to switch the "3" and
"2" and negate one of them, in order to get the terms with
n to cancel. In fact, that works:
Note: You can't always do this kind of "switch and negate"
trick: Sometimes coming up with a linear combination is more work.
And there are other ways to show two numbers are relatively
prime.
Proof of the theorem. I'll use the Euclidean algorithm. At each step in the Euclidean algorithm, I replace an old pair of numbers with a new pair of numbers. The proof will go this way.
(a) The first two numbers m and n are linear combinations of m and n.
(b) At each step, if the old numbers are linear combinations of m and n, then so are the new numbers.
(c) By (a) and (b), the last two numbers in the algorithm must be linear combinations of m and n.
(d) The last two numbers in the algorithm are and 0. Therefore,
is a linear combination of m and n.
Of these four steps, all are clear except the second. So here is the proof of step (b).
Suppose that my old numbers are , and suppose that they're
linear combinations of m and n:
To do the Euclidean algorithm I divide x by y:
The new numbers are
Each of the new numbers is a linear combination of m and n.
This proves step (b), and the four steps above show that is
a linear combination of m and n. Next, I have to show that it's the
smallest positive linear combination of m and n.
Suppose p is a positive linear combination of m and n:
and
, so
. Both of
these numbers are positive, so
. Since
is smaller than any
positive linear combination of m and n,
must be the
smallest positive linear combination of m and n.
Another way to prove this result is to give an algorithm which constructs a linear combination: the Extended Euclidean Algorithm.
Copyright 2019 by Bruce Ikenaga