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 (Euclidean algorithm, fast)
Let the numerator and denominator with and Now if then Therefore any pair that works satisfies By Euler's totient theorem, there are numbers relatively prime to 1000 from 1 to 1000. Recall that and note by Euclidean algorithm , so we want Thus the relatively prime numbers can generate desired fractions.
Solution 2
If the initial manipulation is not obvious, consider the Euclidean Algorithm. Instead of using as the fraction to use the Euclidean Algorithm on, we can rewrite this as or Thus, we want . You can either proceed as Solution , or consider that no even numbers work, limiting us to choices of numbers and restricting to be odd. If is odd, is odd, so the only possible common factors and can share are multiples of . Thus, we want to avoid these. There are multiples of less than , so the answer is .
Solution 3
Say ; then . If this fraction is reducible, then the modulus of some number for is the same as the modulus for . Since , that modulus can only be or . This implies that if or , the fraction is reducible. There are cases where , where , and where , so by PIE, the number of fails is , so our answer is .
Solution 4
We know that the numerator of the fraction cannot be even, because the denominator would also be even. We also know that the numerator cannot be a multiple of because the denominator would also be a multiple of . Proceed by listing out all the other possible fractions and we realize that the numerator and denominator are always relatively prime. We have fractions to start with, and with odd numerators. Subtract to account for the multiples of , and we get .
Solution 5
We know 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 or . Thus, the answer to the question is the number of integers between and inclusive that are not divisible by or .
We note there are numbers between and , and
- numbers are divisible by
- numbers are divisible by
- numbers are divisible by
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 numbers relatively prime to , meaning possible fractions satisfying the necessary conditions. Solution 1 is a more detailed solution utilizing Euler's totient.
Solution 6
We notice that there are a total of fractions that are in simplest form where the numerator and denominator add up to . Because the numerator and denominator have to be relatively prime, there are fractions. Half of these are greater than , so the answer is
- bedwarsnoob
~MathFun1000 (Minor Edits)
Solution 7
Our fraction can be written in the form Thus the fraction is reducible when divides We also want By PIE, the total values of that make the fraction reducible is, By complementary counting, the answer we want is
Solution 8 (Simplest)
Suppose our fraction is . The given condition means . Now, if and share a common factor greater than , then the expression must also contain that common factor. This means our fraction cannot have a factor of or be even.
There are fractions that aren’t even. From this, are divisible by , which means the answer is
~Geometry285
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.