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.