12,502,578 members (54,613 online)
alternative version

71.4K views
20 bookmarked
Posted

# Extended Euclidean Alogo

, 29 Aug 2001
 Rate this:
To detemine multiplicative inverse.

## Introduction

The statement of the Extended Euclidean Algorithm Theorem. (Extended Euclidean Algorithm.) Let `m` and `n` be positive integers. Define:

```a[0] = m,  a[1] = n,

q[k] = Floor (a[k-1]/a[k])  for  k > 0,

a[k] = a[k-2] - a[k-1] q[k-1]  for  k > 1,

x[0] = 1,  x[1] = 0,  y[0] = 0,  y[1] = 1,

x[k] = x[k-2] - q[k-1] x[k-1]  for  k > 1,

y[k] = y[k-2] - q[k-1] y[k-1]  for  k > 1.
```

If `a[p]` is the last nonzero `a[k]`, then:

```a[p] = (m,n) = x[p] m + y[p] n.
```

(The `Floor` of a real number `x` is the greatest integer less than or equal to `x`. So `Floor(1.5)` = 1, `Floor(-2.1)` = -3, and `Floor(0)` = 0.)

Don't be alarmed by all the subscripts! Believe it or not, the algorithm isn't bad for hand computation if you're careful to arrange the numbers in a table.

Before I give the proof, here's a quick overview. The `q`s compute the greatest common divisor by successive division, i.e., using the standard Euclidean algorithm. Nothing new there! The `x`s and `y`s are for bookkeeping; they eventually yield the coefficients in the linear combination.

Proof. I'll take for granted the statement and proof of the standard Euclidean algorithm.

Ignoring the `x`s and `y`s, the computation of the `a`s and `q`s is the same as the computation of the standard Euclidean algorithm: the `a`s are the remainders, and the `q`s are the quotients. Thus, the algorithm terminates, and when it does, the last nonzero `a` is the greatest common divisor `(m,n)`.

I claim that:

`x[k]a[0] + y[k]a[1] = a[k]  for  k > 0.`

I'll prove this using induction.

For `k` = 1, I have:

`x[1]a[0] + y[1]a[1] = 0[1] a[0] + 1[1] a[1] = a[1].`

Now, take `k` > 1, and assume that the result is true for all indices less than or equal to `k`. I want to prove the result for `k` + 1. Compute:

```x[k+1] a[0] + y[k+1] a[1] =

(x[k-1] - q[k] x[k]) a[0] + (y[k-1] - q[k] y[k]) a[1] =

(x[k-1] a[0] + y[k-1] a[1]) - q[k] (x[k] a[0] + y[k] a[1]) =

a[k-1] - q[k] a[k] =

a[k+1].
```

The first equality comes from the definition of the `x`s and the `y`s. I used the induction hypothesis to get the third equality. The last equality uses the definition of the `a`s.

The result is true for `k` + 1, so it's true for all `k` > 0, by induction. In particular, if `a[p]` = `(m,n)` is the last nonzero `a`, then:

```x[p] a[0] + y[p] a[1] = a[p] = (m,n).
```

## The Extended Euclidean Algorithm

If `m` and `n` are integers (not both 0), the greatest common divisor `(m,n)` of `m` and `n` is the largest integer which divides both `m` and `n`. The Euclidean algorithm uses repeated division to compute the greatest common divisor.

The greatest common divisor of `m` and `n` can be expressed as an integer linear combination of `m` and `n`. That is, there are integers `c` and `d` such that,

```(m,n) = c m + d n.
```

There are infinitely many pairs of numbers `c`, `d` that work; sometimes, you can find a pair by trial and error. For example, (10,7) = 1, and by juggling numbers in my head, I see that:

```1 = (-2)(10) + (3)(7).
```

On the other hand, (367,221) = 1, but it's not likely that you'd figure out that:

```1 = (-56)(367) + (93)(221)
```

The Extended Euclidean Algorithm computes the greatest common divisor `(m,n)` of integers `m` and `n`, as well as numbers `c` and `d` such that:

```(m,n) = c m + d n.
```

A list of licenses authors might use can be found here

## Share

 United States
No Biography provided

## You may also be interested in...

 Pro Pro

 First Prev Next
 My vote of 1 ashkan.zamani7-Aug-12 18:47 ashkan.zamani 7-Aug-12 18:47
 My vote of 5 manoj kumar choubey14-Mar-12 3:54 manoj kumar choubey 14-Mar-12 3:54
 ZIPfile not available cbuchner17-Aug-02 23:31 cbuchner1 7-Aug-02 23:31
 Good Work Imran Farooqui30-Aug-01 19:27 Imran Farooqui 30-Aug-01 19:27
 Wow Annonymous30-Aug-01 12:52 Annonymous 30-Aug-01 12:52
 Re: Wow Jörgen Sigvardsson30-Aug-01 22:06 Jörgen Sigvardsson 30-Aug-01 22:06
 Re: Wow azam's25-Feb-07 18:04 azam's 25-Feb-07 18:04
 Last Visit: 31-Dec-99 18:00     Last Update: 25-Sep-16 21:12 Refresh 1