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**

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**