Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

counting and probability intermediate

Problem

Two integers are relatively prime if they have no common factors other than 1 or -1. What is the probability that a positive integer less than or equal to 30 is relatively prime to 30? Express your answer as a common fraction.
Solution
It might be easier to find the integers less than or equal to 30 which are NOT relatively prime to 30. They include 2, 4, 6, 8, 10, , 28, 30, or 15 even integers. They also include 3, 9, 15, 21, 27, or the odd multiples of 3. And also, 5, 25, the multiples of 5 relatively prime to 2 and 3. So we have a total of numbers sharing a factor with 30. So there are 8 relatively prime integers, giving us a ratio of .

Notice that the prime divisors of 30 are 2, 3, and 5, and we have which equals the number of positive integers less than 30 that are relatively prime to 30. Is this a coincidence?
Final answer
\frac{4}{15}