Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

prealgebra senior

Problem

Two numbers are said to be 'relatively prime' if their greatest common factor is 1. How many integers greater than 10 and less than 30 are relatively prime with 28?
Solution
Since , a positive integer is relatively prime with if and only if it contains neither nor in its prime factorization. In other words, we want to count the number of integers between and inclusive which are divisible by neither nor .

All of the odd numbers are not divisible by 2; there are 10 such numbers. The only one of these that is divisible by 7 is 21, so there are numbers between 10 and 30 that are relatively prime with 28.
Final answer
9