## 1. Overview

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.

## 2. Greatest Common Factor Algorithm

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.

## 3. Euclidean Algorithm Implementation

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.

### 3.1. Imperative Implementation

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.

### 3.2. Recursive Implementation

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);
}
```

## 4. Using *BigInteger*‘s Implementation

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);
}
```

## 5. Conclusion

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.