Euclidean Algorithm

March 15 2025•Steve Boby George
dsaalgorithmsgcdmathematics

The School of Athens

“The School of Athens” by Raphael, via Wikimedia Commons

The algorithm states that the greatest common divisor (GCD) of two numbers can be derived using the following identity:

gcd⁡(n1,n2)=gcd⁡(n1−n2,n2)\gcd(n_1, n_2) = \gcd(n_1 - n_2, n_2)

where n1>n2n_1 > n_2

The difference is always divisible by the GCD, i.e.,

(n1−n2) mod gcd⁡(n1,n2)=0(n_1 - n_2) \bmod \gcd(n_1, n_2) = 0

Example: GCD for n1=7n_1 = 7 and n2=2n_2 = 2

gcd⁡(7,2)=gcd⁡(7−2,2)=gcd⁡(5,2)\gcd(7, 2) = \gcd(7 - 2, 2) = \gcd(5, 2) gcd⁡(5,2)=gcd⁡(5−2,2)=gcd⁡(3,2)\gcd(5, 2) = \gcd(5 - 2, 2) = \gcd(3, 2) gcd⁡(3,2)=gcd⁡(3−2,2)=gcd⁡(1,2)\gcd(3, 2) = \gcd(3 - 2, 2) = \gcd(1, 2) gcd⁡(2,1)=gcd⁡(2−1,1)=gcd⁡(1,1)\gcd(2, 1) = \gcd(2 - 1, 1) = \gcd(1, 1) gcd⁡(1,1)=gcd⁡(1−1,1)=gcd⁡(0,1)\gcd(1, 1) = \gcd(1 - 1, 1) = \gcd(0, 1)

Hence, the GCD of n1=7n_1 = 7 and n2=2n_2 = 2 is 1.

Optimization with Modulus

Instead of repeated subtraction, we can use the modulus operator:

gcd⁡(7 mod 2,2)=gcd⁡(1,2)\gcd(7 \bmod 2, 2) = \gcd(1, 2)

The code for the algorithm can be written as follows:

class Solution {
    public int GCD(int n1, int n2) {
        while (n1 != 0 && n2 != 0) {
            if (n1 > n2)
                n1 = n1 % n2;
            else
                n2 = n2 % n1;
        }
        return (n2 == 0) ? n1 : n2;
    }
}

Complexity Analysis

Time Complexity:

O(log⁡(min⁡(n1,n2)))O(\log(\min(n_1, n_2)))

where n1n_1 and n2n_2 are given numbers. Because in every iteration, the algorithm is dividing the larger number with the smaller number, resulting in logarithmic time complexity.

Space Complexity:

O(1)O(1)

Since only a couple of variables are used, i.e., constant space.