The extended Euclidean algorithm

The quotients qk and remainders rk for the Euclidean algorithm for m/n are printed.

Here r0 = m > 0, r1 = n > 0,

 r0 = r1q1 + r2 (0 < r2 < r1) r1 = r2q2 + r3 (0 < r3 < r2) ··· rk-1 = rkqk + rk+1 (0 < rk+1 < rk) ··· rl-1 = rlql

Then rl = gcd(m,n). The sk and tk are also printed, where

 s0 = 1, s1 = 0, sk = sk-2 – qk-1sk-1, t0 = 0, t1 = 1, tk = tk-2 – qk-1tk-1, k = 2,...,l+1.

(In fact |sk| = Ak-2 and |tk| = Bk-2, where Ak/Bk is the kth convergent to m/n.)
Also the continued fraction for m/n is q1 + 1/q2 + ··· + 1/ql
The length l of the algorithm is printed, as is the continued fraction for -m/n.

Other properties of rk, sk and tk:

1. qk ≥ 1 for 1 ≤ k ≤ l and ql ≥ 2 if m > n and n does not divide m;
2. sk = (-1)k|sk|, tk = (-1)k+1|sk|;
3. 0 = |s1| < 1 = |s2| < ··· < |sl+1|;
4. 1 = |t1| ≤ |t2| < ··· < |tl+1|;
5. rk = skm + tkn, 0 ≤ k ≤ l+1;
6. m = |tk|rk-1 + |tk-1|rk, 1 ≤ k ≤ l+1;
7. |sk| = |sk-2| + qk-1|sk-1|, |tk| = |tk-2| + qk-1|tk-1|, k = 2,...,l+1;
8. sl+1 = (-1)l+1n/gcd(m,n), tl+1 = (-1)ln/gcd(m,n);
9. If gcd(m,n) = 1, then |sl| ≤ n/2, |tl| ≤ m/2.
Theorem (Aubry 1913, Thue 1902, Vinogradov 1926). Suppose gcd(m,n) = 1, m > n > 1. Then the congruence

nx ≡ y (mod m)

has a solution x, y satisfying 1 ≤ |x| < √m, 1 ≤ |y| ≤ √m, namely (x,y) = (tk,rk), where rk-1 > √m ≥ rk.
(Hint: Use (6).)

See lecture notes for an application to Hermite-Serret's proof of p=x2+y2. Also used in the paper Thue's theorem and the diophantine equation x2-Dy2=±N, K.R. Matthews, Mathematics of Computation, 71 (2002), 1281-1286. Also see BCMATH program.

Enter m (> 0):
Enter n (> 0):