Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2008 IMO Problems/Problem 3"
 
(28 intermediate revisions by 6 users not shown)
Line 1: Line 1:
−
(still editing...)
+
== 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>.
  
−
The main idea is to take a gaussian prime <math>a+bi</math> and multiply it by a "smaller" <math>c+di</math> to get <math>n+i</math>. The rest is just making up the little details.
+
== Solutions ==
  
−
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.
+
'''Solution 1'''
  
−
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. If <math>a=1</math> or <math>b=1</math>, then <math>n=b</math> or <math>n=a</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 both <math>a>1</math> and <math>b>1</math>.
+
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.
  
−
Since <math>a</math> and <math>b</math> are apparently co-prime, there must exist integers <math>c</math> and <math>d</math> such that
+
For each ''sufficiently large'' prime <math>p</math> of the form <math>4k+1</math>, we shall find a corresponding <math>n</math> such that <math>p</math> divides <math>n^2+1</math> and <math>p>2n+\sqrt{2n}</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 hypothesis.
−
<cmath>ad+bc=1 \reqno{(1)}</cmath>
 
−
In fact, if <math>c</math> and <math>d</math> are such numbers, then <math>c\pm a</math> and <math>d\mp b</math> work as well, so we can assume that <math>c \in \left(\frac{-a}{2}, \frac{a}{2}\right)</math>.
 
  
−
Define <math>n=|ac-bd|</math> and let's see what happens. Notice that <math>(a^2+b^2)(c^2+d^2)=n^2+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 what we are looking for, and <math>p=n^2+1 > 2n+\sqrt{2n}</math> as long as <math>p</math> (and hence <math>n</math>) is large enough. Assume from now on that <math>b>a>1</math>.
  
−
If <math>c=\pm\frac{a}{2}</math>, then from (1), we get <math>a/2</math> and hence <math>a=2</math>. That means that <math>d=-\frac{b-1}{2}</math>
+
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. \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>.
 +
 
 +
Define <math>n=|ac-bd|</math> and let's see why this is a good choice. For starters, notice that <math>(a^2+b^2)(c^2+d^2)=n^2+1</math>.
 +
 
 +
If <math>c=\pm\frac{a}{2}</math>, from (1) we see that <math>a</math> must divide <math>2</math> and hence <math>a=2</math>. This implies, <math>d=-\frac{b-1}{2}</math> and <math>n=\frac{b(b-1)}{2}-2</math>. Therefore,
 +
<math>\left(b-\frac{1}{2}\right)^2 = 1/4 + 2(n+2) > 2n</math>, so <math>b > \sqrt{2n}+\frac{1}{2}</math>. Finally, <math>p=b^2+2^2 > 2n+\sqrt{2n}</math> and the case <math>c=\pm\frac{a}{2}</math> is cleared.
 +
 
 +
We can safely assume now that
 +
<cmath>|c| \le \frac{a-1}{2}.</cmath>
 +
As <math>b>a>1</math> implies <math>b>2</math>, we have
 +
<cmath>|d| = \left|\frac{1-bc}{a}\right| \le \frac{b(a-1)+2}{2a} < \frac{ba}{2a} = \frac{b}{2},</cmath>
 +
so
 +
<cmath>|d| \le \frac{b-1}{2}.</cmath>
 +
 
 +
Therefore,
 +
<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 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 is not hard to show for ''large enough'' <math>p</math>.
 +
 
 +
Now armed with <math>a+b-1>\sqrt{p}</math> and (2), we get
 +
<cmath>4(n^2+1)\le p( a^2+b^2 - 2(a+b-1) )< p( p-2\sqrt{p} )< u^2(u-1)^2,</cmath>
 +
where <math>u=\sqrt{p}.</math>
 +
 
 +
Finally,
 +
<cmath>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}.</cmath>
 +
The proof is complete.
 +
 
 +
'''Solution 2'''
 +
 
 +
We begin with a lemma.
 +
 
 +
Lemma: For every prime <math>p \equiv 1 \mod{4}</math>, there exists a positive integer <math>n \le \dfrac{p - \sqrt{p-4}}{2}</math> such that <math>p\mid n^2 + 1</math>.
 +
 
 +
Proof:
 +
We know that there must be a solution <math>x</math> to the equation
 +
<cmath>x^2+1 \equiv 0 \mod{p}</cmath>
 +
with <math>1 \le x \le p-1</math>.  However, if <math>x</math> is a solution then so is <math>p-x</math>, so there must be a solution <math>x \le p-1</math>.  Let <math>n</math> denote this solution and suppose that <math>n = \frac{p-k}{2}</math>.  Then, we have
 +
<cmath>\left(\dfrac{p-k}{2}\right)^2 \equiv -1 \mod{p}</cmath>
 +
<cmath>k^2 \equiv -4 \mod{p}.</cmath>
 +
Since <math>k</math> is a positive integer, it follows that <math>k^2 \ge p-4</math>, so we have
 +
<cmath>n \le \dfrac{p - \sqrt{p-4}}{2},</cmath>
 +
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
 +
<cmath>p > 2N + \sqrt{2N}</cmath>
 +
<cmath>p - 2N > \sqrt{2N}.</cmath>
 +
But, we know that <math>p-2N \ge \sqrt{p-4}</math>, so it suffices to show that
 +
<cmath>p-4 > 2N</cmath>
 +
<cmath>p - 2N > 4.</cmath>
 +
Once again, it suffices to show that
 +
<cmath>\sqrt{p-4} > 4,</cmath>
 +
which follows from <math>p>20</math>.
 +
 
 +
Thus, <math>N</math> satisfies the required condition and it follows that there exist infinitely many values of <math>n</math> that satisfy the given condition, as desired.
 +
 
 +
==See Also==
 +
 
 +
{{IMO box|year=2008|num-b=2|num-a=4}}

Latest revision as of 00:09, 19 November 2023

Problem

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

Solutions

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,\] 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.

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\mid 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{p}\] \[k^2 \equiv -4 \mod{p}.\] Since $k$ is a positive integer, it follows that $k^2 \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.

See Also

2008 IMO (Problems) • Resources
Preceded by
Problem 2 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 4
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2008_IMO_Problems/Problem_3&oldid=204530"