Q: Find the greatest common divisor of 2 numbers a and b and also find 2 numbers x and y such that ax + by = GCD(a,b)
Sol:
Every number is divisible by 1, and so the least common divisor of a pair of numbers is 1. The more challenging problem is to find the Greatest Common Divisor (GCD), the largest divisor common to a set of given integers.
The naive way of finding the GCD is to find all divisors of one number and test each of these for divisibility on the second. Another way would be to find the prime factorization of both numbers and find product of all common factors. But, as you can see, these methods are more brute-force and will be computationally intensive.
Euclid's algorithm for GCD computation was one of the earliest interesting algorithms in history. It is based of a couple of basic observations.
1. If b divides a, then GCD(a,b) equals b
2. If a = bn + k, then GCD(a,b) = GCD(b,k)
The first observation is pretty straight forward. If b divides a, then a = bn where n = 1,2,3.. and so GCD(a,b) = GCD(bn,b) = b
For the second observation, GCD(a,b) = GCD(bn+k, b) Any common divisor of a and b is now dependant on k, since bn is divisible by b.
From this you see that the algorithm is recursive. Replace the bigger integer by its remainder mod smaller integer. This basically cuts down the integer size to at least half for each step, and thus the running time of the algorithm is logarithmic number of iterations to the naive ones discussed above.
An outcome of Euclid's algorithm is that you can find more than just the GCD(a,b). In fact you can also find two integers x and y such that
ax + by = GCD(a,b)
int GCD(int a, int b, int& x, int& y)
{
int prevX, prevY;
int gcd;
if(b > a)
{
return GCD(b,a,y,x);
}
if(b == 0)
{
x=1;
y=0;
return a;
}
gcd = GCD(b, a%b, prevX, prevY);
x = prevY;
y = prevX - FLOOR(q/b) * prevY;
return gcd;
}
