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
or
divides
, so 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 Note to author: Were you on a sugar rush when you wrote this? lol
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.