Code Logo

GCD with Euclidean Algorithm

Published at25 Jul 2026
Created by
Number Theory Easy 2 views
Like0

Given two non-negative integers a and b, compute their greatest common divisor (GCD) using the Euclidean algorithm. The GCD is the largest positive integer that divides both numbers without a remainder.

For example, GCD(12, 8) = 4 because 4 divides both 12 and 8, and no larger number does. GCD(7, 3) = 1 because 7 and 3 share no common factors (they are coprime). GCD(0, 5) = 5 because every number divides 0, and the GCD of 0 and any non-zero number is that number.

The Euclidean algorithm is one of the oldest known algorithms, dating back to ancient Greece (circa 300 BC). It is remarkably elegant: repeatedly replace the larger number by its remainder when divided by the smaller number, until one of them reaches zero. The non-zero number at that point is the GCD.

The Euclidean algorithm is far more efficient than factoring both numbers and comparing prime factors. It runs in O(log min(a, b)) time, which is fast even for numbers with hundreds of digits. This algorithm is foundational for cryptography (RSA key generation), rational number arithmetic (simplifying fractions), and many number-theoretic computations.

Edge cases include one or both numbers being zero (GCD(x, 0) = x), and both numbers being equal (GCD(x, x) = x). The algorithm handles all of these naturally.

Example Input & Output

Example 1
Input
100,10
Output
10
Explanation

100/10

Example 2
Input
17,17
Output
17
Explanation

Same numbers

Example 3
Input
7,3
Output
1
Explanation

Prime pair

Example 4
Input
12,8
Output
4
Explanation

GCD of 12 and 8 is 4

Example 5
Input
0,5
Output
5
Explanation

GCD with 0

Algorithm Flow

Recommendation Algorithm Flow for GCD with Euclidean Algorithm

Solution Approach

Implement the Euclidean algorithm: repeatedly replace the larger number with the remainder of division by the smaller number.

function solution(a, b) {
  while (b !== 0) {
    var t = b;
    b = a % b;
    a = t;
  }
  return a;
}

The loop runs while b is not zero. Inside, store b in a temporary variable t, set b to a % b (remainder), and set a to t (the old b). When b reaches 0, a holds the GCD. For example, with a=12, b=8: first iteration: t=8, b=12%8=4, a=8. Second: t=4, b=8%4=0, a=4. Return 4.

Many languages provide a built-in GCD function: Python's math.gcd, Java's BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)), or Rust's a.gcd(&b). The manual implementation using the Euclidean algorithm is shown here for educational purposes.

Time complexity is O(log min(a, b)). Space complexity is O(1).

Best Answers

java
class Solution {
    public int solution(int a, int b) {
        while(b!=0){int t=b;b=a%b;a=t;}return a;
    }
}