Difference between revisions of "2008 IMO Problems/Problem 3"
Line 1: | Line 1: | ||
− | + | == Problem == | |
Prove that there are infinitely many positive integers <math>n</math> such that <math>n^{2} + 1</math> has a prime divisor greater than <math>2n + \sqrt {2n}</math>. | Prove that there are infinitely many positive integers <math>n</math> such that <math>n^{2} + 1</math> has a prime divisor greater than <math>2n + \sqrt {2n}</math>. | ||
Line 11: | Line 11: | ||
Since <math>a</math> and <math>b</math> are (obviously) co-prime, there must exist integers <math>c</math> and <math>d</math> such that | Since <math>a</math> and <math>b</math> are (obviously) co-prime, there must exist integers <math>c</math> and <math>d</math> such that | ||
− | <cmath>ad+bc=1 \ | + | <cmath>ad+bc=1. \quad(1)</cmath> |
In fact, if <math>c</math> and <math>d</math> are such numbers, then <math>c\pm ma</math> and <math>d\mp mb</math> work as well for any integer <math>m</math>, so we can assume that <math>c \in \left[-\frac{a}{2}, \frac{a}{2}\right]</math>. | In fact, if <math>c</math> and <math>d</math> are such numbers, then <math>c\pm ma</math> and <math>d\mp mb</math> work as well for any integer <math>m</math>, so we can assume that <math>c \in \left[-\frac{a}{2}, \frac{a}{2}\right]</math>. | ||
Line 26: | Line 26: | ||
<cmath>|d| \le \frac{b-1}{2}.</cmath> | <cmath>|d| \le \frac{b-1}{2}.</cmath> | ||
− | <cmath>n^2+1 = (a^2+b^2)(c^2+d^2) \le p\left( \frac{(a-1)^2}{4}+\frac{(b-1)^2}{4} \right).\ | + | <cmath>n^2+1 = (a^2+b^2)(c^2+d^2) \le p\left( \frac{(a-1)^2}{4}+\frac{(b-1)^2}{4} \right). \quad (2)</cmath> |
− | Before we proceed, we would like to show that <math>a+b-1 > \sqrt{p}</math>. Observe that the function <math>x+\sqrt{p-x^2}</math> over <math>x\in(2,\sqrt{p-4})</math> reaches its minima on the ends, so <math>a+b</math> given <math>a^2+b^2=p</math> is minimized for <math>a = 2</math>, where it equals <math>2+\sqrt{p-2^2}</math>. So we want to show that <cmath>2+\sqrt{p-4} > \sqrt{p} + 1,</cmath> | + | Before we proceed, we would like to show first that <math>a+b-1 > \sqrt{p}</math>. Observe that the function <math>x+\sqrt{p-x^2}</math> over <math>x\in(2,\sqrt{p-4})</math> reaches its minima on the ends, so <math>a+b</math> given <math>a^2+b^2=p</math> is minimized for <math>a = 2</math>, where it equals <math>2+\sqrt{p-2^2}</math>. So we want to show that <cmath>2+\sqrt{p-4} > \sqrt{p} + 1,</cmath> |
which obviously holds for large <math>p</math>. | which obviously holds for large <math>p</math>. | ||
Revision as of 00:24, 4 September 2008
Problem
Prove that there are infinitely many positive integers such that
has a prime divisor greater than
.
Solution
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
satisfying the required condition with the prime number in question being
. Since there exist infinitely many such primes and, for each of them,
, we will have found infinitely many distinct
satisfying the problem.
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 was a good choice. For starters, notice that
.
If , then from (1), we see that
must divide
and hence
. In turn,
and
. Therefore,
and so
, from where
. Finally,
and the case
is cleared.
We can safely assume now that
As
implies
, we have
so
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 obviously holds for large
.
Now armed with and (2), we get
where
Finally,