the_extended_euclidean_algorithm

Given two positive integers m and n, we find their greatest common divisor d and two integers a and b, such that am + bn = d.

We compute the gcd as well as finding integers that satisfy the bezouts_lemma

1. [Initialise] Set a^′ ← b ← 1, a ← b^′ ← 0, c ← m, d ← n
2. [Divide] Let q, r be the quotient and remainder, respectively, of c divided by d. c = qd + r, 0 ≤ r < d
3. [Remainder zero?] If r = 0, we are done as am + bn = d
4. [Recycle] Set c ← d, d ← r, t ← a^′, a^′ ← a, a ← t − qa, t ← b^′, b^′ ← b, b ← t − qb Go to step 2.

TODO transclude code/the_extended_euclidean_algorithm.c here

If we forget about a, b, a^′, b^′ and use m, n instead of c, d we get the euclidean_algorithm.

proving the_extended_euclidean_algorithm using proof_by_induction

backlinks

• euclidean_algorithm
• index_of_files.pd