Euclidean Division

Let $a ∈ Z$ and $b ∈ Z$ be two integers with $b \neq 0$. Then there is always another integer $m ∈ Z$ and a natural number $r ∈ N$, with $0 ≤ r < |b|$ such that the following holds:

$$a = m · b + r$$

This decomposition of a given $b$ is called Euclidean Division, where $a$ is called the dividend, $b$ is called the divisor, $m$ is called the quotient and $r$ is called the remainder. It can be shown that both the quotient and the remainder always exist and are unique, as long as the divisor is different from 0.

Notation: Suppose that the numbers $a, b, m$ and $r$ satisfy above equation. We can then use the following notation for the quotient and the remainder of the Euclidean Division as follows:

$$a \text{ div } b := m, a \text{ mod } b := r$$

We also say that an integer $a$ is divisible by another integer $b$ if $a \text{ mod } b = 0$ holds. In this case, we write $b|a$, and call the integer $a \text{ div } b$ the cofactor of $b$ in $a$.

The Euclidean Algorithm

The greatest common divisor of two non-zero integers $a$ and $b$ is defined as the largest non-zero natural number $d$ such that $d$ divides both $a$ and $b$, that is, $d|a$ as well as $d|b$ are true. We use the notation $gcd(a, b) := d$ for this number. Since the natural number 1 divides any other integer, 1 is always a common divisor of any two non-zero integers, but it is not necessarily the greatest.

A common method for computing the greatest common divisor is the so-called Euclidean Algorithm:

def gcd(a, b):
    (r, rr) = (a, b)
    while r % rr != 0:
        (r, rr) = (rr, r % rr)
    return rr

Sage example:

a.gcd(b)

Complexity: $O(\log{\min(a, b)})$

The Extended Euclidean Algorithm

The Extended Euclidean Algorithm is a method for calculating the greatest common divisor of two natural numbers $a$ and $b \in N$, as well as two additional integers $s,t ∈ Z$, such that the following equation holds:

$$gcd(a, b) = s · a + t · b.$$

def xgcd(a, b):
    (r, rr) = (a, b)
    (s, ss) = (1, 0)
    (t, tt) = (0, 1)
    while r % rr != 0:
        q = r // rr
        (r, rr) = (rr, r - q * rr)
        (s, ss) = (ss, s - q * ss)
        (t, tt) = (tt, t - q * tt)
    return (rr, ss, tt)

Sage example:

a.xgcd(b)

Complexity: $O(\log{\min(a, b)})$