Suppose we have two integers $a$ and $b$ . We say that the number $d$ is the greatest common divisor of $a$ and $b$ if and only if, $d \mid a$ and $d \mid b$ and if $c \mid a$ and $c \mid b$ , then $c \leq d$ . Condition $1$ says that $d$ is a common divisor of $a$ and $b$ , and condition $2$ says that it is the greatest such divisor.

Note that if $a$ and $b$ are not both zero, then the set of common divisors of $a$ and $b$ is a set of integers that is bounded above by the largest of $a$ , $b$ , $-a$ , and $-b$ . Hence, from the well ordering principle for the integers, the set has a largest element, so the greatest common divisor of $a$ and $b$ exists and is unique. Note that $gcd(0,0)$ is not defined, and when $gcd(a,b)$ is defined, then it is positive. In fact, $gcd(a, b) \geq 1$ because $1 \mid a$ and $1 \mid b$ for all $a$ and $b$ .

Properties of GCD

$gcd(a, 0) = |a|$
$gcd(a, b) = gcd(b, a)$
$gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)$
$gcd(a + mb, b) = gcd(a, b)$
$gcd(ca, cb) = c * gcd(a, b)$
$gcd(a, b) = gcd(a - b, b)$
$gcd(a, b) = gcd(b, a \mod b)$
If $m \mid a$ and $m \mid b$ then $gcd(a/m, b/m) = gcd(a, b)/m$
If $gcd(a, b) = d$ , then $gcd(a/d, b/d) = 1$
Every common divisor of $a$ and $b$ is also a divisor of $gcd(a, b)$
If $gcd(a, b) = d$ , then there exists integers $x, y$ such that $ax + by = d$

Mathematical Proofs

If a and b are not both 0, and let $d = gcd(a, b)$ . Then $d$ is the smallest positive integer that can be expressed as a linear combination of $a$ and $b$ , $d = sa+tb$ .

The set of all linear combinations of $a$ and $b$ contains a smallest integer $m$ such that, $m = sa+tb$ . On the right hand side of the equation we see that $d \mid sa$ abd $d \mid tb$ . Hence, in the left hand side, $d \mid m$ . The smallest integer that $d$ can divide is $d$ . So, $m = d$ . So, $d$ is the smallest positive integer that can be expressed as a linear combination of $a$ and $b$ . It is known as Bézout's identity.

If $c$ is any common divisor of $a$ and $b$ , then $c$ divides $gcd(a, b)$ .

Let $d = gcd(a, b)$ . Now we can express $d$ as a linear combination, $d = sa + tb$ . Since, the right hand side is divisible by $c$ ( $c \mid a$ and $c \mid b$ ), in the left hand side $c$ must divide $d$ .

$gcd(ca, cb)$ is the same as $c\times gcd(a, b)$

Let $d = gcd(a, b)$ . So we can say, $d \mid a$ and $d \mid b$ , which implies $d \mid ca$ and $d \mid cb$ . Hence $dc \mid ca$ and $dc \mid cb$ . As $d$ is the greatest common divisor of $a, b$ , we can say that $dc$ is the greatest common divisor of $ca, cb$ . So, $gcd(ca, cb) = dc = c \times gcd(a, b)$

If $m \mid a$ and $m \mid b$ then $gcd(a/m, b/m) = gcd(a, b)/m$

Let $d = gcd(a, b)$ , since $m \mid a$ and $m \mid b$ , so $m$ is common divisor of $a$ and $b$ and $m \leq d$ . We have to prove that $gcd(a / m, b / m) = d / m$ . From $d = sa + tb$ , it follows that $m \mid d$ . We know that $gcd(ca, cb)$ is the same as $c\times gcd(a, b)$ . Hence, $gcd(a/m, b/m) = \frac{1}{m} \times gcd(a, b)$

If $d = gcd(a, b)$ then $gcd(a / d, b / d) = 1$

Let us assume that, $gcd(a / d, b / d) = 1$ . We know that $gcd(ca, cb)$ is the same as $c\times gcd(a, b)$ . Hence, $gcd(a, b) = d * gcd( a / d, b / d )$ . In order to satisfy the equation $gcd(a / d, b / d)$ must be equal to $1$ .

$gcd(a, b)$ is equal $gcd(b, a \mod b)$

Let $d = gcd(a, b)$ . We know that since $d \mid a$ and $d \mid b$ , it follows from $b = qa + r$ that $d \mid r$ . Thus $d$ is a common divisor of $a$ and $r$ . Now we need to make sure that $d$ is the greatest of all common divisors of $a$ and $r$ . Let $c$ be a common divisor of $a$ and $r$ . From $b = qa + r$ , if $c \mid a$ and $c \mid r$ , then also $c \mid b$ . Now $c \leq d$ , because $d$ is the largest of all common divisors. So we can conclude that $gcd(a, b)$ = $gcd(b, a \mod b) = gcd(b, r)$ where $r = a \mod b$ .

Prime Factorization to Compute GCD

If we have two integers $a, b$ and we can find $gcd(a, b)$ from the prime factorization of $a, b$ . Suppose $a = 2^{a_1} \times 3^{a_2} \times 5^{a_3}...$ and $b = 2^{b_1} \times 3^{b_2} \times 5^{b_3}...$ , then we can write $a \times b = 2^{a_1 + b_1} \times3^{a_2+b_2} \times5^{a_3 + b_3}...$ . Now, if we take the $min(a_i, b_i)$ for each $p_i$ we get the common portion for that $p_i$ . In this way, we can keep multiplying the common portions to get $gcd(a, b)$ . Thus mathematically if $ab = p_1^{a_1 + b_1} \times p_2^{a_2 + b_2} \times p_3^{a_3 + b_3} \times \dots \times p_n^{a_n + b_n}$ then, $gcd(a, b) = \prod p_i^{min(a_i , b_i)}$

Euclidean Algorithm to Compute GCD

One of the ways to compute the GCD of two integers is to list down the divisors of $a$ and $b$ and pick the largest one. But this naive method takes a lot of time. Another way is the Euclidean Algorithm. This is much more efficient and the time complexity of this algorithm is roughly $O(log_2n)$ . This algorithm is based on the fact that when $a = bq + r$ , then we can say that $gcd(a, b) = gcd(b, r)$ . We know from the division algorithm, $a = bq + r$ , where $r$ is the remainder when $a$ is divided by $b$ . So, $r = a \mod b$ .

The division algorithm is nothing but a proof that the long divisions that we used to do in schools was right. Let’s take a look at the proof, Let $d = gcd(a, b)$ . From the division algorithm we know that $a = bq + r$ . We know, $d \mid a$ and $d \mid b$ , which implies that $d \mid r$ . Again let $c$ is any common divisor of $b$ and $r$ , then we know $c \mid b$ and $c \mid r$ which implies $c \mid a$ . Both parts of the definition of GCD are satisfied and hence Thus $gcd(a, b) = gcd(b, r)$ where $r = a \mod b$ . Let's now implement the algorithm. As we have seen, $gcd(a, b) = gcd(b, a \mod b)$ which is a recurrence relation and this relation can be used to calculate GCD of two integers recursively. When we reach $b = 0$ , we can say that $gcd(a, 0) = a$ .

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

We can also implement the euclidean algorithm without recursive calls, which may reduce the recursion overhead. Thus making it a bit faster than the recursive one.

int gcd( int a, int b ) {
    while( b != 0 ) {
        int new_a = b;
        b = a % b;
        a = new_a;
    }
    return a;
}

Related problems

UVa 11417 - GCD SPOJ GCD - Greatest Common Divisor CF 664A - Complicated GCD

References

Wikipedia - Greatest Common Divisor Khan Academy - Euclidean Algorithm

Tag: number-theory

GCD and Euclidean Algorithm

Prime Factorization Using Sieve Method