IMO-2008-3

Discussion on International Mathematical Olympiad (IMO)
Tahmid Hasan
Posts: 665
Joined: Thu Dec 09, 2010 5:34 pm

IMO-2008-3

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. ]
বড় ভালবাসি তোমায়,মা

Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm

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}$
One one thing is neutral in the universe, that is $0$.

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$.

Masum
Posts: 592
Joined: Tue Dec 07, 2010 1:12 pm

Re: IMO-2008-3

Thue's lemma ব্যাবহার করা যাইতে পারে। আর যারা Thue's lemma জানেনা তাদের জন্য ও সহজে আরেকভাবে দেখানো যায়।
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$.