Given integers $x_{0},n$ with $x_{0}^{2}\equiv -1$ (mod $n$) then there are integers $y,b$ with $(y,b)=1,0<b\le\sqrt{n}$ and
$$\left|-\frac{x_{0}}{n}-\frac{y}{b}\right|<\frac{1}{b\sqrt{n}}$$
I tried to solve $|bx_{0}+ny|<\sqrt{n}$ for some integers $y,b$, but it seems do nothing.
Is there any hint that I can follow ?
Any comment and advise I will be appreciated.
On
The proof that I provide here is related to the other answer. I will discuss the connection at the end of this answer.
Take $x_0\in\mathbb Z$ and $n>1$ and $(x_0,n)=1$. Consider the following set: $$ A=\{bx_0-a: 0\leq a,b\leq [\sqrt n], (a,b)\neq 0\} $$ The goal is to use the elements of $A$ to construct $bx_0-a=-ny$ and we will see how.
There are $([\sqrt n]+1)([\sqrt n]+1)-1$ different pairs of $(a,b)$ and therefore there are at most $n$ different numbers module $n$ in $A$. Consider the following cases:
If $n|bx_0-a$ for some $(a,b)$, then $a$ and $b$ cannot be zero. Because otherwise $n|a$ or $n|b$ (note that $(x_0,n)=1$, which is not possible since $a,b\leq[\sqrt n]$. Therefore we have: $$ \exists y\in\mathbb Z: bx_0+ny=a, $$ with $0<a,b\leq \sqrt n$.
If the previous case does not occur, then there are two different pairs $(a_1,b_1)$ and $(a_2,b_2)$ for which: $$ b_1x_0-a_1\equiv b_2x_0-a_2\mod n. $$ Assuming that $b_2\geq b_1$, we have $n|(b_2-b_1)x_0+(a_2-a_1)$. Note that since $|a_2-a_1|\leq [\sqrt n]$, $b_1$ and $b_2$ should be different and therefore $0<b_2-b_1\leq [\sqrt n]$.
Therefore one can find $0<b\leq \sqrt n$ and $|a|\leq \sqrt n$ such that $$ \exists y\in\mathbb Z: bx_0+ny=a. $$ This means that: $$ \left|-\frac{x_{0}}{n}-\frac{y}{b}\right|=\left|\frac{a}{nb}\right|\leq\frac{1}{b\sqrt{n}}. $$
The proof above is indeed a proof of Thue's lemma, or at least one of its variations. Note that no need to have $n|x_0^2+1$ but only $(n,x_0)=1$. But Thue's lemma is used to prove the existence of solutions for the sum of square equation: $$ x^2+y^2=p, $$ when $p\equiv 1\mod 4$. The technique used in the other answer is also part of a proof of this problem.
Proof. Let $x^2+1=mn$. If $m$ is prime, then $m=2$ or $m\equiv 1\pmod 4$, hence $m$ is the sum of two squares $m=y^2+d^2$. Since $x^2\equiv -1\pmod{m}$, we have $$(xy+d)(xy-d)=x^2y^2-d^2\equiv 0\pmod{m}$$ hence (wlog) $m\mid(xy-d)$.
Let $m_1m_2\mid(x^2+1)$ and assume $m_j=y_j^2+d_j^2$ and $xy_j\equiv d_j\pmod{m_j}$ for $j\in\{1,2\}$. Then $$m_1m_2=(y_1^2+d_1^2)(y_2^2+d_2^2)=(y_1y_2-d_1d_2)^2+(y_1d_2+d_1y_2)^2$$ and $$0\equiv -(xy_1-d_1)(xy_2-d_2)\equiv (y_1d_2+y_2d_1)x+(y_1y_2-d_1d_2)\pmod{m_1m_2}$$ thus proving the lemma.
Proof of the main question. The assertion is obvious for $n=1$, hence we assume $n>1$. Let $x^2+1=mn$ and let $y,d$ as in the lemma. Let $xy-d=bm$ and $a=bx-ny$. Then $$m(a^2+b^2-n)=n((mb-xy)^2-d^2)=0$$ proves $a^2+b^2=n$, hence $|a|,|b|\leq\sqrt n$.
If $b=0$, then $d=xy$ hence $m=y^2+d^2=y^2+x^2y^2=y^2(1+x^2)=y^2nm$ hence $y^2n=1$ from which $n=1$.
If $a=0$, then $bx=ny$, hence $x^2y-xd=x(xy-d)=xbm=nym=y(x^2+1)$ from which $y=-xd$ hence $m=y^2+d^2=x^2d^2+d^2=(x^2+1)d^2=mnd^2$ from which $nd^2=1$ that's $n=1$.
This proves $0<|a|,|b|<\sqrt n$ from which $$\left|\frac xn-\frac yb\right|=\frac{|a|}{n|b|}<\frac 1{|b|\sqrt n}$$