Difference between revisions of "2008 IMO Problems/Problem 3"

Revision as of 20:23, 30 May 2011

Problem

Prove that there are infinitely many positive integers $n$ such that $n^{2} + 1$ has a prime divisor greater than $2n + \sqrt {2n}$ .

Solution

Solution 1

The main idea is to take a gaussian prime $a+bi$ and multiply it by a "twice as small" $c+di$ to get $n+i$ . The rest is just making up the little details.

For each sufficiently large prime $p$ of the form $4k+1$ , we shall find a corresponding $n$ such that $p$ divides $n^2+1$ and $p>2n+\sqrt{2n}$ . Since there exist infinitely many such primes and, for each of them, $n \ge \sqrt{p-1}$ , we will have found infinitely many distinct $n$ satisfying the hypothesis.

Take a prime $p$ of the form $4k+1$ and consider its "sum-of-two squares" representation $p=a^2+b^2$ , which we know to exist for all such primes. As $a\ne b$ , assume without loss of generality that $b>a$ . If $a=1$ , then $n=b$ is what we are looking for, and $p=n^2+1 > 2n+\sqrt{2n}$ as long as $p$ (and hence $n$ ) is large enough. Assume from now on that $b>a>1$ .

Since $a$ and $b$ are (obviously) co-prime, there must exist integers $c$ and $d$ such that $ad+bc=1. \quad(1)$ In fact, if $c$ and $d$ are such numbers, then $c\pm ma$ and $d\mp mb$ work as well for any integer $m$ , so we can assume that $c \in \left[-\frac{a}{2}, \frac{a}{2}\right]$ .

Define $n=|ac-bd|$ and let's see why this is a good choice. For starters, notice that $(a^2+b^2)(c^2+d^2)=n^2+1$ .

If $c=\pm\frac{a}{2}$ , from (1) we see that $a$ must divide $2$ and hence $a=2$ . This implies, $d=-\frac{b-1}{2}$ and $n=\frac{b(b-1)}{2}-2$ . Therefore, $\left(b-\frac{1}{2}\right)^2 = 1/4 + 2(n+2) > 2n$ , so $b > \sqrt{2n}+\frac{1}{2}$ . Finally, $p=b^2+2^2 > 2n+\sqrt{2n}$ and the case $c=\pm\frac{a}{2}$ is cleared.

We can safely assume now that $|c| \le \frac{a-1}{2}.$ As $b>a>1$ implies $b>2$ , we have $|d| = \left|\frac{1-bc}{a}\right| \le \frac{b(a-1)+2}{2a} < \frac{ba}{2a} = \frac{b}{2},$ so $|d| \le \frac{b-1}{2}.$

Therefore, $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)$

Before we proceed, we would like to show first that $a+b-1 > \sqrt{p}$ . Observe that the function $x+\sqrt{p-x^2}$ over $x\in(2,\sqrt{p-4})$ reaches its minima on the ends, so $a+b$ given $a^2+b^2=p$ is minimized for $a = 2$ , where it equals $2+\sqrt{p-2^2}$ . So we want to show that $2+\sqrt{p-4} > \sqrt{p} + 1,$ which is not hard to show for large enough $p$ .

Now armed with $a+b-1>\sqrt{p}$ 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 $u=\sqrt{p}.$

Finally, $u^2(u-1)^2 > 4n^2+4 > 4n^2\Rightarrow \\ u(u-1) > 2n \Rightarrow \\ (u-\frac{1}{2})^2 > 2n+\frac{1}{4} > 2n \Rightarrow \\ u > \sqrt{2n} + \frac{1}{2} \Rightarrow \\ p = u^2 > 2n + \sqrt{2n}.$ The proof is complete.--Vbarzov 03:02, 5 September 2008 (UTC)

Solution 2

We begin with a lemma.

Lemma: For every prime $p \equiv 1 \mod{4}$ , there exists a positive integer $n \le \dfrac{p - \sqrt{p-4}}{2}$ such that $p | n^2 + 1$ . Proof: We know that there must be a solution $x$ to the equation $x^2+1 \equiv 0 \mod{p}$ with $1 \le x \le p-1$ . However, if $x$ is a solution then so is $p-x$ , so there must be a solution $x \le p-1$ . Let $n$ denote this solution and suppose that $n = \frac{p-k}{2}$ . Then, we have $\left(\dfrac{p-k}{2}\right)^2 \equiv -1 \mod{4}$ $k^2 \equiv -4 \mod{4}.$ Since $k$ is a positive integer, it follows that $k \ge p-4$ , so we have $n \le \dfrac{p - \sqrt{p-4}}{2},$ as desired. The lemma is proven.

Suppose for sake of contradiction that there are only finitely many integers $n_1,n_2,\dots,n_k$ that work. Let $p \equiv 1 \mod{4}$ be a prime with $p>20$ and such that $p$ is relatively prime to $n_i^2+1$ for all $i$ (the existence of $p$ is guaranteed by the existence of infinitely many primes of the form $4k+1$ ). Then, we know that there exists an $N$ such that $N\le \dfrac{p - \sqrt{p-4}}{2}$ and $p | N^2 + 1$ (this last condition shows that $N$ is not among $n_1,n_2,\dots,n_k$ . We want to show that $p > 2N + \sqrt{2N}$ $p - 2N > \sqrt{2N}.$ But, we know that $p-2N \ge \sqrt{p-4}$ , so it suffices to show that $p-4 > 2N$ $p - 2N > 4.$ Once again, it suffices to show that $\sqrt{p-4} > 4,$ which follows from $p>20$ .

Thus, $N$ satisfies the required condition and it follows that there exist infinitely many values of $n$ that satisfy the given condition, as desired.

@@ Line 63: / Line 63: @@
 Since <math>k</math> is a positive integer, it follows that <math>k \ge p-4</math>, so we have
 <cmath>n \le \dfrac{p - \sqrt{p-4}}{2},</cmath>
-as desired.
+as desired.  The lemma is proven.
 Suppose for sake of contradiction that there are only finitely many integers <math>n_1,n_2,\dots,n_k</math> that work.  Let <math>p \equiv 1 \mod{4}</math> be a prime with <math>p>20</math> and such that <math>p</math> is relatively prime to <math>n_i^2+1</math> for all <math>i</math> (the existence of <math>p</math> is guaranteed by the existence of infinitely many primes of the form <math>4k+1</math>).  Then, we know that there exists an <math>N</math> such that <math>N\le \dfrac{p - \sqrt{p-4}}{2}</math> and <math>p | N^2 + 1</math> (this last condition shows that <math>N</math> is not among <math>n_1,n_2,\dots,n_k</math>.  We want to show that

Page

Toolbox

Search

Difference between revisions of "2008 IMO Problems/Problem 3"

Revision as of 20:23, 30 May 2011

Problem

Solution