2005 PMWC Problems/Problem I3
Problem
Let be a fraction between and . If the denominator of is and the numerator and denominator have no common factor except , how many possible values are there for ?
Solution
We let .
We find the ranges for , disregarding the restriction that must be relatively prime with 455.
, .
,
Since must be relatively prime to 455, it cannot have any prime factors equal to any in . Thus we use the Principle of Inclusion-Exclusion and complementary counting:
There are 43 multiples of 5 in that range.
There are 31 multiples of 7 in that range.
There are 16 multiples of 13 in that range.
There are 6 multiples of 7*5=35 in that range.
There are 3 multiples of 5*13=65 in that range.
There are 2 multiples of 7*13=91 in that range.
There aren't any multiples of 455 in that range.
Now there are numbers total, so subtracting the unsuccessful numbers(79) from that we get possible values of .