Find GCD in Java

What you’ll learn

  • Definition of gcd(a,b) and special case gcd(0,n).
  • Iterative and recursive Euclidean algorithm in Java.
  • Practical uses in fractions, modular arithmetic, and LCM.

Prerequisites

  • Java basics: methods, loops, and % remainder.
  • Use Math.abs to normalize signs before Euclid.

Reduction rule

gcd(a,b) = gcd(b, a % b) for b != 0, so each step reduces the problem size.

Intuition

gcd(48,18) -> gcd(18,12) -> gcd(12,6) -> gcd(6,0) = 6.

Live preview

Enter two integers and compute gcd using Euclid.

Try (48,18), (17,13), or (0,21).

Live result
Press "Compute gcd".

Algorithm

Goal: compute gcd(a,b) using Euclid's reduction.

Normalize signs

Use Math.abs so the final gcd is nonnegative.

Euclidean loop

While b != 0, set (a,b) = (b, a % b).

Return answer

When b == 0, return a.

📜 Pseudocode

Pseudocode
function gcd(a, b):
    a = abs(a)
    b = abs(b)
    while b != 0:
        (a, b) = (b, a mod b)
    return a
1

Iterative Euclidean algorithm

java
public class Main {
    static int findGcd(int num1, int num2) {
        num1 = Math.abs(num1);
        num2 = Math.abs(num2);
        while (num2 != 0) {
            int temp = num2;
            num2 = num1 % num2;
            num1 = temp;
        }
        return num1;
    }

    public static void main(String[] args) {
        int number1 = 48;
        int number2 = 18;
        System.out.println("GCD of " + number1 + " and " + number2 + " is: " + findGcd(number1, number2));
    }
}
📤 Output
GCD of 48 and 18 is: 6
2

Recursive Euclidean algorithm

java
public class Main {
    static int gcdRecursive(int a, int b) {
        a = Math.abs(a);
        b = Math.abs(b);
        if (b == 0) return a;
        return gcdRecursive(b, a % b);
    }

    public static void main(String[] args) {
        int number1 = 48;
        int number2 = 18;
        System.out.println("GCD of " + number1 + " and " + number2 + " is: " + gcdRecursive(number1, number2));
    }
}
📤 Output
GCD of 48 and 18 is: 6

Applications

Fractions: reduce p/q by dividing numerator and denominator by gcd.

LCM: lcm(a,b) = |a*b| / gcd(a,b).

Also used in: modular inverse, Diophantine equations, and cryptography basics.

Optimization note

Euclid is already optimal for interview-sized int/long inputs.

For very large integers, use BigInteger.gcd.

❓ FAQ

The greatest common divisor of a and b is the largest positive integer that divides both.
For n > 0, gcd(0, n) = n. For gcd(0,0), many programs return 0 by convention.
Repeat (a,b) = (b, a % b) until b becomes 0. Then a is gcd.
Java % keeps sign of dividend. For clean gcd, normalize with Math.abs first.
Both are good. Iterative avoids recursive call stack.
O(log min(a,b)) Euclidean steps in worst case.

🔄 Input / output examples

(a,b)gcd
(48, 18)6
(17, 13)1
(0, 21)21

Edge cases

0,0

Convention

gcd(0,0) is convention-based; this page returns 0.

Sign

Negative values

Normalize signs before Euclid for predictable positive gcd.

Large values

Type width

For very large values, prefer long or BigInteger.

⏱️ Time and space complexity

VersionTimeExtra space
Iterative EuclidO(log min(a,b))O(1)
Recursive EuclidO(log min(a,b))O(log min(a,b)) stack

Summary

  • Use Euclid update (a,b) = (b, a % b) until b = 0.
  • Normalize signs and define behavior for gcd(0,0).
Did you know?

Bezout identity: for integers a, b not both zero, there exist integers x, y with gcd(a,b) = a*x + b*y. Extended Euclid finds these coefficients.

About the author

Mari Selvan M P
Mari Selvan M P 🔗

Developer, cloud engineer, and technical writer

  • Experience 12 years building web and cloud systems
  • Focus Full Stack Development, AWS, and Developer Education

I write practical tutorials so students and working developers can learn by doing—from databases and APIs to deployment on AWS.

AWS Certified Developer – Associate (Credly)

8 people found this page helpful

Java Program to Display Fibonacci Series Java Program to Check Happy Number