Associated Topics || Dr. Math Home || Search Dr. Math

### Euclid's Extended Algorithm

```
Date: 09/16/2001 at 23:11:24
From: Anna
Subject: Extended euclid's algorithm

Can you please state for me the steps of Euclid's extended algorithm
in simple terms? All of the things I have been able to find about it
on the Internet have just confused me.

Thank you!
Anna
```

```
Date: 09/17/2001 at 14:08:13
From: Doctor Rob
Subject: Re: Extended euclid's algorithm

Thanks for writing to Ask Dr. Math, Anna.

Start the Euclidean Algorithm as usual, with two positive integers
r(1) and r(2) as input:

r(1) = q(3)*r(2) + r(3),  0 <= r(3) < r(2),
r(2) = q(4)*r(3) + r(4),  0 <= r(4) < r(3),
r(3) = q(5)*r(4) + r(5),  0 <= r(5) < r(4),
...

Now notice that the remainders r(3), r(4), r(5), and so on, can be
expressed as combinations of the two input numbers, r(1) and r(2), by
substitution:

r(3) = 1*r(1) - q(3)*r(2),
r(4) = 1*r(2) - q(4)*r(3),
= 1*r(2) - q(4)*[1*r(1) - q(3)*r(2)],
= -q(4)*r(1) + [1+q(3)*q(4)]*r(2),
r(5) = 1*r(3) - q(5)*r(4),
= 1*[1*r(1)-q(3)*r(2)] - q(5)*[-q(4)*r(1)+[1+q(3)*q(4)]*r(2)],
= [1+q(4)*q(5)]*r(1) - [q(2)+q(4)+q(2)*q(3)*q(4)]*r(2),

and so on.

It turns out that these coefficients of r(1) and r(2) can be computed
right along with the usual Euclidean Algorithm process as follows.
Let a(1) = b(2) = 1, a(2) = b(1) = 0.  Let the a(n)'s and b(n) be
computed recursively from the equations

a(n+2) = a(n) - q(n+2)*a(n+1),
b(n+2) = b(n) - q(n+2)*b(n+1).

Then for all n >= 1, you have

r(n) = a(n)*r(1) + b(n)*r(2).

Example:  Start with the two numbers 114 = r(1) and 48 = r(2).

114 = 2*48 + 18, so q(3) = 2 and r(3) = 18.
a(3) = a(1) - q(3)*a(2) = 1 - 2*0 = 1,
b(3) = b(1) - q(3)*b(2) = 0 - 2*1 = -2.
48 = 2*18 + 12, so q(4) = 2 and r(4) = 12.
a(4) = a(2) - q(4)*a(3) = 0 - 2*1 = -2,
b(4) = b(2) - q(4)*b(3) = 1 - 2*(-2) = 5,
18 = 1*12 + 6, so q(5) = 1 and r(5) = 6.
a(5) = a(3) - q(5)*a(4) = 1 - 1*(-2) = 3,
b(5) = b(3) - q(5)*b(4) = -2 - 1*5 = -7,
12 = 2*6 + 0, so q(6) = 2 and r(6) = 0.
a(6) = a(4) - q(6)*a(5) = -2 - 2*3 = -8,
b(6) = b(4) - q(6)*b(5) = 5 - 2*(-7) = 19.

Sure enough,

114 =  (1)*114 +  (0)*48,
48 =  (0)*114 +  (1)*48,
18 =  (1)*114 + (-2)*48,
12 = (-2)*114 +  (5)*48,
6 =  (3)*114 + (-7)*48,
0 = (-8)*114 + (19)*48.

You can keep track of the work like this

n      q(n)     r(n)     a(n)     b(n)
1               114        1        0
2                48        0        1
3        2       18        1       -2
4        2       12       -2        5
5        1        6        3       -7
6        2        0       -8       19

Start by filling in the first two rows with r(1) = one of input
numbers, r(2) = other input number, a(1) = b(2) = 1, a(2) = b(1) = 0.
For each new row labeled n, compute

q(n) = integer part of r(n-2)/r(n-1),
r(n) = r(n-2) - q(n)*r(n-1),
a(n) = a(n-2) - q(n)*a(n-1), and
b(n) = b(n-2) - q(n)*b(n-1).

Here's a larger example:

n      q(n)     r(n)     a(n)     b(n)
1              9810        1        0
2              7047        0        1
3         1    2763        1       -1
4         2    1521       -2        3
5         1    1242        3       -4
6         1     279       -5        7
7         4     126       23      -32
8         2      27      -51       71
9         4      18      227     -316
10        1       9     -278      387
11        2       0      783    -1090

If you need further explanation, please write again.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Number Theory
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search