### The extended Euclidean algorithm

The quotients q_{k} and remainders r_{k} for the Euclidean algorithm for m/n are printed.
Here r_{0} = m > 0, r_{1} = n > 0,

r_{0} | = | r_{1}q_{1} + r_{2} | (0 < r_{2} < r_{1}) |

r_{1} | = | r_{2}q_{2} + r_{3} | (0 < r_{3} < r_{2}) |

| ··· | | |

r_{k-1} | = | r_{k}q_{k} + r_{k+1} | (0 < r_{k+1} < r_{k}) |

| ··· | | |

r_{l-1} | = | r_{l}q_{l} | |

Then r_{l} = gcd(m,n). The s_{k} and t_{k} are also printed, where

s_{0} = 1, | s_{1} = 0, | s_{k} = s_{k-2} – q_{k-1}s_{k-1}, | |

t_{0} = 0, | t_{1} = 1, | t_{k} = t_{k-2} – q_{k-1}t_{k-1}, | k = 2,...,l+1. |

(In fact |s_{k}| = A_{k-2} and |t_{k}| = B_{k-2}, where A_{k}/B_{k} is the kth convergent to m/n.)

Also the continued fraction for m/n is q_{1} + 1/q_{2} + ··· + 1/q_{l}

The length l of the algorithm is printed, as is the continued fraction for -m/n.
Other properties of r_{k}, s_{k} and t_{k}:

- q
_{k} ≥ 1 for 1 ≤ k ≤ l and q_{l} ≥ 2 if m > n and n does not divide m;
- s
_{k} = (-1)^{k}|s_{k}|,
t_{k} = (-1)^{k+1}|s_{k}|;
- 0 = |s
_{1}| < 1 = |s_{2}| < ··· < |s_{l+1}|;
- 1 = |t
_{1}| ≤ |t_{2}| < ··· < |t_{l+1}|;
- r
_{k} = s_{k}m + t_{k}n, 0 ≤ k ≤ l+1;
- m = |t
_{k}|r_{k-1} + |t_{k-1}|r_{k}, 1 ≤ k ≤ l+1;
- |s
_{k}| = |s_{k-2}| + q_{k-1}|s_{k-1}|,
|t_{k}| = |t_{k-2}| + q_{k-1}|t_{k-1}|, k = 2,...,l+1;
- s
_{l+1} = (-1)^{l+1}n/gcd(m,n), t_{l+1} = (-1)^{l}n/gcd(m,n);
- If gcd(m,n) = 1, then |s
_{l}| ≤ n/2, |t_{l}| ≤ 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) = (t_{k},r_{k}), where r_{k-1} > √m ≥ r_{k}.

(Hint: Use (6).)
See lecture notes for an application to Hermite-Serret's proof of p=x^{2}+y^{2}. Also used in the paper *Thue's theorem and the diophantine equation x*^{2}-Dy^{2}=±N, K.R. Matthews, Mathematics of Computation, **71** (2002), 1281-1286. Also see BCMATH program.

*Last modified 5th October 2007*

Return to main page