Here's the definition I have:(adsbygoogle = window.adsbygoogle || []).push({});

Extended Euclidean algorithm

Takes a and b

Computes r, s, t such that

r=gcd(a, b) and, sa + tb = r

(only the last two terms in each of these sequences at any point in the algorithm)

Corollary. Suppose gcd(r0, r1)=1. Then

r_1-1 mod r_0=t_m mod r_0.

The example is in the attached image.

I don't understand the steps used to obtain all the values in the table or how to get the inverse which i'm assuming is -8 in that example?

If someone could guide me though it that would be very helpful, I've been struggling with it for hours now.

Thank you!

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# How to do the extended euclidean algorithm

Loading...

Similar Threads for extended euclidean algorithm |
---|

Insights Intro to Algorithms for Programming - Comments |

Python Verlet algorithm and Lorentz force trajectory |

C/++/# Is there a flaw in my longest common subsequence algorithm? |

C/++/# Finding duplicates algorithm |

Perceptron algorithm initial vector |

**Physics Forums - The Fusion of Science and Community**