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.

 

[LudusRex]

The extended Euclidean algorithm is a method used to find the greatest common divisor (gcd) of two numbers, as well as the values of r, s, and t such that sa + tb = r. This algorithm is based on the Euclidean algorithm, which is used to find the gcd of two numbers by repeatedly dividing the larger number by the smaller number until the remainder is 0. The extended Euclidean algorithm adds the additional step of keeping track of the values of s and t as the algorithm progresses.

To begin, we start with the two numbers a and b. The algorithm works by repeatedly finding the remainder when a is divided by b, and then updating the values of a and b for the next iteration. This is shown in the attached image, where the values of a and b are updated in each row of the table. The algorithm continues until the remainder is 0, at which point the gcd is equal to the last non-zero remainder.

In the example given, the gcd of 240 and 46 is 2. The algorithm finds this by first dividing 240 by 46, with a remainder of 2. The values of a and b are then updated to 46 and 2, respectively. This process continues until a remainder of 0 is reached. At this point, the gcd is equal to the last non-zero remainder, which is 2 in this case.

The values of s and t are found by working backwards from the last row of the table. In this example, the last two rows correspond to the equation sa + tb = r, where r is the gcd. By substituting in the values of a and b from the last row, we can solve for s and t. In this case, we get s = -8 and t = 41.

To obtain the inverse of a number, we can use the extended Euclidean algorithm to find the values of s and t that satisfy sa + tb = 1. In the example given, we can see that sa + tb = gcd(a, b) = 2. Therefore, we can multiply both sides of the equation by the inverse of 2, which is 1/2. This gives us (s/2)a + (t/2)b = 1. So, the inverse of a can be found by multiplying s/2 by a. In the example, this gives us -4 x 240 = -960, which is the inverse