2006 SMT/Algebra Problems/Problem 1
Problem
A finite sequence of positive integers for
are defined so that
and
for
. How many of these integers are divisible by
?
Solution
Notice that . Also, if
is divisible by
, then
and
is also divisible by
. Therefore, all numbers of the form
are divisible by
.
Now, if we have a number of the form , this is equal to
and is therefore
more than a multiple of
. Similarly,
is
more than a multiple of
. Thus, the only
divisible by
are those in which
is a multiple of
.
The multiples of in
are
, and dividing all of these by
we get
. Therefore, there are
multiples of
.