http://www.mathlinks.ro/viewtopic.php?search_id=550514793&t=126781 This says much more and the solution presented there gives infinitely many such numbers, not just one, as stated in that link. However, I guess the official solution runs along the ideas used in a problem given in a recent USAMO (proposed by Titu Andreescu and me). In any case, I doubt this is a good problem for IMO.

Sorry for double posting, but it's just as I thought: take $ p-1$ multiple of $ 4$ very large. Then we know there is $ n$ such that $ p|n^2+1$ and of course we may assume that $ n<p$ and even $ 2n\leq p$, simply because $ p$ also divides $ (p-n)^2+1$. Now, write $ p-2n=k>0$ and observe that $ p$ divides $ 4n^2+4=(p-k)^2+4$, thus $ p$ divides $ k^2+4$ and so $ k$ is at least $ \sqrt{p-4}$. This ismmediately implies $ p>2n+\sqrt{2n}$ if $ n$ is large enough, that is $ p$ is large enough.

Fix a prime $ p$ of the form $ 20m+1$. There are two solutions to the congruence $ n^2 \equiv -1 \pmod{p}$, one of them is less then $ \frac{p-1}{2}$ and one is greater. Let $ \frac{p-1}{2}-k$ be the smaller one ($ k>0$). Now we want find a lower bound for the $ k$, let's see what do we need. Take for simplicity $ \frac{p-1}{2} = a$. We want to have: $ 2(a-k) + \sqrt{2(a-k)} \leq p-1$ or $ a-k + \sqrt{\frac{a-k}{2}} \leq a$ which is equivalent to $ a \leq 2k^2 + k$ and finally $ p \leq 4k^2 + 2k + 1$. Ok, now we see that $ (\frac{p-1}{2} - k)^2 \equiv -1 \pmod{p}$ is equivalent to $ (2k+1)^2 \equiv -4 \pmod{p}$. But $ p-4 \equiv 3 \pmod{5}$, so it's not a square. Of course $ (2k+1)^2 \not = 2p-4$ since the parity is different. Therefore $ (2k+1)^2 \geq 3p-4$, i.e. $ 4k^2+4k + 5 \geq 3p$ and it's clear that the desired inequality is satisfied.

harazi wrote: Sorry for double posting, but it's just as I thought: take $ p - 1$ multiple of $ 4$ very large. Then we know there is $ n$ such that $ p|n^2 + 1$ and of course we may assume that $ n < p$ and even $ 2n\leq p$, simply because $ p$ also divides $ (p - n)^2 + 1$. Now, write $ p - 2n = k > 0$ and observe that $ p$ divides $ 4n^2 + 4 = (p - k)^2 + 4$, thus $ p$ divides $ k^2 + 4$ and so $ k$ is at least $ \sqrt {p - 4}$. This ismmediately implies $ p > 2n + \sqrt {2n}$ if $ n$ is large enough, that is $ p$ is large enough. Very nice !

Seems like people who have seen the problem Prove that there exists infinite $ n$ such that $ n^4+1$ has a prime divisor larger than $ 2n$ would have some advantages

Just a side remark. Even those who did not know that any $ p=4k+1$ divides some $ x^2+1$ could solve the problem like harazi did because all one needs is to have infinitely many primes that divide $ x^2+1$ for some $ x$ and the classical Euclid's proof of the infinitude of primes can be trivially ajusted to give this statement. The opening sentence in TomciO's solution, on the other hand, would tempt me to reduce a few points immediately if I were one of the graders because it is quite doubtful that the contestant could prove it if asked. Anyway, the first day problems were sort of disappointing . Let's see what the second day will bring

Every prime that is congruent to $ 1$ mod $ 4$ appears exactly once as the divisor here, except for $ 5$ and $ 13$. Harazi's "large enough" threshold is $ p = 29$, and $ p = 17$ works easily because $ 17 - 4$ is not a perfect square. If $ 2n + \sqrt {2n}$ were changed to $ 2n + \sqrt {2n} + 1$, we would need to exclude all primes of the form $ m^2 + 4$ as well. This still leaves infinitely many, but proving that is hard compared to the Euclid-style argument that there are infinitely many primes $ \equiv 1\mod 4$. [Edit- fixed silly mistake]

Shouldn't 3rd problems be a little difficult in the sense that the solution should be a little long or at least involve some clever argument or trick? I mean look at Harazi's post (#3)... And then a gain P1 asking if you know Power Of a Point, and P2 being cross multiplication+multiplication+addition+completing the square... Very disappointed. Again the question is: Poor choice of leaders or bad ISL?

Note that for any prime $ p \equiv 1 \pmod{4}$, we can always choose some $ \alpha \in \{ 0, \ldots, \frac{p-3}{2} \}$ such that $ \left(\frac{p-1}{2} - \alpha \right)^2 \equiv -1 \pmod{p}$. Denote $ m = \frac{p-1}{2} - \alpha$. This problem then becomes equivalent to choosing a suitable $ p$, with corresponding $ \alpha$, such that $ p > 2m + \sqrt{2m}$. We check that \[ p > p-1 - 2\alpha + \sqrt{p-1-2\alpha} \Leftrightarrow 2\alpha + 1 > \sqrt{p-1-2\alpha} \Leftrightarrow 4\alpha^2 + 6\alpha + 2-p >0.\] Solving this quadratic inequality, since we assumed $ \alpha \geq 0$, this is equivalent to \[ \alpha > \dfrac{-6+\sqrt{36+16(p-2)}}{8} = \dfrac{-3+\sqrt{4p+1}}{4}.\] Hence, if $ \alpha > \dfrac{-3+\sqrt{4p+1}}{4}$, then we are done. Suppose not, then we have $ 0 \leq \alpha \leq \dfrac{-3+\sqrt{4p+1}}{4}$. Note that $ 4m^2 = (p-1-2\alpha)^2 \equiv (2\alpha+1)^2 \pmod{p}$. By the bounds on $ \alpha$, we get $ 0 \leq (2\alpha+1)^2 \leq \left( \dfrac{\sqrt{4p+1} - 1}{2} \right)^2$. Now, by assumption, $ 4m^2 \equiv -4 \pmod{p}$, so if $ \left( \dfrac{\sqrt{4p+1} - 1}{2} \right)^2 < p-4$, we get a contradiction. Solving this inequality, this is equilavent to $ p>20$. Therefore, if $ p$ is sufficiently large (i.e. $ p>20$) and $ p\equiv 1 \pmod{p}$, we can always find some $ m$ such that $ p|(m^2+1)$ and $ p > 2m + \sqrt{2m}$.

harazi wrote: Sorry for double posting, but it's just as I thought: take $ p - 1$ multiple of $ 4$ very large. Then we know there is $ n$ such that $ p|n^2 + 1$ and of course we may assume that $ n < p$ and even $ 2n\leq p$, simply because $ p$ also divides $ (p - n)^2 + 1$. Now, write $ p - 2n = k > 0$ and observe that $ p$ divides $ 4n^2 + 4 = (p - k)^2 + 4$, thus $ p$ divides $ k^2 + 4$ and so $ k$ is at least $ \sqrt {p - 4}$. This ismmediately implies $ p > 2n + \sqrt {2n}$ if $ n$ is large enough, that is $ p$ is large enough. Similarly I got to the step that $ p$ divides $ k^2 + 4$, obviously if $ \frac{k^2+4}{p}>1$ we will done. So p=$ k^2$+4. So this will lead to that any prime congruent to 1 mod 4 need also be congruent to 5 mod 8.(otherwise p-4 congruent to 5 mod 8 which cannot be $ k^2$) This is clearly a contradiction by Dirichlet's Theorem! P.S Is there an elementary way to show that there are infinitely many prime of form 8K+1?

yes. one way for example is considering divisors of $ 2^{2^m} + 1$

Author of this problem is Kęstutis Česnavičius, Lithuania., from Jacobs University Bremen which is the host of the 50th International Mathematical Olympiad 2009 in Bremen Germany. It will also be the 20th anniversary after the last IMO in Braunschweig, Germany in 1989. Formerly the German Democratic Republic (GDR) was supposed to host the IMO 1992 but due to the unification with the Federal Republic of Germany (FRG) the event was cancelled and organized by Moscow, Russia, as a substitute host in 1992.

If solution of the problem consists only of two simple steps – it isn’t third. My solution. Consider the set of numbers $ S=${$ p \in \mathbb{P} | p \equiv 1 \mod 4, p \not = 5,13$}. For every $ p \in S$ let us define set of positive integers $ N_p$ such that $ n \in N_p \leftrightarrow p|n^2+1$ and $ n_p$ - the minimal of them. It’s easily seen that $ n_p<p$ and also $ n_p<\frac{p}{2}$ else we can take $ p-n_p$ instead of $ n_p$. Let $ k_p$ be $ p-2n_p$. Then $ k_p^2+4=(p-2n_p)^2+4 \equiv 4(n_p^2+1) \equiv 0 \mod p$, hence $ k^2+4>=p$. Let us notice that $ k_p>4$. Really, if this isn’t true then there are only two variants: $ k_p=1$ and $ k_p=3$ since $ k_p$ is odd. If $ k_p=1$ then $ p|1^2+4$ and $ p=5$ - contr; if $ k_p=3$ then $ p|3^2+4$ and $ p=13$ -contr. So we have $ k_p^2+k_p>k_p+4 \ge p$, therefore $ p-k_p+\sqrt{p-k_p}<p$ or $ 2n_p+\sqrt{2n_p}<p$. Since $ |S|=\infty$ then there are infinitely many different integers $ n_p$ such that $ p \in S$, so we are done. Evidently it’s possible to estimate this value better. For example if we take the set $ T=${$ p \in \mathbb{P} | p \equiv 1 \mod 4, p \equiv 1 \mod 5$} then for every $ p \in T$ $ p-4$ isn’t square of integer and hence $ k_p^2+4 \ge 5p$.

harazi wrote: \we may assume that $ n < p$ and even $ 2n\leq p$, simply because $ p$ also divides $ (p - n)^2 + 1$. . vhy??? :

Why what? $ 0<n<p$ because you can subtract any multiple of $ p$ from $ n$ and still have $ p|n^2+1$ (clearly, if $ p|n^2+1$, then $ p\not |n$). If $ n>p/2$, then $ p-n<p/2$ and $ (p-n)^2+1=p(p-2n)+n^2+1$ is also divisible by $ p$.

It suffices to show that there exist an infinitely many positive interger $ n$ such that:$ n^2 + 1$ has a prime facter greater than $ 3n$. It comes from the $ 2n$-problem.Indeed,just choosing among $ 3$ positive integers:$ p - 2n,n,n$ to get the minimal one,namely $ m$.Then $ p > 3m$ and $ p|m^2 + 1$. Solving the $ 2n$-problem is just the same exactly!First,we have:such a $ p$ exists infinitely(as fedja said above).Express:$ n = kp + r,r < p$. And now choosing between $ r$ and $ p - r$ the least ,namely $ m$.Therefore $ p > 2m$ and $ p|m^2 + 1$. The $ Cn$-problem follows immediatelly. QED. EDIT:harazi,I'm really curious to now the USAMO problem???

$ p-2n$ does not work! The $ Cn$ problem is much subtler than you think

http://www.mathlinks.ro/viewtopic.php?p=490625#490625 It is the problem from the USAMO that harazi has mentioned.

your link directs to problem 6??

delegat wrote: Prove that there are infinitely many positive integers $ n$ such that $ n^{2} + 1$ has a prime divisor greater than $ 2n + \sqrt {2n}$. Author: Kestutis Cesnavicius, Lithuania Wait I solved an IMO #3 thats $>$ year $2000$ in less than 15 minutes? Im so Proud ___________________________________________________________________________________________________________________________________________________ First we set out to simplify the problem statement. We see that $ 2n + \sqrt {2n} < n^{2} + 1$ for all $n > 2$. Thus, if there exists infinite primes of the form $k = n^{2} + 1$, then the problem is solved, since the maximum prime divisor of $k$, which is itself, is necessarily higher than the bound given. We rewrite the problem as follows: Prove that there exist infinite prime numbers of form $n^{2} + 1$ which $n \in Z^{+}$ Claim: There exist infinite prime numbers of form $n^{2} + 1$ which $n \in Z^{+}$ If $n^{2} +1$ is prime then $n^2$, and $n$, are even. Thus we can consider the expression mod $4$, to assert that $n^{2} + 1$ is of form $4r + 1$ for positive integers $r$. Simply proving there are infinite primes of form $4r + 1$ will suffice. This is well known. The proof for that is as follows Proof wrote: We proceed by way of contradiction. Suppose there are only finite primes of form, labeled $p_{1}, p_{2}, .... p_{n}$. $N=(p_{1}...p_{n})^{2}+1$; $N>p_{i}$ for $1 \le i \le n$. Hence $N$ can not be prime. Any number of the form $a^{2}+1$, has, except possibly the factor $2$, only prime factors of the form $4m+1$ .Since dividing $N$ by each prime factor of the form $4j+1$ leaves a remainder $1$, $N$ can not be composite CONTRADICTION. Thus the statement is proven Accordingly, we are done ___________________________________________________________________________________________________________________________________________________ EDIT: Wait this is 30M No way... Okay!

The above proof fails (the proof of the claim is incorrect). It is one of Landau's unsolved problems. See this.

bryanguo wrote: The above proof fails (the proof of the claim is incorrect). It is one of Landau's unsolved problems. See this. Wait how come? I 99% expected that since I'm not very good at math, but why doesn't this work: Claim: There exist infinite prime numbers of form $n^{2} + 1$ which $n \in Z^{+}$ If $n^{2} +1$ is prime then $n^2$, and $n$, are even. Thus we can consider the expression mod $4$, to assert that $n^{2} + 1$ is of form $4r + 1$ for positive integers $r$. Simply proving there are infinite primes of form $4r + 1$ will suffice. This is well known. So done

Well consider the following invalid argument. Variant wrote: If $n^{2} +1$ is prime then $n^2 + 1$ must be odd for $n \ge 2$. Thus we can consider the expression mod $2$, to assert that $n^{2} + 1$ is of form $2r + 1$ for positive integers $r$. Simply proving there are infinite primes of form $2r + 1$ will suffice. This is well known. So done

Oh I see... But still, why doesn't it work? Like why isn't mod 4 good enough? It usually works with similar diophantines so im confused Are there other circumstances where this is true as well?

Let's take YaoAOPS's example and push it even further. Variant wrote: If $n^{2} -1$ is prime then $n^2 - 1$ must be odd for $n \ge 2$. Thus we can consider the expression mod $2$, to assert that $n^{2} - 1$ is of form $2r - 1$ for positive integers $r$. Simply proving there are infinite primes of form $2r - 1$ will suffice. This is well known. So done But here the claim is false, because $n^2 - 1$ factors! Do you see what's going on here? You've expanded the search space too much. An analogous "real life" version of your argument would be as follows: Variant of a variant wrote: Let's prove that over 1 billion people live in Mongolia. To do this, note that if someone lives in Mongolia, they must live in Asia. Thus, it suffices to prove that over 1 billion people live in Asia, which is true.

Oh!!!!!!!! I see! Thank you so much Basically for my proof to work I have to prove all primes of form 4n+1 are also of form x^2 + 1 which is false tysm

For each sufficiently large prime $p \equiv 1 \pmod{4}$, let $n$ be the minimal root of $n^2 + 1 \equiv 0 \pmod{p}$. I claim that this $n$ has $p > 2n + \sqrt{2n}$, which will finish. Indeed, clearly $n \le \frac{p-1}{2} = a$, so let $n = a - k$. Now \begin{align*} n^2 + 1 \equiv 0 \pmod{p} &\implies (a - k)^2 + 1 \equiv 0 \pmod{p} \\ &\implies (2k+1)^2 + 4 \equiv 0 \pmod{p} \\ &\implies p \le 4k^2 + 4k + 5. \end{align*}Putting this back in terms of $n$ gives \begin{align*} p \le 4k^2 + 4k + 5 &\implies p \le (p - 2n)^2 + 4 \\ &\implies p^2 - (4n+1)p + (4n^2+4) \ge 0 \\ &\implies p \ge \frac{4n + 1 + \sqrt{8n - 15}}{2} \end{align*}which implies the bound for sufficiently large $n$.

Let $p$ be some arbitrarily large prime that is $\equiv 1\pmod{4}$. Then let $n$ be the smallest $n$ that satisfies $n^2 \equiv -1\pmod{p}$. Notice that $n \leq \frac{p-1}{2}$ since there are at most two distinct solutions to $n^2 \equiv -1\pmod{p}$ that add up to $p-1 \pmod{p}$ (you can prove this with primitive roots). So then let $k = \frac{p-1}{2} - n$. Expanding $(\frac{p-1}{2} - k)^2 + 1 \pmod{p}$ gives $4k^2 + 4k + 5 \equiv 0\pmod{p}$. Then plugging in $k = \frac{p-1}{2} - n$ again gives $(p - 2n)^2 + 4 \geq p$. Expanding gives $p^2 - (4n + 1)p + 4n^2 + 4 \geq 0 \implies p \geq \frac{4n + 1 + \sqrt{8n - 15}}{2}$ which is enough as $\sqrt{8n - 15} \geq \sqrt{2n}$ for sufficiently large $n$.

Let $p$ be a prime equivalent to $1\pmod 4$. Then $n^2\equiv -1 \pmod p$ has solutions. Note that if there are solutions for $n$ that are less than $p$, then they come in pairs adding up to $p-1$. Let $a=\tfrac{p-1}{2}$ then let the two smallest solutions be $a\pm k$. Note that $p\mid (a-k)^2+1$ so $p\mid (2a-2k)^2+4$, which implies $p\mid (2k+1)^2+4=(p-2n)^2+4$. Solving the quadratic equation gives \[p=\frac{4n+1+\sqrt{8n-15}}{2}\]Now, $4n+1+\sqrt{8n-15}>4n+\sqrt{8n}$ if and only if $\sqrt{8n}-\sqrt{8n-15}<1$ which is true for sufficiently large $n$. The reason why sufficiently large $n$ ever appear in our method is because for any fixed $n$, only finitely many $p$ divides $n^2+1$.

Consider primes $p>20$ which are $1\pmod4$. (By Dirichlet's, there are infinitely many.) Suppose the squareroots of $-1$ mod $p$ are $\frac{p-a}2$ and $\frac{p+a}2$, with $0<a<p$. Then $a^2\equiv(a-p)^2\equiv-4\pmod p$, so $p\leq a^2+4$. Since $p>20$, we have $a>4$, so $p\leq a^2+4<a^2+a$. Now $a>\sqrt{p-a}$, so $p>(p-a)+\sqrt{p-a}$, and we're done by setting $n=\frac{p-a}2$. Since $p$ can be arbitrarily large and $p\leq n^2+1$, $n$ can also be arbitrarily large, so there are infinitely many such $n$.

We instead show that for infinitely many primes $p$ there exists $n$ with $p\mid n^2+1$ and $p>2n+\sqrt{2n}.$ This implies the problem, since no $n$ works for multiple $p$ as $n^2+1$ can have at most one divisor $>2n+\sqrt{2n}.$ In fact we show a much stronger statement: this is true for all $p\equiv 1\pmod 4$ and $p>20.$ First suppose $p\equiv 1\pmod 4.$ Then choose $n$ that satisfies $n^2\equiv -1\pmod p$ and $n<\frac p2.$ Next, we can see that $p>2n+\sqrt{2n}$ is equivalent to $n<\frac{2p+1-\sqrt{4p+1}}4$ by manipulating. Thus we just want to prove this bound. Now set $n=\frac{p-c}2.$ From $n<\frac p2$ it follows $c$ is a positive odd integer. Now \[n^2=\left(\frac{p-c}2\right)^2\equiv -1\pmod p,\]so this becomes $c^2\equiv -4\pmod p.$ In particular, $c^2\ge p-4$ and $c\ge\sqrt{p-4}.$ Now we have $n\le\frac{p-\sqrt{p-4}}2.$ But \begin{align*}&\frac{p-\sqrt{p-4}}2<\frac{2p+1-\sqrt{4p+1}}4\\\iff&2p-2\sqrt{p-4}<2p+1-\sqrt{4p+1}\\\iff&2\sqrt{p-4}>\sqrt{4p+1}-1\\\iff&4p-16>4p+2-2\sqrt{4p+1}\\\iff&\sqrt{4p+1}>9\\\iff&p>20,\end{align*}so our claim is true.

Let $P = 4K + 1 \geq 13$ be a prime number. Then there exist two solutions to the equation $n^2 + 1 \equiv 0 \pmod{P}$. Let $0 < X_1 < X_2 < P$ be these solutions. Since $X_1 = P - X_2$, we have $X_2 > \frac{P}{2}$. That is, $X_2 \geq 2K + 1$. But if $X_2 = 2K + 1$, we would have: \[ 0 \equiv X_2^2 + 1 \equiv (2K + 1)^2 + 1 \equiv 2K(2K + 1) + 3K + 2 \equiv 3K + 2 \pmod{P}. \]Which is not possible, since $P > 13$ we have $K \geq 3$, hence $0 < 3K + 1 \leq 4K + 1 = P$. Similarly, if $P = 2K + 2$ we would have: \[ 0 \equiv X_2^2 + 1 \equiv (2K + 2)^2 + 1 \equiv 4K(K+1)(K+1) + 3K + 4 \equiv 3K + 4 \pmod{P}. \]Which is not possible, since $K > 3$ then $0 < 3K + 4 < 4K + 1 = P$. From the above, we have $X_2 \geq 2K + 3$. It follows that $$2X_1 = 2(P - X_2) \leq 2(4K + 1 - (2K + 3)) = 2(2K - 2) = 4K - 4 < P - 4$$Finally, we observe that: \[ (P - 2X_1)^2 + 4 \equiv P^2 - 4P X_1 + 4X_1^2 + 4 \equiv 4X_1^2 + 4 \equiv 0 \pmod{P}. \]From which $P \leq (P - 2X_1)^2 + 4$, that is, $\sqrt{P - 4} \leq P - 2X_1$. We conclude that: \[ P \geq 2X_1 + \sqrt{P - 4} > 2X_1 + \sqrt{2X_1}. \]So for each $P > 13$ there exists an integer $n$ such that $P \mid n^2 + 1$ and $P > 2n + \sqrt{2n}$, thus we are done.

The main idea is that instead of thinking about it in terms of choosing $n$, think about it in terms of choosing a prime $p$ and considering the smallest $n$ for which $n^2\equiv -1\pmod{p}$. Clearly $p\equiv 1\pmod{4}$. The idea is that the bound $$p>2n+\sqrt{2n}$$is not very strong, in fact, it says that $n$ only has to be slightly less than $\frac{p}{2}$. Since the two solutions are symmetric, the only concern is that both solutions may be very close to $\frac{p}{2}$. The following claim dispels this. Claim: If $p\equiv 1\pmod{4}$ is sufficently large and $a$ is a positive integer such that $(\frac{p-a}{2})^2\equiv -1\pmod{p},$ then $a\geq\sqrt{p-4}$. We have $$p^2-2ap+a^2\equiv -4\pmod{p}$$$$a^2\equiv -4\pmod{p}.$$In particular, $a^2\geq p-4$. Thus, since there exists a solution at most $\frac{p-1}{2}$ by symmetry, there exist $n\leq \frac{p-\sqrt{p-4}}{2}$ such that $n^2\equiv -1\pmod{p}$. Thus, assuming $p\geq 29$, we have $$2n+\sqrt{2n}\leq p-\sqrt{p-4}+\sqrt{p-\sqrt{p-4}}$$$$< p-\sqrt{p-4}+\sqrt{p-4}=p,$$as desired.

Solved with erkosfobiladol. Pick a prime $p\equiv 17(mod \ 28)$. We will prove that there exists some $n$ such that $p|n^2+1$ and $n<\frac{p-\sqrt p}{2}$ which is stronger than given bound. There are two $n$ where $p|n^2+1$ and $0<n<p$, let $m$ be the smaller one. Suppose that $m=\frac{p-a}{2}$. We have $p|(\frac{p-a}{2})^2+1$ or $p|a^2+4$. If $a<\sqrt p$, then $a^2+4\leq p+4$ which implies $a^2+4=p$. However $a^2+4$ cannot be $3(mod \ 7)$. Thus, $a>\sqrt p$ and this gives $n<\frac{p-\sqrt p}{2}$ as desired.$\blacksquare$