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 23:11, 3 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,