How to calculate a coprime

Updated April 17, 2017

A prime number is an integer whose only factors are itself and 1. For example, the numbers 3, 5 and 7 are prime, but 9 is divisible by 3, so it is not. Any integer can be factored into a product of prime numbers. Two integers are said to be coprime, or relatively prime, if they have no common prime factors. For example, 14 (2 x 7) and 9 (3 x 3) are coprime, yet neither is prime. Any prime number is a coprime number of every other integer by definition; hence, any integer has an infinite number of coprime numbers.

Select an integer for which you would like to calculate coprime numbers. For example, select the number 66.

Locate a list of prime numbers online, such as the MathIsFun Prime Numbers Chart.

Go through the prime numbers in ascending order and find the first one that evenly divides the chosen number. In this example, 2 divides 66 evenly, since 66 = 2 * 33.

Note the factor you determined, and perform that process again on the number you obtained by your division. In this example, you will now factor the number 33, and you will find that the next prime factor is 3, since 33 = 3 * 11.

Continue this procedure until you have expressed the chosen number as a product of prime numbers. In this example, 66 = 2 x 3 x 11.

Write down all integers in a given range in ascending order. For example, write down the integers from 1 through 65.

Cross out all multiples of the prime factors of the number you selected. In this case, 66 = 2 x 3 x 11, so cross out all multiples of 2. Do the same for the numbers 3 and 11.

Look at the remaining numbers on your list. These are the coprime numbers of the chosen number in the range you selected. In this example, the coprime numbers of 66 between 1 and 65 are 5, 7, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 59, 61 and 65.

Things You'll Need

  • Pencil and paper
  • Calculator (optional)
Cite this Article A tool to create a citation to reference this article Cite this Article

About the Author

Jim Dorsch has been a writer and editor since 1991. He has written for major newspapers, including "The Washington Post" and "Chicago Tribune," and is publisher and editor of "American Brewer" magazine. He holds a Bachelor of Science in mathematics from Rose-Hulman Institute of Technology and a Master of Science in statistics from Purdue University.