<s>[INST] Is it possible to find such integers $y,b$ that $\left|-\frac{x_{0}}{n}-\frac{y}{b}\right|<\frac{1}{b\sqrt{n}}$ 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. 
 [/INST] 
Lemma. If $m\mid(x^2+1)$, then there exists $y,d$ such that
  
  
*
  
*$m=y^2+d^2$
  
*$xy\equiv d\pmod m$.
  

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}$$
</s>