2014 AIME I Problems/Problem 3
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
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 are divisible by 2
- 99 are divisible by 5
- 49 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.
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.