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
Select an Integer
Select an integer for which you would like to calculate coprime numbers. For example, select the number 66.
Select a Prime Factor
Select a prime number that evenly divides the chosen number. In this example, 2 divides 66 evenly, since 66 = 2 × 33.
Repeat Step 2
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 Until All Prime Factors Are Discovered
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
Write Integers in Descending Order
Write down all integers in a given range in ascending order. For example, write down the integers from 1 through 65.
Eliminate Multiples
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.
Conclude With Coprimes
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.
