Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 3 / 1G / i

Put $\alpha =\sqrt{N}$. Every positive solution satisfiesAfter reducing $x/y=p/q$, we still have $|\alpha -p/q|<1/(2q^2)$. Here is the continued fraction convergent criterion with its proof. If $p/q$ is reduced and obeys this inequality, it is a strict best approximation of the second kind: for any different $r/s$ with $0<s\le q$, the assumption $|s\alpha -r|\le |q\alpha -p|$ would givea contradiction. Choose consecutive continued fraction convergents $p_j/q_j,p_{j+1}/q_{j+1}$ with $q_j\le q<q_{j+1}$. Their determinant is $\pm 1$, their errors $e_j=q_j\alpha -p_j$ alternate in sign, and every integer pair $(r,s)$ is uniquely $a(p_j,q_j)+b(p_{j+1},q_{j+1})$. For $0<s<q_{j+1}$, either $b=0$, or $a,b$ have opposite signs: positive $a,b$ would make $s\ge q_{j+1}$, negative $a,b$ make $s<0$, and $a=0$ is impossible. Opposite signs make $a{e}_j$ and $b{e}_{j+1}$ have the same sign, so $|s\alpha -r|\ge |e_j|$. If $b=0$, reduction gives the $j$th convergent itself. Thus a strict best approximation must be a convergent. The determinant and alternating-error facts follow immediately from the recurrence $p_j=a_j{p}_{j-1}+p_{j-2}$, $q_j=a_j{q}_{j-1}+q_{j-2}$ and the positive continued-fraction tail formula. Therefore the reduced ratio $x/y$ is a convergent of $\sqrt{N}$. Without assuming $\gcd (x,y)=1$, the unreduced pair may be a common multiple of the convergent's numerator and denominator; for example $(10,2)$ for $N=24,M=4$ reduces to $5/1$.