BlackWaspTM

This web site uses cookies. By using the site you accept the cookie policy.This message is for compliance with the UK ICO law.

Algorithms and Data Structures
.NET 1.1+

Determining if Values are Coprime

Two integer values are said to be coprime, or relatively prime, when they share no common divisors other than the number one. This article describes the process for determining whether two positive values are coprime, with C# example code.

Coprime Numbers

All integer values can be expressed as the product of their prime factors. These are the prime numbers that, when multiplied, yield the original value. For example, the value 12 is the product of the prime numbers 2, 2 and 3. Two values are said to be coprime if they have no common prime factors. For example, the values nine (3 x 3) and ten (2 x 5) are coprime. The values eight (2 x 2 x 2) and ten (2 x 5) are not coprime as they share the common divisor of two.

You can determine if two values are coprime by using Euclid's algorithm to find their greatest common divisor (GCD). When values are coprime, their GCD is one.

Checking if Two Values are Coprime

In this section we will create a method that determines if two values are coprime. First we need an implementation of Euclid's Algorithm to obtain the GCD. We will use the modulus-based code from the article, "Euclid's Algorithm":

public static int GetGCDByModulus(int value1, int value2)
{
    while (value1 != 0 && value2 != 0)
    {
        if (value1 > value2)
            value1 %= value2;
        else
            value2 %= value1;
    }
    return Math.Max(value1, value2);
}

We can now create the method that determines if the values are coprime. This accepts the two positive integers to be tested as parameters and returns a Boolean result. The result is generated by comparing the GCD of the two values with one:

public static bool Coprime(int value1, int value2)
{
    return GetGCDByModulus(value1, value2) == 1;
}
6 December 2010