n_xgcd

n_xgcd uses the extended Euclidean algorithm, which always produces cofactors $\lvert a \rvert < x/2$ and $\lvert b \rvert < x/2$, apart from a few degenerate cases. The proof is by induction. Suppose that at some step $x_n = q y_n + r$ with $r \ge 1$ and $1 = s y_n - t r$ with $s < y_n/2$ and $t < y_n/2$. Then $1 = s y_n - t (x_n - q y_n) = (s + tq) y_n - t x_n$, and it suffices to show $s + tq < x_n/2$, since $t < y_n/2 < x_n/2$. At the previous step of the back-substitution we had $1 = s r - c d$ with $s < r/2$ and $c < r/2$, so $s + tq < r/2 + q y_n/2 = (r + q y_n)/2 = x_n/2$.