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:
- qk ≥ 1 for 1 ≤ k ≤ l and ql ≥ 2 if m > n and n does not divide m;
- sk = (-1)k|sk|,
tk = (-1)k+1|sk|;
- 0 = |s1| < 1 = |s2| < ··· < |sl+1|;
- 1 = |t1| ≤ |t2| < ··· < |tl+1|;
- rk = skm + tkn, 0 ≤ k ≤ l+1;
- m = |tk|rk-1 + |tk-1|rk, 1 ≤ k ≤ l+1;
- |sk| = |sk-2| + qk-1|sk-1|,
|tk| = |tk-2| + qk-1|tk-1|, k = 2,...,l+1;
- sl+1 = (-1)l+1n/gcd(m,n), tl+1 = (-1)ln/gcd(m,n);
- 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.
Last modified 5th October 2007
Return to main page