Theorem 1.4 If c|a and c|b, then c|(ax + by) for any integers x and y.
Proof: We have a = cq1 and b = cq2, so ax + by = acq1 + bcq2 = c(aq1 + bq2).
This gives
the result.
A number of the form ax+by is called a linear combination of a and b . So this
result simply
states that if a number divides two numbers a and b, it divides any linear
combination of
them. Note that in line with our previous statement , these letters refer to
integers only.
For example, if x and y are any integers, 7|(21x − 35y). This is because 7|21
and 7|35.
The Greatest Common Divisor .
When we reduce a fraction to lowest terms , we find a divisor of the numerator and
the
denominator (a common divisor) and cancel it. Thus we have the familiar
computation
To reduce the fraction a/b to lowest terms, it would be necessary to
find the
greatest common
divisor of a and b. This is simply called gcd(a, b). This computation is very
cumbersome if
the numerator and denominator are large. For example, how would you reduce the
fraction
28, 841/33, 043 to lowest terms? The method we now show handles this problem
very quickly,
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
a linear
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
and
computing gcd(b, r). We then use the same result to simplify gcd(b, r), and
continue until
we find the answer. Let's use this method to find gcd(75, 55). (Of course this can
immediately
be done by most students, but let's illustrate the method.) Dividing, we have
These equations show that
gcd(75, 55) = gcd(55, 20) = gcd(20, 15) = gcd(15,5) = gcd(5, 0) = 5
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
divided
by b and find gcd(b, r). We keep repeating the process until the remainder is 0,
and then
the last non- zero remainder is the required gcd. As noted above, this technique
is called
the Euclidean Algorithm. For simplicity, we have as sumed that a and b are
positive in
this statement of the Euclidean algorithm, and we will often make this
assumption in what
follows.
We can now reduce 28, 841/33, 043 to lowest terms! The following table
systematically gives
the numerator, denominator, quotient and remainders in the Euclidean Algorithm.
| Numerator |
Denominator |
Quotient |
Remainder |
 |
 |
 |
 |
The gcd is 191. Note that in each line, the numbers move over one to the left,
and the
quotients are ignored. Finally, we reduce to lowest terms:
The Euclidean Algorithm computation will be done automatically in the lab, using
the Excel
spreadsheet called GCD.
Many facts about number theory were simply told to us at an early age, and so we
take
them for granted. For example, suppose you know that 5|7x. Does it follow that
5|x? We
were taught to think somewhat as follows:
7x/5
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
about
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
GCD
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
note that
r = a − qb = a ٠ 1 + b(−q), a linear combination of a and b. If we continue the
Euclidean
Algorithm, we divide again we divide b by r to nd b = rq1+r1. Then the second
remainder
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
particular d
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
and 17.
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
equation to
get
Finally, using the last equation and the previous expressions for the remainders
7 and 3, we
obtain
Theorem 1.6 has an interesting corollary. We have defined gcd(a, b) as the
greatest common
divisor of a and b. Thus, if d|a and d|b, then d ≤ gcd(a, b). We can now state
more.
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
gcd.
For example, if two numbers have gcd 6, then 4 cannot divide both of these
numbers.
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
have
1 = ax + by for some integers x and y. Multiply by n to get n = axn + bny. Now
since a|a
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,
then a|n.
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
relatively prime,
b|q by the above result, and so q = bq1 for some q1. Therefore n = aq = abq1.
This shows
that ab|n.
If we \divide out" the gcd of two numbers, the resulting quotients are
relatively prime.
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
that a/d
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
is a
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
therefore
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
prime. Using
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
relatively
prime.
Proof: Let d be a common divisor of a and b. Then, by Theorem 1.4, d divides any
linear
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
observe that
3 ٠ 7 − 4 ٠ 5 = 1.
Here's an example to use some of these results. It will be used in the next
section.
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 to eliminate 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|c and
f|d. Therefore, by the above two equations, we find f|2a and f|2b. Therefore
f|gcd(2a, 2b).
But by Theorem 1.14, gcd(2a, 2b) = 2gcd(a, b) = 2. Therefore, f|2 and so f = 1
or f = 2.
