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. 
 A: 
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}$$
A: 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. 
