Jump to content



Photo

extended euclid algorithm

euclid

  • Please log in to reply
No replies to this topic

#1 amnakhan786

amnakhan786

    Neowinian

  • 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




Click here to login or here to register to remove this ad, it's free!