Labels

Greatest common divisor (GCD)

The greatest common divisor for $a$ and $b$ is the biggest number $c$, such that $c\ |\ a$, and $c\ |\ b$. This is denoted with $\textrm{GCD}(a,b)=c$.

Suppose we want to find $\textrm{GCD}(252, 810)$. We can use two methods to find the greatest common divisor.

Prime factorization

If we decompose $a$ and $b$ into the prime factorization, we get that $a = 2^2\cdot 3^2\cdot 7$, and $b = 2\cdot 3^4\cdot 5$. Extract the common factors $2\cdot 3^2$, which gives the answer $\textrm{GCD}(252, 810) = 18$. However, if $a$ and $b$ are large numbers, the prime factorization is too time consuming, and we can use another method.

Euclid's method

A second method is Euclid's method. This method is based on the fact that $$\textrm{GCD}(a, b) = \textrm{GCD}(b, a-q\cdot b),$$

where $q = a - b\cdot\lfloor \frac{a}{b} \rfloor$.

Using this method, we find that:

$$ \begin{align} \textrm{GCD}(810, 252) &= \\ \textrm{GCD}(252, 54) &= \qquad &(810-3\cdot 252 = 54) \\ \textrm{GCD}(54, 36) &= \qquad &(252 - 4\cdot 54 = 36) \\ \textrm{GCD}(36, 18) &= \qquad &(54 - 1\cdot 36 = 18) \\ \textrm{GCD}(18, 0) &= 18. \qquad &(36 - 2\cdot 18 = 0) \end{align} $$ However, a faster way of writing this, is: $$ \begin{align} 810& \\ \underline{252}& \\ 54& \qquad &(810-3\cdot 252 = 54) \\ 36& \qquad &(252 - 4\cdot 54 = 36) \\ (\textrm{GCD})\quad 18& \qquad &(54 - 1\cdot 36 = 18) \\ 0& \qquad &(36 - 2\cdot 18 = 0) \end{align} $$

Using this algorithm to write a function in Python, we can find the $\mathrm{GCD}$ with: 
def gcd(a, b):
    a = abs(a)
    b = abs(b)
    if b > a:
        a, b = b, a
    while b != 0:
        a, b = b, a - a // b * b
    return a

The $\textrm{GCD}$ can also be used to find the least common multiple $\textrm{LCM}$, with $$ \textrm{LCM}(a, b) = \dfrac{a\cdot b}{\textrm{GCD}(a, b)}. $$

Another application of the $\textrm{GCD}$ is the simplification of fractions. If both the numberator $a$, and the denominator $b$, are divided by $\textrm{GCD}(a, b)$, the fraction is simplified to the lowest form. Example: simplify $\frac{461538}{999999}$ to the lowest form. First we find the greatest common divisor: $$ \begin{align} 999999& \\ \underline{461538}& \\ \textrm{(GCD)}\quad 76923& \\ 0& \end{align} $$ Finally we divide both the numerator and denominator by $76923$ to find $\dfrac{6}{13}$.

Extended Euclidean Algorithm

It is also possible to express $\textrm{GCD}(a, b)$ as a linear combination of $a$ and $b$. To do this, we will use the extended Euclidean algorithm. Using the previous example, we can construct the following table.

$810$ $252$
$810$ $1$ $0$
$252$ $0$ $1$
$52$ $1$ $-3$ $R_1 - 3R_2$
$36$ $-4$ $13$ $R_2 - 4R_3$
$18$ $5$ $-16$ $R_3 - R_4$

Using the last row, we can read that $810\cdot(5) + 252\cdot(-16) = 18$. The linear combination is useful in solving Diophantine equations. The code below is the previous gcd(a, b) function modified to find the linear combination with the extended Euclid's algorithm. 

def extended_euclid(a, b):
    sign_a = 1 if a >= 0 else -1
    sign_b = 1 if b >= 0 else -1
    a = abs(a)
    b = abs(b)
    x1, y1 = 1, 0
    x2, y2 = 0, 1
    swap = b > a
    if swap:
        a, b = b, a
    while b != 0:
        q = a // b
        a, b = b, a - q*b
        x1, y1, x2, y2 = x2, y2, x1 - q*x2, y1 - q*y2
    if swap:
        x1, y1 = y1, x1
    return sign_a * x1, sign_b * y1
Labels: