= Small norm residues from square-root continued fractions
{title2=$|p_k^2-Nq_k^2|<2\sqrt N$}
For nonsquare $N>1$, write the complete quotients after the initial term as $(\sqrt N+m)/d$. They exceed one, while their algebraic conjugates lie between minus one and zero. Thus $d<\sqrt N+m<2\sqrt N$. Comparing coefficients in $\sqrt N=(p_k\alpha_{k+1}+p_{k-1})/(q_k\alpha_{k+1}+q_{k-1})$ gives $p_k^2-Nq_k^2=d_{k+1}(p_kq_{k-1}-q_kp_{k-1})$, and the last determinant has absolute value one. These small residues are useful candidates for <smooth numbers> in congruence-of-squares factorization.
Back to article page
