Finding the GCD and LCM (the Euclidean Algorithm)

This lesson covers finding the greatest common divisor and least common multiple in Java using the Euclidean algorithm, so you understand a mathematical algorithm using recursion. It's for anyone searching "Java GCD LCM implementation."

The Euclidean algorithm is an ancient, efficient algorithm for finding the greatest common divisor (GCD) of two numbers. It keeps repeating "divide the larger by the smaller and take the remainder" until the remainder is 0.

The example's gcd() method expresses the recursive logic in a single line using the ternary operator: b == 0 ? a : gcd(b, a % b). Since the least common multiple relates to the GCD as a * b / gcd(a, b), lcm() reuses the GCD result to compute it.

A common early mistake is not knowing the relationship between GCD and LCM. Once you have the GCD, finding the LCM is easy with just multiplication and division.

This is a well-known algorithm frequently used to practice writing recursive functions, packed with both mathematical and programming fundamentals.

📖 Reference code

static int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

static int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

System.out.println("GCD: " + gcd(12, 18));
System.out.println("LCM: " + lcm(4, 6));

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run Java directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser — nothing is sent anywhere).