I know the extended euclidean algorithm by working myself backward from the euclidean algorithm to find the GCD. I'm confused with the extended euclidean algorithm as given in this page. How is this process derived and why are we introducing new variables s and t? How is this process derived from working backwards with the standard euclidean algorithm? And how does the computation work now that we have $s_0, s_1, t_0, t_1$, which is neither intuitive nor any explanation is given anywhere.
No comments:
Post a Comment