This is a post discussing about the basics of GCD – Greatest Common Divisor , it’s relation with LCM and an efficient algorithm to find it – Euclidean Algorithm.
Now it is highly probable that most of you already know about the above contents. But, It is important to know the proofs about basic stuffs like GCD. So Here’s a blog post explaining it.
GCD or Greatest Common Divisor between two numbers ‘a‘ and ‘b‘ is the largest number ‘g‘ that divides both ‘a‘ and ‘b‘ leaving no remainder.
For example – GCD for 12 and 8 is 4. (Since there is no other number that divides both 8 and 12 leaving 0 remainder).
Since, GCD is a divisor of a and b, it is proved that GCD of a and b is always <= min(a,b)
HOW TO CALCULATE GCD?
Since gcd of a and b <= min(a,b), A naive method would be to iterate from min(a,b) to 1 (decrement by 1). If we encounter any number which divides both a and b, we got our GCD.
But this solution is too slow – O(n) – it takes linear worst time. This method will definitely Time out if we need to solve a large number of GCDs in our problem or if we need to calculate gcd of numbers in range of 10^8 or above.
This is an extremely fast solution for finding GCD. Let us discuss what this algorithm says and understand its proof of correctness.
According to Euclidean’s algorithm, gcd(a,b) = gcd(b,a%b). Let us try to prove this relation.
Suppose we want to calculate the GCD of a and b. Let us consider that a>=b .We can draw the following division relation –
a = b*q + r
dividend = divisor * quotient + remainder
Let gcd be g.
Since g is a divisor of both a and b –
- g divides a
- g divides b
- g divides b*q – since it divides b, it divides multiple of b as well
- g divides (a-b*q) – since it divides both a and b*q
- therefore, since r = a-b*q , g divides r as well
Therefore , we have proved that if g divides a and b, it divides their remainder – r as well. or gcd(a,b) = gcd(b,a%b).
Also if b is 0 , gcd(a,b) = a
thus, we have proved the Euclidean Algorithm.
The time complexity of this algorithm is O(log(a.b)). Let us see how.
from gcd(a,b), our next step is gcd(b,r) till one of them becomes 0.
r < a/2 (This is always the case if dividend (a) >= divisor(b))
multiply b both sides-
Thus , in the worst case scenario we are moving half the value of product a*b . This proves that the time complexity is O(log(a.b)) .
RELATION BETWEEN LCM AND GCD/HCF
let LCM of a and b be g and LCM be l.
then, a*b = l*g .
Let us prove this.
a can be written as g.x
similarly, b can be written as g.y
Here x and y has to be co-prime (no common divisors) otherwise they would be contributing to g.
Let us try to calculate LCM by understanding its definition. LCM of two numbers is the smallest number which is a multiple of both the numbers.
Thus a and b are the divisors of LCM l . Thus l = x*y*g (it divides both a and b and it is the smallest such number).
l*g = x*y*g*g = a*b
I tried my best trying to write about the proofs. If there’s any query, feel free to ask in the comments below . Also share any important additional info about the same topic if there’s something additional you know 🙂