Euclidean Algorithm

By | March 10, 2026
0 Comment

simple algorithm

The Euclidean algorithm is a classical method for computing the greatest common divisor (GCD) of two non‑negative integers.
The key idea is based on the following property:

For any integers a and b (with a ≥ b), the GCD of a and b is the same as the GCD of b and a mod b.

Because the remainder becomes strictly smaller each step, the process terminates after only a few iterations, even for very large numbers. When the remainder finally becomes 0, the divisor at that step is the GCD.

def gcd(a: int, b: int) -> int:
    """
    Compute the greatest common divisor (GCD) of two non‑negative integers
    using the Euclidean algorithm.

    Parameters
    ----------
    a, b : int
        The numbers whose GCD is required.  They may be zero, but not both
        simultaneously zero (gcd(0,0) is mathematically undefined).

    Returns
    -------
    int
        The greatest common divisor of a and b.
    """
    # Ensure the inputs are non‑negative
    a, b = abs(a), abs(b)

    # Edge cases
    if a == 0 and b == 0:
        raise ValueError("gcd(0, 0) is undefined.")
    if b == 0:
        return a   # gcd(a, 0) = a

    # Main loop: repeatedly replace (a, b) with (b, a % b)
    while b:
        a, b = b, a % b
    return a


# ------------------------------
# Demo / simple test cases
# ------------------------------
if __name__ == "__main__":
    test_pairs = [
        (48, 18),    # expected 6
        (270, 192),  # expected 6
        (100, 25),   # expected 25
        (7, 13),     # expected 1 (coprime)
        (0, 5),      # expected 5
    ]

    for x, y in test_pairs:
        print(f"gcd({x}, {y}) = {gcd(x, y)}")

A few sample pairs are tested, printing the results.

  1. Input sanitisation – We take absolute values so the function works with negative inputs as well.
  2. Edge‑case handling –
    • gcd(0, 0) is mathematically undefined, so we raise an error.
    • If one argument is zero, the GCD is simply the absolute value of the other.
  3. Main loop – While b is non‑zero, we repeatedly assign a, b = b, a % b.
    This implements the Euclidean step described earlier.
    When b finally becomes zero, a holds the GCD.