Jump to content


extended euclid algorithm


  • Please log in to reply
No replies to this topic

#1 amnakhan786



  • 2 posts
  • Joined: 19-November 12

Posted 19 November 2012 - 08:53

can i prove by induction on b that , for all positive integers a and b such that a > b, the triple (d; s; t) returned
by EEgcd(a; b) indeed satis es d = s  a + t  b. I donot have a clue how to prove this. How i should start?

Any help is appreciated