Euclidean Algorithm - Greatest Common Divisor

The recursive version of GCD is simple and small. Just 4 lines of code are enough to find GCD.

int gcd ( int a, int b ) {
    if ( b == 0 ) return a;
    return gcd ( b, a % b );
}

int gcd ( int a, int b ) {
    while ( b ) {
        a = a % b;
        swap ( a, b );
    }
    return a;
}

There is also a builtin function in C++ for finding gcd. You can simply write __gcd(a,b) to find GCD(a,b).

Proof 

The Euclidean Algorithm works on the principle $GCD(a,b) = GCD(b,a\%b)$. If we can prove this, then there will be no doubt about the algorithm.

Let $g = GCD(a,b)$ and $a = k \times b + r$, where k is a non-negative integer and r is the remainder. Since $g$ divides $a$, $g$ also divides $k \times b + r$. Since $g$ divides $b$, $g$ also divides $k \times b$. Therefore, $g$ must divide $r$ otherwise $k \times b + r$ won't be divisible.

So we proved that $g$ divides $b$ and $r$.

Now lets say we have $g' = gcd (b,r)$. Since $g'$ divides both $b$ and $r$, it will divide $k \times b + r$. Therefore, $g'$ will divide $a$.

Now, can $g$ and $g'$ be two different numbers?

We will prove this using contradiction. Let's say that $g > g'$. We know that $g$ divides both $b$ and $r$. So how can $gcd(b,r)$ be $g'$ when we have a number greater than $g'$ that divides both $b$ and $r$? So $g$ cannot be greater than $g'$.

Using the same logic, we find there is a contradiction when $g < g'$. Therefore, the only possibility left is $g = g'$.

$\therefore GCD(a,b) = GCD(b, r ) = GCD( b, a \% b )$.

Complexity

It's kind of tricky. For now, just look at this answer from StackOverflow. The complexity of Eculidean Algorithm according to the answer is $O(log_{10}A + log_{10}B)$.

Apparently, there is a whole chapter in Knuth's book TAOCP. I will write a separate post on the complexity of this algorithm when I understand it. For now, just know that it works fast.

Properties