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 .
See also
2005 PMWC (Problems) | ||
Preceded by Problem I2 |
Followed by Problem I4 | |
I: 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 T: 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 |