2014 AIME I Problems/Problem 3
Contents
Problem 3
Find the number of rational numbers 
such that when 
is written as a fraction in lowest terms, the numerator and the denominator have a sum of 1000.
Solution 1
We have that the set of these rational numbers is from 
to 
where each each element 
has 
and is irreducible.
We note that 
.
Hence, is irreducible if 
is irreducible, and is irreducible if 
is not divisible by 2 or 5. Thus, the answer to the question is the number of integers between 999 and 501 inclusive that are not divisible by 2 or 5.
We note there are 499 numbers between 501 and 999, and
- 249 numbers are divisible by 2
- 99 numbers are divisible by 5
- 49 numbers are divisible by 10
Using the Principle of Inclusion and Exclusion, we get that there are 
numbers between 
and 
are not divisible by either 
or 
, so our answer is 
.
Euler's Totient Function can also be used to arrive at 400 numbers relatively prime to 1000, meaning 200 possible fractions satisfying the necessary conditions.
Solution 2
If the initial manipulation is not obvious, instead ,consider the euclidean algorithm. Instead of using 
as the fraction to use the euclidean algorithm on, rewrite this as 
. Thus, we want gcd(1000,500-x)=1. You can either proceed as solution 1, or consider that no even numbers work, limiting us to 250 choices of numbers and restricting x to be odd. If x is odd, 500-x is odd, so the only possible common factors 1000 and 500-x can share are multiples of 5. Thus, we want to avoid these. There are 50 multiples of 5 less than 500, so the answer is 
.
See also
| 2014 AIME I (Problems • Answer Key • Resources) | ||
| Preceded by Problem 2 |
Followed by Problem 4 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
| All AIME Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
