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.
