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):
Last modified 5th October 2007
Return to main page