Mock AIME 2 2006-2007 Problems/Problem 8
Problem
The positive integers satisfy
and
for
. Find the last three digits of
.
Solution
This solution is rather long and unpleasant, so a nicer solution may exist:
From the givens, and so
and
.
Note that this factorization of 144 contains a pair of consecutive integers, and
. The factors of 144 are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72 and 144 itself. As both
and
are positive integers,
, so we must have
equal to one of 2, 3 and 8.
If then
and so
from which
. It is clear that this equation has no solutions if
, and neither
nor
is a solution, so in this case we have no solutions.
If then
so
. It is clear that
is the unique solution to this equation in positive integers. Then
and our sequence is
.
If then either:
a) and so
so
, which has no solutions in positive integers
or
b) and so
so
which has solution
. Then our sequence becomes
.
Thus we see there are two possible sequences, but in both cases the answer is 456.