Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

number theory senior

Problem

How many fractions in the form , with , are in lowest terms?
Solution
The prime factorization of 99 is . So for to be in lowest terms, cannot be divisible by 3 or 11. The possible values of are from 1 to 98, inclusive, so there are 98 possible values for . We can find the number of multiples of 3 and multiples of 11 and subtract from 98 to get the number of values that aren't divisible by 3 or 11. For multiples of 3, we go from 3 to 96, or to , so there are 32 multiples of 3 from 1 to 98, inclusive. For multiples of 11, we go from 11 to 88, so there are 8 multiples of 11 from 1 to 98, inclusive. We have to make sure we don't double-count the numbers that are multiples of both 3 and 11: 33 and 66. So there are values of that are divisible by 3 or 11. That means there are values of for which is in lowest terms.
Final answer
60