## Explaining the extended GCD algorithm

Expand Messages
• 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
• 0 Attachment
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.