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