2016 AMC 12B Problems/Problem 25
Contents
Problem
The sequence is defined recursively by
,
, and
for
. What is the smallest positive integer
such that the product
is an integer?
Solution 1
Let . Then
and
for all
. The characteristic polynomial of this linear recurrence is
, which has roots
and
.
Therefore, for constants to be determined
. Using the fact that
we can solve a pair of linear equations for
:
.
Thus ,
, and
.
Now, , so we are looking for the least value of
so that
.
Note that we can multiply all by three for convenience, as the
are always integers, and it does not affect divisibility by
.
Now, for all even the sum (adjusted by a factor of three) is
. The smallest
for which this is a multiple of
is
by Fermat's Little Theorem, as it is seen with further testing that
is a primitive root
.
Now, assume is odd. Then the sum (again adjusted by a factor of three) is
. The smallest
for which this is a multiple of
is
, by the same reasons. Thus, the minimal value of
is
.
Solution 2
Since the product is an integer, the sum of the logarithms
must be an integer. Multiply all of these logarithms by
, so that the sum must be a multiple of
. We take these vales modulo
to save calculation time. Using the recursion
:
Notice that
. The cycle repeats every
terms. Since
and
, we only need the first
terms to sum up to a multiple of
:
. (NOTE: This solution proves 17 is the upper bound, but since 17 is the lowest answer choice, it is correct. To rigorously prove it, you will have to add up the mods listed until you get
.
See Also
2016 AMC 12B (Problems • Answer Key • Resources) | |
Preceded by Problem 24 |
Followed by Last Problem |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | |
All AMC 12 Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.