IMO-2008-3

Discussion on International Mathematical Olympiad (IMO)
User avatar
Tahmid Hasan
Posts:665
Joined:Thu Dec 09, 2010 5:34 pm
Location:Khulna,Bangladesh.
IMO-2008-3

Unread post by Tahmid Hasan » Sun Apr 01, 2012 9:59 am

Prove that there exist infinitely 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. :mrgreen: ]
বড় ভালবাসি তোমায়,মা

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: IMO-2008-3

Unread post by Masum » Tue Apr 03, 2012 12:32 pm

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

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

Re: IMO-2008-3

Unread post by zadid xcalibured » Tue Apr 03, 2012 2:50 pm

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

User avatar
Masum
Posts:592
Joined:Tue Dec 07, 2010 1:12 pm
Location:Dhaka,Bangladesh

Re: IMO-2008-3

Unread post by Masum » Thu Apr 05, 2012 12:12 pm

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

Post Reply