How to do the extended euclidean algorithm

[SpiffyEh]

Here's the definition I have:
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!

 

[rcgldr]

The goal here is to find the multiplicative inverse of 28, (1/28), modulo 75 so that

(t x 28) mod (75) = 1

it will also turn out that

(s x 75) mod (28) = 1

The algorithm iterates until it finds

(s x 75) + (t x 28) = 1

where s and t will have opposite signs. This only works if a and b are coprime, gcd(a,b) = 1. (Otherwise the algorithm iterates to 0 and the previous remainder will not be 1). Note that there is no inverse for 15 mod (75), since gcd(15, 75) = 5. For finite field math modulo(a), a should be a prime number.

Wiki article:

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

inverse which I'm assuming is -8 in that example?

Modulo(x) should have the same sign as x, in this case the range of (...) mod (75) are positive integers in the set {0 ... 74}.

(-8) mod (75) = 67, resulting in

(67 x 28) mod (75) = 1

 

[SpiffyEh]

I still don't understand it. I need someone to literally walk me through it so that I understand each step. I get what the algorithm is for but I don't understand that example I posted.

So the inverse is 67 in this case?

 

[rcgldr]

So the inverse is 67 in this case?

Yes 67 x 28 = 1876, and the nearest multiple of 75 less than 1876 is 25 x 75 = 1875, so (67 x 28) mod (75) = 1. Divide (67 x 28) / 75 = 1876/75, quotient = 25, remainder = 1. You could also use (-8 x 28) / 75, = -224/75, quotient = -3, remainder = 1.

literally walk me through it.

The article linked to below includes a better explanation of the extended euclidean algorithm, but without the requirement that the gcd(a,b) = 1.

extended-euclidean.html

It would help me to futher explain extended euclid algorithm if I knew what class your are taking, a math class, a programming class, something related to finite field math? If this is for finite field math, then 75 was a bad example because it's not a prime number. If a prime number was used instead, such as 79, then all integers from 1 to 78 would have an inverse modulo 79. This isn't true for 75, since any number that is a multiple of 3 or 5 will not have an inverse modulo 75.