2008 IMO Problems/Problem 3
Problem
Prove that there are infinitely many positive integers such that
has a prime divisor greater than
.
Solution
Solution 1
The main idea is to take a gaussian prime and multiply it by a "twice as small"
to get
. The rest is just making up the little details.
For each sufficiently large prime of the form
, we shall find a corresponding
such that
divides
and
. Since there exist infinitely many such primes and, for each of them,
, we will have found infinitely many distinct
satisfying the hypothesis.
Take a prime of the form
and consider its "sum-of-two squares" representation
, which we know to exist for all such primes. As
, assume without loss of generality that
. If
, then
is what we are looking for, and
as long as
(and hence
) is large enough. Assume from now on that
.
Since and
are (obviously) co-prime, there must exist integers
and
such that
In fact, if
and
are such numbers, then
and
work as well for any integer
, so we can assume that
.
Define and let's see why this is a good choice. For starters, notice that
.
If , from (1) we see that
must divide
and hence
. This implies,
and
. Therefore,
, so
. Finally,
and the case
is cleared.
We can safely assume now that
As
implies
, we have
so
Therefore,
Before we proceed, we would like to show first that . Observe that the function
over
reaches its minima on the ends, so
given
is minimized for
, where it equals
. So we want to show that
which is not hard to show for large enough
.
Now armed with and (2), we get
\[4(n^2+1) & \le p( a^2+b^2 - 2(a+b-1) ) \\ & < p( p-2\sqrt{p} ) \\ & < u^2(u-1)^2,\] (Error compiling LaTeX. Unknown error_msg)
where
Finally,
The proof is complete.
Solution 2
We begin with a lemma.
Lemma: For every prime , there exists a positive integer
such that
.
Proof:
We know that there must be a solution to the equation
with
. However, if
is a solution then so is
, so there must be a solution
. Let
denote this solution and suppose that
. Then, we have
Since
is a positive integer, it follows that
, so we have
as desired. The lemma is proven.
Suppose for sake of contradiction that there are only finitely many integers that work. Let
be a prime with
and such that
is relatively prime to
for all
(the existence of
is guaranteed by the existence of infinitely many primes of the form
). Then, we know that there exists an
such that
and
(this last condition shows that
is not among
. We want to show that
But, we know that
, so it suffices to show that
Once again, it suffices to show that
which follows from
.
Thus, satisfies the required condition and it follows that there exist infinitely many values of
that satisfy the given condition, as desired.