Basics of GCD & Euclidean Algorithm

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 and b, it is proved that GCD of a and b is always <= min(a,b)

HOW TO CALCULATE GCD?

Naive Method

Since gcd of and <= 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 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.

Euclidean Method

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 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 and b – 

  • divides a
  • divides b
  • divides b*q – since it divides b, it divides multiple of b as well
  • divides (a-b*q) – since it divides both a and b*q
  • therefore, since r = a-b*qdivides 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-

r*b <a*b/2

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 and be and LCM be l.

then, a*b = l*g .

Let us prove this.

a can be written as g.x

similarly, can be written as g.y

Here and 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 and are the divisors of LCM l . Thus l = x*y*g (it divides both a and and it is the smallest such number).

l*g = x*y*g*g = a*b

PROVED

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 🙂