**I just announced the new *** Learn Spring * course, focused on the fundamentals of Spring 5 and Spring Boot 2:

*Learn Spring*course, focused on the fundamentals of Spring 5 and Spring Boot 2:

Last modified: April 5, 2019

Given two integers, *a* and *b*, we say that they are **relatively prime if the only factor that divides both is 1. Mutually prime or coprime are synonyms for relatively prime numbers.**

In this quick tutorial, we’ll walk through a solution to this problem using Java.

As it turns out, if the greatest common divisor (*gcd*) of 2 numbers *a* and *b* is 1 (i.e. *gcd(a, b) = 1*) then *a* and *b* are relatively prime. As a result, determining whether two numbers are relatively prime consists simply of finding if the *gcd* is 1.

In this section, we’ll use the Euclidean algorithm to calculate the *gcd* of 2 numbers.

Before we show our implementation, let’s summarize the algorithm and look at a quick example of how to apply it for the sake of understanding.

So, imagine we have two integers, *a* and *b*. In the iterative approach, we first divide *a* by *b* and get the remainder. Next, we assign *a* the value of *b*, and we assign *b* the remainder value. We repeat this process until *b* = *0*. Finally, when we reach this point, we return the value of *a* as the *gcd* result, and if *a* = *1*, we can say that *a* and *b* are relatively prime.

Let’s try it out on two integers, *a = 81 *and *b = 35*.

In this case, the remainder of *81 *and *35 (81 % 35) *is *11*. So, in the first iteration step, we end with *a = 35* and *b = 11*. Consequently, we’ll do another iteration.

The remainder of *35* divided by *11 *is *2*. As a result, we have now *a = 11* (we swapped values) and *b = 2*. Let’s keep going.

One more step will result in *a = 2* and *b = 1*. Now, we’re getting close to the end.

Lastly, after one more iteration, we’ll reach *a = 1 *and *b = 0*. The algorithm returns *1* and we can conclude that *81 *and *35* are indeed relatively prime.

First, let’s implement the imperative Java version of the Euclidean algorithm as described above:

int iterativeGCD(int a, int b) { int tmp; while (b != 0) { if (a < b) { tmp = a; a = b; b = tmp; } tmp = b; b = a % b; a = tmp; } return a; }

As we can notice, in the case where *a *is less than *b*, we swap the values before continuing. The algorithm stops when *b *is 0.

Next, let’s look at a recursive implementation. This is probably cleaner since it avoids explicit variable value swaps:

int recursiveGCD(int a, int b) { if (b == 0) { return a; } if (a < b) { return recursiveGCD(b, a); } return recursiveGCD(b, a % b); }

But wait — isn’t the *gcd* algorithm already implemented in Java? Yes, it is! The *BigInteger* class provides a *gcd* method that implements the Euclidean algorithm for finding the greatest common divisor.

Using this method, we can more easily draft the relatively prime algorithm as:

boolean bigIntegerRelativelyPrime(int a, int b) { return BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)).equals(BigInteger.ONE); }

In this quick tutorial, we’ve presented a solution to the problem of finding if two numbers are relatively prime using three implementations of the *gcd* algorithm.

And, as always, the sample code is available over on GitHub.