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 a Prime Factor
Repeat Step 2
Continue Until All Prime Factors Are Discovered
Select an integer for which you would like to calculate coprime numbers. For example, select the number 66.
Select a prime number 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 × 3 × 11.
Calculate Coprime Numbers
Write Integers in Descending Order
Eliminate Multiples
Conclude With Coprimes
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 × 3 × 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.