Difference between revisions of "2008 IMO Problems/Problem 3"
Line 1: | Line 1: | ||
The main idea is to take a gaussian prime <math>a+bi</math> and multiply it by a "twice as small" <math>c+di</math> to get <math>n+i</math>. The rest is just making up the little details. | The main idea is to take a gaussian prime <math>a+bi</math> and multiply it by a "twice as small" <math>c+di</math> to get <math>n+i</math>. The rest is just making up the little details. | ||
− | |||
− | For each | + | == Solution == |
+ | |||
+ | For each ''sufficiently large'' prime <math>p</math> of the form <math>4k+1</math>, we shall find a corresponding <math>n</math> satisfying the required condition with the prime number in question being <math>p</math>. Since there exist infinitely many such primes and, for each of them, <math>n \ge \sqrt{p-1}</math>, we will have found infinitely many distinct <math>n</math> satisfying the problem. | ||
Take a prime <math>p</math> of the form <math>4k+1</math> and consider its "sum-of-two squares" representation <math>p=a^2+b^2</math>, which we know to exist for all such primes. As <math>a\ne b</math>, assume without loss of generality that <math>b>a</math>. If <math>a=1</math>, then <math>n=b</math> is our guy, and <math>p=n^2+1 > 2n+\sqrt{2n}</math> as long as <math>p</math> (and hence <math>n</math>) is large enough. Let's see what happens when <math>b>a>1</math>. | Take a prime <math>p</math> of the form <math>4k+1</math> and consider its "sum-of-two squares" representation <math>p=a^2+b^2</math>, which we know to exist for all such primes. As <math>a\ne b</math>, assume without loss of generality that <math>b>a</math>. If <math>a=1</math>, then <math>n=b</math> is our guy, and <math>p=n^2+1 > 2n+\sqrt{2n}</math> as long as <math>p</math> (and hence <math>n</math>) is large enough. Let's see what happens when <math>b>a>1</math>. |
Revision as of 00:11, 4 September 2008
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.
Solution
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 our guy, and
as long as
(and hence
) is large enough. Let's see what happens when
.
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 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,