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 | Science Articles, Homework Help, Discussion**

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

**Physics Forums | Science Articles, Homework Help, Discussion**