Let $m\in\mathbb N$ be such that $m>1$ and $n$ be another natural number such that $n\mid(m^2+1).$ If $n>m,$ then how to prove that $n>m+\sqrt m.$ (Basically I have no clue how to approach this problem but still tried to write few lines based on my little knowledge..)
We have: $n>m>1.$ Let $n=m+x$ with $x\le\sqrt m.$ Then $n$ divides both $(m^2+1)$ and $(m+x)(m-x)=m^2-x^2.$ This implies $n\mid\{(m^2+1)-(m^2-x^2)\}=(x^2+1),$ where $x^2+1\le m+1.$
I was actually looking for a contradiction. But I don't know how to proceed further with it. Is this even a correct way to approach the problem? Please help! Thanks in advance.
 A: Yes, just go a further step with your proof: Since $n \mid (x^2+1)$, it must be that $x^2 + 1 \geq n \gt m$, therefore $x^2 \geq m$, so $x \geq \sqrt{m}$.
But if $x = \sqrt{m}$, then from the above we know $m+1 \geq n \gt m$, therefore $n = m+1$ and $n = m+\sqrt{m}$, so $\sqrt{m}=1$, $m=1$, contradicting the assumption. Therefore it must be that $x \gt \sqrt{m}$ and $n = m+x \gt m+\sqrt{m}$.
A: You have made some good first steps. You have that $$n | (x^2 + 1)$$
with $n = m+x$ and $0 < x \le \sqrt{m}$
This means that there must be integer solutions to $$tn = x^2 + 1 \to t(m+x) = x^2 + 1$$
Rearranging for $m$, I get $$m = \frac{x^2+1}{t}-x$$
For $t = 1$, it is easy to see that there are no solutions.
For integer $t > 1$, the curve $m = \frac{x^2+1}{t}-x$ will intersect the curve $m = x^2$ at only one positive $x$: $$x_1=\frac{-t+\sqrt{t^{2}+4t-4}}{2\left(t-1\right)}$$
This means that $0 < x \le x_1$ would have to be satisfied. The problem is that $x_1 < 1$ for $t \ge 2$, so there would be no integer solutions for $x$. Therefore, there is no such $n, x$ such that $n | (x^2+1)$ with $n = m+x$ and $0 < x \le \sqrt{m}$.
