On the common measure of two magnitudes

Enuntiatio

Propositio III. Theorema. Datis duobus numeris non utrisque nullis, eorum maxima communis mensura per divisiones successivas invenitur.

Let two non-negative integers $a$ and $b$ be given, not both zero. I say that their greatest common divisor — the greatest integer dividing both without remainder — is found by the following reduction: while $b$ is not zero, replace the pair $(a, b)$ by the pair $(b,\, a \bmod b)$; when $b$ becomes zero, the remaining first element $a$ is the sought divisor. The reduction always terminates, for the second magnitude strictly diminishes within the well-ordered naturals and cannot descend below zero. The number of reductions does not exceed a constant multiple of $\log\min(a,b)$, whence the labour is logarithmic in the magnitudes.

Expressio

def gcd(a: int, b: int) -> int:
    """Greatest common divisor of a and b by Euclid's reduction.

    Operates on the absolute values, so signs are immaterial.
    By convention gcd(0, 0) == 0.

    >>> gcd(48, 18)
    6
    >>> gcd(18, 48)   # order is immaterial
    6
    >>> gcd(1071, 462)
    21
    >>> gcd(17, 13)   # coprime magnitudes
    1
    >>> gcd(0, 5)     # zero carries no constraint
    5
    >>> gcd(-48, 18)  # signs are immaterial
    6
    """
    a, b = abs(a), abs(b)
    while b != 0:
        a, b = b, a % b   # the reduction (a, b) -> (b, a mod b)
    return a


# --- Demonstratio per exempla: concrete inline assertions ---
assert gcd(48, 18) == 6        # 48 = 2*18 + 12; 18 = 1*12 + 6; 12 = 2*6 + 0
assert gcd(18, 48) == 6        # symmetry under exchange
assert gcd(0, 0) == 0          # the conventional boundary case
assert gcd(0, 7) == 7          # gcd(0, n) = n
assert gcd(13, 17) == 1        # distinct primes are coprime
assert gcd(100, 100) == 100    # gcd(n, n) = n
assert gcd(1071, 462) == 21    # the classical worked example

if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)
    # Verification against the standard library over a wide range:
    from math import gcd as _ref
    for x in range(0, 200):
        for y in range(0, 200):
            assert gcd(x, y) == _ref(x, y), (x, y)
    print("All assertions hold.")

Demonstratio

We treat $a, b \ge 0$, not both zero; signs are discharged at the outset by taking absolute values, since $d \mid n \iff d \mid |n|$, and the case $a=b=0$ returns $0$ by convention. Two parts are required: that the reduction preserves the divisor sought (correctness), and that it must halt (termination). A third part bounds the labour.

Lemma (Preservation of common divisors). For $b > 0$, the pairs $(a, b)$ and $(b,\, a \bmod b)$ have exactly the same set of common divisors; hence the same greatest common divisor.

Write the division with remainder $a = qb + r$, where $q = \lfloor a/b \rfloor$ and $r = a \bmod b$ with $0 \le r < b$. Let $d$ be any integer.

• Suppose $d \mid a$ and $d \mid b$. Then $d$ divides any integer combination of $a$ and $b$; in particular $d \mid (a - qb) = r$. Thus $d$ divides both $b$ and $r$.
• Conversely, suppose $d \mid b$ and $d \mid r$. Then $d \mid (qb + r) = a$. Thus $d$ divides both $a$ and $b$.

Therefore the common divisors of $\{a, b\}$ and of $\{b, r\}$ coincide as sets. Two equal sets of positive integers have the same greatest element, so $\gcd(a, b) = \gcd(b,\, a \bmod b). \qquad \square$

Loop invariant (Correctness). Let $(a_0, b_0)$ be the input pair (already made non-negative), and let $(a_k, b_k)$ denote the pair held after $k$ reductions. I claim the invariant $\gcd(a_k, b_k) = \gcd(a_0, b_0) \quad\text{holds for every } k \ge 0.$

Base. At $k = 0$ the pair is $(a_0, b_0)$ and the invariant is the identity $\gcd(a_0,b_0)=\gcd(a_0,b_0)$.

Step. Suppose it holds after $k$ reductions and the loop performs one more, which requires $b_k > 0$. The new pair is $(a_{k+1}, b_{k+1}) = (b_k,\, a_k \bmod b_k)$. By the Lemma, $\gcd(b_k,\, a_k \bmod b_k) = \gcd(a_k, b_k)$, which by hypothesis equals $\gcd(a_0, b_0)$. Hence the invariant survives the step.

When the loop halts it is because $b = 0$; say this occurs at step $K$, so $b_K = 0$. Then by the invariant $\gcd(a_0, b_0) = \gcd(a_K, b_K) = \gcd(a_K, 0) = a_K,$ the last equality because every integer divides $0$, so the common divisors of $\{a_K, 0\}$ are exactly the divisors of $a_K$, the greatest of which is $a_K$ itself (and is $0$ only in the degenerate all-zero case). The returned value $a_K$ is therefore precisely $\gcd(a_0, b_0)$.

Termination. Consider the second component $b$ as a measure $\mu = b_k$. After the first reduction the second component is a remainder, and remainders satisfy $0 \le a_k \bmod b_k < b_k$. Hence for every step actually taken, $0 \le b_{k+1} < b_k.$ The sequence $b_1 > b_2 > b_3 > \cdots$ is a strictly decreasing sequence of non-negative integers. By the well-ordering of the naturals, no such sequence is infinite: a strictly descending chain bounded below by $0$ has at most $b_1 + 1$ terms. Therefore $b$ reaches $0$ after finitely many reductions and the loop halts. There is no infinite regress; the construction is well-founded.

Scholium (the labour is logarithmic). A sharper bound shows the descent is fast. After two reductions the second component is at least halved: if $b_{k+1} = a_k \bmod b_k$, then either $b_{k+1} \le b_k/2$ already, or $b_{k+1} > b_k/2$, in which case the next quotient is exactly $1$ and $b_{k+2} = b_k \bmod b_{k+1} = b_k - b_{k+1} < b_k/2$. Thus $b_{k+2} < b_k/2$ in every case, so the second component loses at least one bit every two steps. The number of reductions is therefore $O(\log \min(a,b))$, and (the tightest classical result) is largest precisely for consecutive Fibonacci numbers, where the quotients are all $1$ — which is why $\gcd(1071, 462)$, lying near a Fibonacci ratio, takes its full complement of steps. The arithmetic operations being taken as unit cost, this is the complexity recorded above.

Both halves established and the bound exhibited, the proposition stands.

Q.E.D.