To reduce the fraction a/b to lowest terms, it would be necessary to
divisor of a and b. This is simply called gcd(a, b). This computation is very
the numerator and denominator are large. For example, how would you reduce the
28, 841/33, 043 to lowest terms? The method we now show handles this problem
and was first d one by Euclid . The technique is called the Euclidean Algorithm.
Lemma 1.5 Let a = bq + r. Then any divisor of both a and b is also a divisor of
b and r.
Conversely, any divisor of both b and r is also a divisor of a and b. Thus gcd(a,
b) = gcd(b, r).
Proof: First, suppose d|a and d|b. Then since r = a − bq, we have d|r since r is
combination of a and b. Thus d|b and d|r.
Conversely, if d|b and d|r, then since a = bq + r is a linear combination of b
and r, we see
that d|a and so d|a and d|b. This proves the result.
In words, gcd(a, b) can be found by finding the remainder r when a is divided by b
computing gcd(b, r). We then use the same result to simplify gcd(b, r), and
we find the answer. Let's use this method to find gcd(75, 55). (Of course this can
be done by most students, but let's illustrate the method.) Dividing, we have
using the above theorem successively, and the fact that gcd(a, 0) = a when a >
0. This is
a general technique. Instead of finding gcd(a, b) we find the remainder r when a is
by b and find gcd(b, r). We keep repeating the process until the remainder is 0,
the last non- zero remainder is the required gcd. As noted above, this technique
the Euclidean Algorithm. For simplicity, we have as sumed that a and b arepositive in
this statement of the Euclidean algorithm, and we will often make this
assumption in what
We can now reduce 28, 841/33, 043 to lowest terms! The following table
the numerator, denominator, quotient and remainders in the Euclidean Algorithm.
The gcd is 191. Note that in each line, the numbers move over one to the left,
quotients are ignored. Finally, we reduce to lowest terms:
The Euclidean Algorithm computation will be done automatically in the lab, using
spreadsheet called GCD.
Many facts about number theory were simply told to us at an early age, and so we
them for granted. For example, suppose you know that 5|7x. Does it follow that
were taught to think somewhat as follows:
is a whole number, and so there must be cancelations. There is no cancelation
of 5 with 7, so all the cancelations are with x, and so 5| x.
Here, the result is true, but the reasoning is suspect. Here is a real proof :
We are given that 5|7x. Also 5|5. Therefore by the linear combination theorem,
5|(3 ٠ 7x − 4x ٠ 5), or using algebra, 5|x.
Query: Suppose we are given that 6|15x. Can we say that 6| x? What can we say
divisors of x?
The correct proof given above is based on the simple observation that 1 = 7
٠ 3 −
5٠ 4. We
were able to express 1 as a linear combination of 5 and 7. Here gcd(5, 7) = 1.
We shall now
show that if d = gcd(a, b), then d is a linear combination of a and b.
Theorem 1.6 Let d = gcd(a, b). Then there are integers x and y such that
d = ax + by
Remark: The proof will show how to compute x and y. In the lab, the spreadsheet
also computes the values of x and y .
Proof: If we divide a by b to get a = bq + r, we know that d = gcd(b, r), and we
r = a − qb = a ٠ 1 + b(−q), a linear combination of a and b. If we continue the
Algorithm, we divide again we divide b by r to nd b = rq1+r1. Then the second
r1 = b − rq1 is also a linear combination of a and b since b and r are.
Continuing in this
way, we can show that every remainder is a linear combination of a and b. In
is, since it is the last non-zero remainder.
We illustrate this technique with a simple numerical example.
Example 1.7 Find d = gcd(92, 17) and express it as a linear combination of 92
Method: The Euclidean algorithm gives
92 = 17٠ 5 + 7
17 = 7٠ 2 + 3
7 = 3 ٠ 2 + 1
Starting from the top, we get
We underline the original numbers to keep track of them. Now use the second
Theorem 1.6 has an interesting corollary. We have defined gcd(a, b) as the
divisor of a and b. Thus, if d|a and d|b, then d ≤ gcd(a, b). We can now state
Corollary 1.8 If d|a and d|b, then d|gcd(a, b)
For a proof, we can write gcd(a, b) = xa + yb, so d|gcd(a, b), since gcd(a, b)
is a linear
combination of a and b. In words, any common divisor of a and b is also a
divisor of their
For example, if two numbers have gcd 6, then 4 cannot divide both of these
Corollary 1.9 gcd(a, b) = 1 if and only if 1 is a linear combination of a and b.
Proof: Theorem 1.6 shows that if gcd(a, b) = 1, then 1 is a linear combination
of a and
b. Conversely, if 1 is a linear combination of a and b then any divisor of a and
b must also
divide 1, and so must equal 1. So gcd(a, b) = 1.
Theorem 1.10 Let gcd(a, b) = 1 and a|bn. Then a|n.
Proof: The proof parallels the example above, when 5|7x. Since gcd(a, b) = 1, we
1 = ax + by for some integers x and y. Multiply by n to get n = axn + bny. Now
and a|bn, we have a|n since n is a linear combination of a and bn.
Definition 1.11 If gcd(a, b) = 1, we say that a and b are relatively prime.
Thus, we can restate the Theorem 1.10. If a and b are relatively prime, and a|bn,
A useful alternative is the following result.
Corollary 1.12 If a and b are relatively prime, a|n and b|n, then ab|n.
Proof: Since a|n, we have n = aq for some q. Thus b|aq. Since a and b are
b|q by the above result, and so q = bq1 for some q1. Therefore n = aq = abq1.
If we \divide out" the gcd of two numbers, the resulting quotients are
Theorem 1.13 Let d = gcd(a, b). Then a/d and b/d are relatively prime.
Proof: Write d = xa + yb. Divide by d to get 1 = x(a/d) + y(a/d). This shows
and b/d are relatively prime by Corrolary 1.9.
Theorem 1.14 gcd(xa, xb) = x gcd(a, b) for any x > 0.
Proof: Let d = gcd(a, b). Then since d|a and d|b, we have xd|xa and xd|xb, so xd
common divisor of xa and xb. Therefore
gcd(xa, xb) ≥ xd
On the other hand, we know that x is a common divisor of xa and xb. Therefore by
Corollary 1.8, gcd(xa, xb) is a multiple of x, say xD. Thus xD|xa and xD|xb, and
D|a and D|b. Since D is a common divisor of a and b, we must have D ≤ d. Thus,
gcd(xa, xb) = xD ≤ xd:
These two inequalities prove the result.
We can give a useful test to decide whether two numbers a and b are relatively
Definition 1.11 and Theorem 1.6, we know that if two numbers are relatively
prime, then 1
is a linear combination of them. The following theorem is a valid converse.
Theorem 1.15 Let ax + by = 1 for some integers x and y. Then a and b are
Proof: Let d be a common divisor of a and b. Then, by Theorem 1.4, d divides any
combination of a and b. Therefore d|1 and so d = 1 since the only positive
divisor of 1 is 1.
Therefore gcd(a, b) = 1 and so a and b are relatively prime.
For example, all that's required to show that 5 and 7 are relatively prime is to
3 ٠ 7 − 4 ٠ 5 = 1.
Here's an example to use some of these results. It will be used in the next
Example 1.16 Given: gcd(a, b) = 1. Prove: gcd(a + b, a − b) = 1 or 2.
Method: Let c = a+b and d = a−b. Add toeliminate b . This gives c+d = 2a.
Similarly, by subtracting , we get c−d = 2b. Now let f be any common divisor of c and d. Thus
f|d. Therefore, by the above two equations, we find f|2a and f|2b. Therefore
But by Theorem 1.14, gcd(2a, 2b) = 2gcd(a, b) = 2. Therefore, f|2 and so f = 1
or f = 2.