Loading ...
Sorry, an error occurred while loading the content.

Explaining the extended GCD algorithm

Expand Messages
  • Kermit Rose
    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.