2006 USAMO Problems/Problem 3
Problem
For integral , let
be the greatest prime divisor of
. By convention, we set
and
. Find all polynomials
with integer coefficients such that the sequence
is bounded above. (In particular, this requires
for
.)
Solution
Let be a non-constant polynomial in
of degree
with
integer coefficients, suppose further that no prime divides all the
coefficients of
(otherwise consider the polynomial obtained by
dividing
by the gcd of its coefficients). We further normalize
by multiplying by
, if necessary, to ensure that the
leading coefficient (of
) is positive.
Let , then
is a polynomial of degree
or
more and
. Let
be the factorization
of
into irreducible factors with positive leading coefficients.
Such a factorization is unique. Let
denote the degree of
. Since
the factors
are either even
functions of
or come in pairs
with
.
Let ,
. For any other integer
let
be the largest prime factor of
.
Suppose that for some finite constant and all
we have
. Since the polynomials
divide
, the
same must be true for each of the irreducible polynomials
. A
theorem of T.~Nagell implies that if
the ratio
takes arbitrarily large values for
sufficiently
large. Since in our case the
is asymptotically bounded above
by
for large
, we conclude that all the irreducible
factors
are linear. Since linear polynomials are not even
functions of
, they must occur in pairs
,
. Without loss of generality,
.
Since the coefficients of
are relatively prime, so are
and
, and since
, neither polynomial can have
any positive integer roots, so
and thus
.
On the other hand, by Dirichlet's theorem, , since
otherwise the sequence
would yield infinitely many
prime values with
So
and
therefore
is a positive odd integer. Setting
, clearly
. Since this holds for each
factor
, it is true for the product
of all the factors
with the bound determined by the factor with the largest value of
.
Therefore, for suitable non-negative integers ,
is a
product of polynomials of the form
. Now,
since
, we conclude that
is a product of
polynomials of the form
.
Since we restricted ourselves to non-constant polynomials with
relatively prime coefficients, we can now relax this condition and
admit a possibly empty list of irreducible factors as
well as an arbitrary non-zero integer multiple
. Thus for a
suitable non-zero integer
and a possibly empty set of
non-negative integers
, we have: