1988 AIME Problems/Problem 13
Contents
Problem
Find if
and
are integers such that
is a factor of
.
Solution 1 (Fibonacci Version 1)
Let represent the
th number in the Fibonacci sequence. Therefore,
The above uses the similarity between the Fibonacci recursion|recursive definition, , and the polynomial
.
and
Solution 2 (Fibonacci Version 2)
We can long divide and search for a pattern; then the remainder would be set to zero to solve for . Writing out a few examples quickly shows us that the remainders after each subtraction follow the Fibonacci sequence. Carrying out this pattern, we find that the remainder is
Since the coefficient of
must be zero, this gives us two equations,
and
. Solving these two as above, we get that
.
There are various similar solutions which yield the same pattern, such as repeated substitution of into the larger polynomial.
Solution 3 (Fibonacci Version 3: For Beginners, Less Technical)
Trying to divide by
would be very tough, so let's try to divide using smaller degrees of
. Doing
, we get the following systems of equations:
Continuing with
:
There is somewhat of a pattern showing up, so let's try
to verify. We get:
Now we begin to see that our pattern is actually the Fibonacci Numbers! Using the previous equations, we can make a general statement about
:
Also, noticing our solutions from the previous systems of equations, we can create the following statement:
If has
as a factor, then
and
Thus, if has
as a factor, we get that
and
so
.
Solution 4 (Fibonacci Version 4: Not Rigorous)
Let's work backwards! Let and let
be the polynomial such that
.
Clearly, the constant term of must be
. Now, we have
, where
is some coefficient. However, since
has no
term, it must be true that
.
Let's find now. Notice that all we care about in finding
is that
. Therefore,
. Undergoing a similar process,
,
,
, and we see a nice pattern. The coefficients of
are just the Fibonacci sequence with alternating signs! Therefore,
, where
denotes the 16th Fibonnaci number and
.
Solution 5 (Fibonacci Version 5)
The roots of are
(the Golden Ratio) and
. These two must also be roots of
. Thus, we have two equations:
and
. Subtract these two and divide by
to get
. Noting that the formula for the
th Fibonacci number is
, we have
. Since
and
are coprime, the solutions to this equation under the integers are of the form
and
, of which the only integral solutions for
on
are
and
.
cannot work since
does not divide
, so the answer must be
. (Note that this solution would not be valid on an Olympiad or any test that does not restrict answers as integers between
and
).
Solution 6 (Decreases the Powers)
We are given that is a factor of
so the roots of
are roots of
Let be a root of
so that
or
Note that
See also
1988 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 12 |
Followed by Problem 14 | |
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.