Submitted By Yashaaa
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:
Consider computing GCD(125, 87)
125 = 1*87 + 38
87. = 2*38 + 11
38. = 3*11 + 5
11 = 2*5 + 1 5. = 5*1
Thus, we find that GCD(125,87) = 1.
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…...