# Difference between revisions of "2005 PMWC Problems/Problem I3"

(New page: ==Problem== Let <math>x</math> be a fraction between <math>\frac{35}{36}</math> and <math>\frac{91}{183}</math>. If the denominator of <math>x</math> is <math>455</math> and the numerator...) |
(→Solution) |
||

Line 16: | Line 16: | ||

There are 43 multiples of 5 in that range. | There are 43 multiples of 5 in that range. | ||

+ | |||

There are 31 multiples of 7 in that range. | There are 31 multiples of 7 in that range. | ||

+ | |||

There are 16 multiples of 13 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 6 multiples of 7*5=35 in that range. | ||

+ | |||

There are 3 multiples of 5*13=65 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 are 2 multiples of 7*13=91 in that range. | ||

+ | |||

There aren't any multiples of 455 in that range. | There aren't any multiples of 455 in that range. | ||

## Revision as of 11:01, 18 September 2008

## 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 .