Euclidean Algorithm - Algorithm Tutorial | Repovive

##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######

Euclidean Algorithm for GCD

The Greatest Common Divisor (GCD), also known as the Greatest Common Factor (GCF) or Highest Common Factor (HCF), is the largest number that divides both inputs. The Euclidean algorithm computes GCD efficiently using the property $gcd(a, b) = gcd(b, a \mod b)$ .

Any common divisor of $a$ and $b$ also divides $a \mod b$ . So you preserve the GCD through the modulo operation. Eventually, you reach $gcd(n, 0) = n$ .

text

function gcd(a, b):
    while b != 0:
        temp = b
        b = a mod b
        a = temp
    return a

Recursive version:

text

function gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a mod b)

Example trace: $gcd(48, 18)$ $1.$ $gcd(48, 18) \to gcd(18, 12)$ $2.$ $gcd(18, 12) \to gcd(12, 6)$ $3.$ $gcd(12, 6) \to gcd(6, 0)$ $4.$ Return $6$

Applications: You use GCD for simplifying fractions, cryptography (RSA), finding LCM, and solving Diophantine equations.

Time complexity: $O(\log(\min(a, b)))$ because the remainder decreases by at least half every $2$ steps.

Space complexity: $O(1)$ for iterative, $O(\log(\min(a, b)))$ for recursive due to call stack.

Euclidean Algorithm Algorithm Tutorial

Learn

Euclidean Algorithm for GCD

Implement this Algorithm

Related Algorithms