# GCD of Two Numbers Problem

## Recommended Posts

Hello everyone,

I'm having trouble understanding the GCD of two numbers in Java. I'm trying to understand the algorithm and code from an online resource but I'm having trouble with the code.

The code provided is:

public static int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}

I don't understand why the code is written this way or what it is doing. Can anyone provide some insight and explain the code to me?

Thanks!

Edited by Phi for All
##### Share on other sites

The algorithm uses the fact that if x is GCD of a and b then it is GCD of a and b % a. It looks for the GCD using recursion. For example, take 21 and 15. Look for their GCD.

21 % 15 = 6. Look for GCD of 15 and 6.

15 % 6 = 3. Look for GCD of 6 and 3.

6 % 3 = 0. Aha! Return 3, this is the GCD.

##### Share on other sites

Wiki page on modulo operation(%) may be of help too.

##### Share on other sites

On 3/28/2023 at 5:04 AM, Bunty12 said:

I'm having trouble understanding the GCD of two numbers in Java. I'm trying to understand the algorithm and code from an online resource but I'm having trouble with the code.

It's the Euclidean algorithm. Study this page and work out some examples by hand to see how it works.

Actually the Wiki page is a little confusing, here's a simpler one I found.

Edited by Phi for All

## Create an account

Register a new account