Euclidean Algorithm — For GCD

(Day -2 of Advanced Competitive Coding Journey)

Suppose we are given two numbers a and b and we have to find their greatest common divisor(GCD), by definition if any one of the given numbers is zero and the second one is non-zero, so their GCD will be the non-zero value. When both of the given numbers are zeros, then their GCD will be undefined.

By using the Euclidean algorithm, we can calculate the gcd of the given numbers in O(log2(min(a,b))) time complexity.

The algorithm is bit simple and states as following :-

gcd(a,b) = { a (if b = 0) or gcd(b, a%b) (otherwise) }

Proof :- We have to prove gcd(a,b) = gcd(b, a%b) for all a≥0, b≥0
We can prove that the value on the left side of the equation divides the value on the right side of the equation and vice versa, which means LHS and RHS are equal.

let d = gcd(a,b), by definition of gcd d will divide a and b.
and we can write a%b = a — b*[a/b], which means d is going to divide a%b as well, d is dividing a, d is dividing b, and d is dividing a%b. Now we use the fact that for any three numbers p,q,r if p divides q and p divides then p will divide gcd(p, r). Thus the equation on the left side divides the equation on the right side, similarly, we can show the vice versa.

Code Snippet:-