Prove that there exist inﬁnitely many positive integers $n$ such that $n^2+1$ has a prime divisor which is greater than $2n+\sqrt{2n}$.

[well I'm still trying to solve this problem and to be frank i haven't made any good progress ,so it'd be helpful if anyone could share a hint. ]

## IMO-2008-3

- Tahmid Hasan
**Posts:**665**Joined:**Thu Dec 09, 2010 5:34 pm**Location:**Khulna,Bangladesh.

### IMO-2008-3

বড় ভালবাসি তোমায়,মা

### Re: IMO-2008-3

Hmm. A tough problem. Let me try.

Some ideas. It would be easier if the limit was $p>2n$ instead of $2n+\sqrt{2n}$.

At first, in the same way as Euclid did, we can prove that $n^2+1$ has an infinite prime divisors of the form $4k+1$, just choose $(p_1p_2\cdots p_k)^2+1$ and we get it has a prime factor greater than and co-prime to $p_i$.

We can take $r$ such that $r$ is the minimum positive remainder of $n$ upon division by $p$. then $p>r$. We may say, \[p|r^2+1, (p-r)^2+1\]

Now choose a convenient $m$ such that $m=min(r,p-r)$. Then we get $m<\frac{p}{2}$ giving $p>2m$ for infinite $m$.

But I need to think more for this tight limit. And I haven't used paper, pen right now. So let me know if I am wrong somewhere.

A bit more idea is if $a=\sqrt{2n}$(a positive real number) then, we can rearrange the inequality like, \[a^2+a<p\Rightarrow4a^2+4a+1<4p+1\]

Or, \[2\sqrt{2n}+1<\sqrt{4p+1}\]

Some ideas. It would be easier if the limit was $p>2n$ instead of $2n+\sqrt{2n}$.

At first, in the same way as Euclid did, we can prove that $n^2+1$ has an infinite prime divisors of the form $4k+1$, just choose $(p_1p_2\cdots p_k)^2+1$ and we get it has a prime factor greater than and co-prime to $p_i$.

We can take $r$ such that $r$ is the minimum positive remainder of $n$ upon division by $p$. then $p>r$. We may say, \[p|r^2+1, (p-r)^2+1\]

Now choose a convenient $m$ such that $m=min(r,p-r)$. Then we get $m<\frac{p}{2}$ giving $p>2m$ for infinite $m$.

But I need to think more for this tight limit. And I haven't used paper, pen right now. So let me know if I am wrong somewhere.

A bit more idea is if $a=\sqrt{2n}$(a positive real number) then, we can rearrange the inequality like, \[a^2+a<p\Rightarrow4a^2+4a+1<4p+1\]

Or, \[2\sqrt{2n}+1<\sqrt{4p+1}\]

One one thing is neutral in the universe, that is $0$.

- zadid xcalibured
**Posts:**217**Joined:**Thu Oct 27, 2011 11:04 am**Location:**mymensingh

### Re: IMO-2008-3

the solution of this problem can be used to solve advanced 29.

29.show that there exist infinitely many positive $n$ such that the largest prime divisor of $n^4+1$ is greater than $2n$.

29.show that there exist infinitely many positive $n$ such that the largest prime divisor of $n^4+1$ is greater than $2n$.

### Re: IMO-2008-3

Thue's lemma ব্যাবহার করা যাইতে পারে। আর যারা Thue's lemma জানেনা তাদের জন্য ও সহজে আরেকভাবে দেখানো যায়।

আইএমও এর একটা প্রব্লেম এ ছিলঃ প্রমাণ কর যে $4n^2+1$ এর প্রত্যেকটা প্রাইম $4k+1$ আকারের। এইটা একটা হিন্ট হইতে পারে।

However, by the time I think it is well known that, if $p\equiv1\pmod4$, then there are integers $x,y$ such that \[p=x^2+y^2\]

If $p$ odd, then one of $x,y$ is even, say $y$. Then \[p=x^2+4z^2\]

Now let $a$ be the integer such that \[az\equiv1\pmod p\]

We get, $p|(ax)^2+4$ which gives $-4$ is a quadratic residue of $p$. So assume that $k^2\equiv-4\pmod p\Rightarrow k^2+4\ge p$ yielding $k\ge\sqrt{p-4}$.

এইটাই sqrt পাওয়ার একমাত্র হিন্ট।

যাইহোক, সমাধানে আসি।

Again, there are exactly $\frac{p-1}{2}$ quadratic residues of $p$. So, for $p|n^2+1$, we may say $p|(p-n)^2+1$, and hence say $n=\frac{p-k}{2}$. This gives us, \[n\le\frac{p-\sqrt{p-4}}{2}\]

(Note the reversing of sign of inequality).

Now try the same approach like Euclid. We want to show that, \[p-2n>\sqrt{2n}\]

From the limit of $k$ above, it will be enough if we can show that, \[p-2n\ge\sqrt{p-4}>\sqrt{2n}\]

It is enough to find, $p-4>2n\iff p-2n>4$(since we can certainly show that $p>2n$ from the above post), which is almost obvious for sufficiently large $p$.

**Lemma:**If $p\equiv1\pmod4$, then $-4$ is a quadratic residue modulo $p$.আইএমও এর একটা প্রব্লেম এ ছিলঃ প্রমাণ কর যে $4n^2+1$ এর প্রত্যেকটা প্রাইম $4k+1$ আকারের। এইটা একটা হিন্ট হইতে পারে।

However, by the time I think it is well known that, if $p\equiv1\pmod4$, then there are integers $x,y$ such that \[p=x^2+y^2\]

If $p$ odd, then one of $x,y$ is even, say $y$. Then \[p=x^2+4z^2\]

Now let $a$ be the integer such that \[az\equiv1\pmod p\]

We get, $p|(ax)^2+4$ which gives $-4$ is a quadratic residue of $p$. So assume that $k^2\equiv-4\pmod p\Rightarrow k^2+4\ge p$ yielding $k\ge\sqrt{p-4}$.

এইটাই sqrt পাওয়ার একমাত্র হিন্ট।

যাইহোক, সমাধানে আসি।

Again, there are exactly $\frac{p-1}{2}$ quadratic residues of $p$. So, for $p|n^2+1$, we may say $p|(p-n)^2+1$, and hence say $n=\frac{p-k}{2}$. This gives us, \[n\le\frac{p-\sqrt{p-4}}{2}\]

(Note the reversing of sign of inequality).

Now try the same approach like Euclid. We want to show that, \[p-2n>\sqrt{2n}\]

From the limit of $k$ above, it will be enough if we can show that, \[p-2n\ge\sqrt{p-4}>\sqrt{2n}\]

It is enough to find, $p-4>2n\iff p-2n>4$(since we can certainly show that $p>2n$ from the above post), which is almost obvious for sufficiently large $p$.

One one thing is neutral in the universe, that is $0$.