Two numbers are relatively prime (also called coprime or mutually prime) if their greatest common divisor (gcd) is 1.
What is a Greatest Common Divisor?
A greatest common divisor is the largest number that divides both numbers. For example, the gcd of:
- 5 and 100 = 5,
- 12, and 48 = 12,
- 100, and 10,000 = 100.
None of the above examples though, give the greatest common divisor as 1—which is what we want if we’re to call them coprimes. The only way numbers are coprimes is if the numbers being divided have no common factors (other than 1). For example, 24 and 35 are coprime:
- 24 (factors are 1, 2, 4, 6, 8, 12, 24)
- 35 (factors are (1, 3, 5, 7, 15);
- The only common factor (bolded) is 1.
How to Find Relatively Prime Numbers
You have a couple of options to find coprimes:
- By hand,
- Use a coprime calculator.
Tip: Any reduced fraction (a fraction that cannot be simplified any further) is relatively prime. For example, 24/25 is relatively prime.
By Hand
By hand, it’s fairly easy to find coprimes for small numbers. Just list out all of the factors (divisors) for each number and compare the lists. For example, let’s say you wanted to find out if 21 and 44 were coprimes:
- Factors of 21: 1, 3, 7, 21.
- Factors of 44: 1, 2, 4, 11, 22, 44.
The only factor in common is 1, therefore 21 and 44 are relatively prime.
For larger numbers (e.g. 9,912), it becomes a little more tedious. For example, the factors of 9,912 are: (1, 2, 3, 4, 6, 6, 8, 12, 14, 21, 24, 28, 42, 56, 59, 84, 118, 168, 177, 236, 354, 413, 472, 708, 826, 826, 1239, 1416, 1652, 2478, 3304, 4956, 9912).
Another “by hand” option is to use the Euclidean algorithm. Although it’s faster than writing out all of the factors, it’s still a lengthy process, involving several division steps. The steps are (from Stephen Greenfield’s page):
- Input Two positive integers, a and b.
- Output The greatest common divisor, g, of a and b.
- Internal computation
- If a < b, exchange a and b.
- Divide a by b and get the remainder, r. If r = 0, report b as the GCD of a and b.
- Replace a by b and replace b by r. Return to the previous step.
It’s obviously subject to arithmetic errors unless you’re very careful. So, unless you have to find coprimes by hand (for example, your professor requires it or perhaps you’re doing it “for fun”, you may want to use a calculator for larger numbers.
Coprime Calculator
This simple calculator will tell you if your numbers are coprimes (relatively prime) or not coprimes (not relatively prime). Enter each number separated by a comma:
References
Johnston, B. & Richman, F. (1997). Numbers and Symmetry: An Introduction to Algebra. CRC Press.
UTM Prime Glossary. greatest common divisor