Calculus How To

Relatively Prime (Coprime, Mutually Prime)

Share on

Calculus Definitions >

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). Two examples of coprime: 24 and 35; 6 and 35.


How to Find Relatively Prime Numbers

You have a couple of options to find coprimes:

  1. By hand,
  2. Use a coprime calculator.

Tip: Any reduced fraction (a fraction that cannot be simplified any further) 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
    1. If a < b, exchange a and b.
    2. Divide a by b and get the remainder, r. If r = 0, report b as the GCD of a and b.
    3. 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.

CITE THIS AS:
Stephanie Glen. "Relatively Prime (Coprime, Mutually Prime)" From CalculusHowTo.com: Calculus for the rest of us! https://www.calculushowto.com/relatively-prime-coprime-mutually/
------------------------------------------------------------------------------

Need help with a homework or test question? With Chegg Study, you can get step-by-step solutions to your questions from an expert in the field. Your first 30 minutes with a Chegg tutor is free!

Leave a Reply

Your email address will not be published. Required fields are marked *