How to Calculate a Coprime

••• Sky_Blue/iStock/GettyImages

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 × 7) and 9 (3 × 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.

Factor the First Number

  1. Select an Integer

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

  3. Select a Prime Factor

  4. Select a prime number that evenly divides the chosen number. In this example, 2 divides 66 evenly, since 66 = 2 × 33.

  5. Repeat Step 2

  6. 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.

  7. Continue Until All Prime Factors Are Discovered

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

Calculate Coprime Numbers

  1. Write Integers in Descending Order

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

  3. Eliminate Multiples

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

  5. Conclude With Coprimes

  6. 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.


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.

Dont Go!

We Have More Great Sciencing Articles!