The Greatest Common Divisor(GCD) of two integers is defined as follows:
An integer c is called the GCD(a,b) (read as the greatest common divisor of integers a and b) if the following 2 conditions hold:
1) c | a ( c | b
2) For any common divisor d of a and b, d | c.
Rule 2 ensures that the divisor c is the greatest of all the common divisors of a and b.
One way we could find the GCD of two integers is by trial and error. Another way is that we could prime factorize each integer, and from the prime factorization, see which factors are common between the two integers. However, both of these become very time consuming as soon as the integers are relatively large.
However, Euclid devised a fairly simple and efficient algorithm to determine the GCD of two integers. The algorithm basically makes use of the division algorithm repeatedly.
Let’s say you are trying to find the GCD(a,b), where a and b are integers with a ( b > 0
Euclid’s algorithm says to write out the following:
a = q1b + r1, where 0 < r < b b = q2r1 + r2, where 0 < r2 < r1 r1 = q3r2 + r3, where 0 < r3 < r2
.
. ri = qi+2ri+1+ ri+2, where 0 < ri+2 < ri+1
.
. rk-1 = qk+1rk
Euclid’s algorithm says that the GCD(a,b) = rk
This might make more sense if we look at an example:
Let’s look at one more quickly, GCD(125, 20)
125 = 6*20 + 5
20. = 4*5,
thus, the GCD(125,20) = 5
Proof That Euclid’s Algorithm Works
Now, we should prove that this algorithm really does always give us the GCD of the two numbers “passed to it”. First I will show that the number the algorithm produces is indeed a divisor of a and b.
a = q1b + r1, where 0 < r < b b = q2r1 + r2, where 0 < r2 < r1 r1 = q3r2 + r3, where 0 < r3 < r2
.
. ri = qi+2ri+1+ ri+2, where 0 < ri+2 < ri+1
.
. rk-1 = qk+1rk
From the last equation, we know that rk | rk-1. So, we know that we can express rk-1 = crk, where c is an integer. Now consider the previous equation:
rk-2 = qkrk-1+ rk = qkcrk, + rk = rk(qkc + 1)
Thus, we have that rk | rk-2.
In our equation previous to that one, we have:
rk-3 = qk-1rk-2+ rk-1
From here , since rk | rk-1 and rk | rk-2, using our rules of divisibility we have that rk | rk-3. As you can see, we can continue this process, considering each previous equation until we get to the last two, where we will find that rk | a and rk | b. Thus, we find that Euclid’s algorithm indeed gives us a common factor of a and b.
Now, we have one more part to prove – and that is to show that the common divisor that Euclid’s algorithm produces is the largest possible. This proof is going to look similar to the previous one, but it is different in that we will start by assuming that a and b have a common factor d, and then show that d | rk.
Consider an arbitrary common factor d of a and b. If d is a common factor, we can rewrite a and b as follows:
a = da’ b = db’, where d, a’, b’ are all positive integers.
Now, consider the first equation from Euclid’s algorithm:
a = q1b + r1. r1 = da’ - q1db’ (Substitute for a and b, and solve for r1.) = d(a’ - q1b’)
Thus, we have that d | r1.
Now, consider the second equation, and repeat the steps we did on the first, this time solving for r2. (Note: We will let r1=dr1’, where r1’ is an integer.)
b = q2r1 + r2.
r2 = db’ - q2dr1’ = d(b’ - q2d)
As you can see, we can continue this process through each of the equations until we hit the second to last one, where we will have:
rk-2 = qkrk-1+ rk
rk = drk-2’ - qkdrk-1’ = d(rk-2’ - qkrk-1’),
thus, d | rk.
But this says that any arbitrary common factor of a and b that we originally picked divides into rk, the value that Euclid’s algorithm produced. Since we know that rk IS a common factor to both a and b, this shows that is must be the largest possible common factor, or the GCD(a,b).
Extended Euclidean Algorithm
One of the consequences of the Euclidean Algorithm is as follows:
Given integers a and b, there is always an integral solution to the equation
ax + by = gcd(a,b).
Furthermore, the Extended Euclidean Algorithm can be used to find values of x and y to satisfy the equation above. The algorithm will look similar to the proof in some manner.
Consider writing down the steps of Euclid's algorithm:
a = q1b + r1, where 0 < r < b b = q2r1 + r2, where 0 < r2 < r1 r1 = q3r2 + r3, where 0 < r3 < r2
.
. ri = qi+2ri+1+ ri+2, where 0 < ri+2 < ri+1
.
rk-2 = qkrk-1+ rk, where 0 < rk < rk-1 rk-1 = qk+1rk
Consider solving the second to last equation for rk. You get
rk = rk-2 - qkrk-1, or
gcd(a,b) = rk-2 - qkrk-1
Now, solve the previous equation for rk-1:
rk-1 = rk-3 - qk-1rk-2,
and substitute this value into the previous derived equation:
Notice that now we have expressed gcd(a,b) as a linear combination of rk-2 and rk-3. Next we can substitute for of rk-2 in terms of of rk-3 and rk-4, so that the gcd(a,b) can be expressed as the linear combination of of rk-3 and rk-4. Eventually, by continuing this process, gcd(a,b) will be expressed as a linear combination of a and b as desired.
This process will be much easier to see with examples:
