Browse Groups

• ## Explaining the extended GCD algorithm

(1)
• NextPrevious
• It took me a long time to figure out the algorithm of the extended greatest common divisor. Now I can explain it in the way that I would have liked someone to
Message 1 of 1 , Jul 7, 2008
View Source
It took me a long time to figure out the algorithm
of the extended greatest common divisor.

Now I can explain it in the way that I would have liked
someone to have explained it to me.

The GCD algorithm to find the gcd of r0 and r1 is as follows:

Divide r1 into r0 to get quotient q1 and remainder r2.

r2 = r0 - q1 r1

Divide r2 into r1 to get quotient q2 and remainder r3.

r3 = r1 - q2 r2

Continue until the remainder is zero. Then the last
non zero remainder is the greatest common divisor.

Now to explain how this is extended to find the integers

t and s such that

t * r0 + s * r1 = GCD(r0,r1).

From the GCD algorithm we have a sequence of quotients
and remainders such that

r2 = r0 - q1 r1
r3 = r1 - q2 r2
r4 = r2 - q3 r3
etc

Now to find t and s such that

t * r0 + s * r1 = GCD(r0,r1).

We construct the sequence t0,t1,t2,...
and s0,s1,s2,...

such that

t0 r0 + s0 r1 = r0
t1 r0 + s1 r1 = r1
t2 r0 + s2 r1 = r2
t3 r0 + s3 r1 = r3
etc

Now to derive the algorithm for calculating the
t0,t1,t2,... and s0,s1,s2,....

t0 r0 + s0 r1 = r0.

Thus t0 = 1 and s0 = 0

t1 r0 + s1 r1 = r1

Thus t1 = 0 and s1 = 1

r2 = r0 - q1 r1

r0 = t0 r0 + s0 r1
r1 = t1 r0 + s1 r1

r2 = r0 - q1 r1
= [ t0 r0 + s0 r1] - q1 [ t1 r0 + s1 r1 ]
= [ t0 - q1 t1 ] r0 + [s0 - q1 s1] r1

r2 = t2 r0 + s2 r1

Thus

t2 = t0 - q1 t1
s2 = s0 - q1 s1
r2 = r0 - q1 r1

It continues in the exact same pattern.

t3 = t1 - q2 t2
s3 = s1 - q2 s2
r3 = r1 - q2 r2

until we get the zero remainder, at which
point we know the gcd, and the values of t and s.

Kermit

< kermit@... >
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.