One way of finding the greatest common divisor of 2 integers a and b would be to list all the divisors of both a and b, then choose the largest integer that appears in both lists. For example, if a = 12 and b = 18, the divisors of 12 are 1, 2, 3, 4, 6, 12 and the divisors of 18 are 1, 2, 3, 4, 6, 9, 18. We can clearly see that the greatest common divisor is 6. This is a very tedious method of calculation, so following the observation that if a = qb + r then gcd(a, b) = gcd(b, r) we can use Euclid's Algorithm.
Example:
To calculate d = gcd(1492, 1066), we write
1492 = (1 x 1066) + 426
1066 = (2 x 426) + 214
426 = (1 x 214) + 212
214 = (1 x 212) + 2
212 = (106 x 2) + 0
The last non-zero remainder is 2, so d = 2. Try out the GCD calculator below to find out the GCD of 2 numbers, if you fancy having a go at the calculations yourself, see the
Division Quiz for more examples and you can always come back and check your answers!
Euclid's algorithm can be very useful in a number of applications when it comes to prime numbers.
Definition:
Two integers a and b are coprime (or relatively prime) if gcd(a, b) = 1.
For example, 10 and 7 are relatively prime as they share no factors other than 1. Neither integers need to be prime in order for them to be relatively prime, as both 8 and 15 are not prime, yet they are relatively prime.
A corollary to this is that;
Two integers a and b are coprime if and only if there exists integers x and y such that ax + by = 1.
This fact is useful for
Bezout's Identity and using the extended algorithm to compute modular inverses, which are of extreme importance when it comes to encryption schemes such as
RSA.
Written by JaneW
