Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

counting and probability intermediate

Problem

How many natural numbers greater than 6 but less than 60 are relatively prime to 15?
Solution
We are interested in how many numbers among are relatively prime to 15.

First, we count how many numbers among are relatively prime to 15. Note that . Among these 60 numbers, are multiples of 3, are multiples of 5, and are multiples of 15. We can take 60, and subtract 20 and 12, but we have subtracted the multiples of 15 twice. Therefore, among the 60 numbers, there are numbers that are relatively prime to 15.

Going back to the set , we must account for the numbers 1, 2, and 4 that are relatively prime to 15. Thus, the answer is .
Final answer
29