Click here to Skip to main content
11,433,997 members (50,843 online)
Click here to Skip to main content

Extended Euclidean Alogo

, 29 Aug 2001
Rate this:
Please Sign up or sign in to vote.
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 qs compute the greatest common divisor by successive division, i.e., using the standard Euclidean algorithm. Nothing new there! The xs and ys 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 xs and ys, the computation of the as and qs is the same as the computation of the standard Euclidean algorithm: the as are the remainders, and the qs 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 xs and the ys. I used the induction hypothesis to get the third equality. The last equality uses the definition of the as.

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)

by juggling numbers in your head!

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Junaid Majeed

United States United States
No Biography provided

Comments and Discussions

 
GeneralMy vote of 1 Pin
ashkan.zamani7-Aug-12 19:47
memberashkan.zamani7-Aug-12 19:47 
GeneralMy vote of 5 Pin
manoj kumar choubey14-Mar-12 4:54
membermanoj kumar choubey14-Mar-12 4:54 
GeneralZIPfile not available Pin
cbuchner18-Aug-02 0:31
membercbuchner18-Aug-02 0:31 
GeneralGood Work Pin
Imran Farooqui30-Aug-01 20:27
memberImran Farooqui30-Aug-01 20:27 
GeneralWow Pin
Annonymous30-Aug-01 13:52
memberAnnonymous30-Aug-01 13:52 
GeneralRe: Wow Pin
Jörgen Sigvardsson30-Aug-01 23:06
memberJörgen Sigvardsson30-Aug-01 23:06 
GeneralRe: Wow Pin
azam's25-Feb-07 19:04
memberazam's25-Feb-07 19:04 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.150428.2 | Last Updated 30 Aug 2001
Article Copyright 2001 by Junaid Majeed
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid