2021 AIME I Problems/Problem 10
Contents
Problem
Consider the sequence of positive rational numbers defined by and for , if for relatively prime positive integers and , then
Determine the sum of all positive integers such that the rational number can be written in the form for some positive integer .
Solution 1
We know that when so is a possible value of . Note also that for . Then unless and are not relatively prime which happens when divides (by the Euclidean Algorithm), or divides . Thus, the least value of is and . We know . Now unless and are not relatively prime which happens the first time divides or divides or , and . We have . Now unless and are not relatively prime. This happens the first time divides implying divides , which is prime so and . We have . We have , which is always reduced by EA, so the sum of all is .
~sugar_rush
Remark
Whenever a fraction is in the form in lowest terms, the difference between the numerator and the denominator in the original fraction will always divide the numerator. We can model as (not necessarily simplified) if for integers and . We want the least such that . Let be a divisor of both and , then , so . This follows from the Euclidean Algorithm.
Solution 2 (Euclidean Algorithm and Generalization)
Let be all terms in the form where and is some positive integer.
We wish to find Suppose for some positive integer
To find we look for the smallest positive integer for which is reducible:
If is reducible, then there exists a common factor for and By the Euclidean Algorithm, we have Since and are not relatively prime, and is fixed, the smallest value of such that is reducible occurs when is the smallest prime factor of
We will prove that for such value of the number can be written in the form where must be a positive integer.
We start with and then find by filling out the table below recursively: As the answer is
Remark
Alternatively, from we can set We cross-multiply, rearrange, and apply Simon's Favorite Factoring Trick to get Since to find the smallest we need to be the smallest prime factor of Now we continue with the last two paragraphs of the solution above.
~MRENTHUSIASM
Video Solution
https://youtu.be/oiUcYn1uYMM ~Math Problem Solving Skills
Video Solution by Punxsutawney Phil
https://youtube.com/watch?v=LIjTty3rVso
See Also
2021 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 9 |
Followed by Problem 11 | |
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.