How To Calculate A Coprime

Mathematicians have come up with many ways to categorize and classify numbers by their properties, and coprimes are one of the more interesting classifications of pairs of numbers based on their prime factors.

But finding two numbers that are coprime isn't necessarily easy, especially if you're working it out by hand. In order to calculate a coprime, you have to first identify the prime factors of a number, then you can use the result of this to find other numbers that are coprime to it. You can also check if two numbers are coprime, which is a simpler process.

What Is a Coprime?

For any number, a coprime is a number that shares no common factors with it other than 1. In other words, if you break both numbers down into their prime factors, they only share the prime factor of 1. These numbers are also sometimes called relatively prime or mutually prime.

For example, 21 and 22 are coprime. For 21, the factors are one, three, seven and 21, but for 22 they are one, two, 11 and 22. Because the only shared member of both of these lists is one, that means 21 and 22 are coprime by definition. Of course, this process is much more difficult to achieve for bigger numbers, which will usually have more factors, but two prime numbers will automatically be coprime by definition (since they only divide by one and themselves).

Prime Factorization

The first and most important step in calculating a coprime for any given number is finding the prime factors of the number. You can go through this process for any number in a similar way, but consider a specific example, the number 35, to make the procedure more concrete. The first stage is finding a low prime that the number is divisible by: In this case, five is the obvious choice. Now you can use this number to find another factor because it must be multiplied by something, in this case seven, to get the result.

In this case, you can't find additional factors other than one and 35 itself, so you've completed the process. In general, try to divide the number by two, then by three, then five and so on through primes until you find one that works (with no remainder), then go through the same process with the result, until the result is another prime.

For example: 60 divides by two to give 30, which divides by two to give 15, which then divides by three to give five (another prime), so you can write 60 = 2 × 2 × 3 × 5. You can easily think of other numbers (like six) that are factors, but these are contained in the result above (since 6 = 2 × 3, which is in the list). Because of this, going to prime factors makes things easier.

Calculating and Checking Coprimes

Use your list of prime factors to produce an alternate number that doesn't share factors with the first (apart from one and the original number). For 35, aside from one and 35, there are factors of five and seven, so you know that any number composed of different primes is coprime.

For example, you can produce coprimes by multiplying 2, 3, 11, 13 and so on, giving:

2 × 3 = 6

3 × 3 = 9

2 × 11 = 22

3 × 11 = 33

2 × 13 = 26

3 × 13 = 39

and other coprimes

Try to find some coprimes of 60 using the same process, noting that seven, 11, 13, 17 and so on are acceptable prime number "building blocks," before reading on. You should find (for example), 77, 91, 119 and 143 as coprimes. There are additional tricks you can use as well, for example, a prime number not included as a prime factor will always be coprime, and two consecutive integers are always coprime.

Check whether two numbers are coprime by prime factorizing each one and looking for shared factors. Alternatively, you can use online tools (see Resources) to automate the process.