The remainder of the 2^nd to last line, 1, yields the gcd of 15 and 26. We can drop the irrelevant last equation. 
                                         

Step 2: "Euclidean Algorithm Backwards" 
We now substitute backwards until the gcd(26,15)=1 is expressed as a linear combination of 26 and 15. To do so, we first isolate each of the four remainders: Starting with the last equation:
    

1 =	4 -	3
		3	= 11 - 2 *	4
				4 = 15 -	11
					11=26 -15

Back-substituting these four identities enables us to express the gcd = 1 in terms of 26 and 15 n such as: 
gcd = 1 = x*26 + y*15 with x and y being integers. 
The inverse of 15 is y and we are done. Let's do it.

Replacing 3 by 11 - 2*4 yields:

Next, I replace 4 by 15-11: 

I finally replace 11 by the 26-15:

This is it. Let's first verify that 7*15 - 4*26 equals 1: 
7*15 - 4*26 = 105 - 104 = 1. Correct.
7 is the desired of 15 since the last equation can be read as 
1 = 7*15 mod 26. 
To verified that 7 is the inverse of 15: 7*15=105=1 mod 26. 

Two Important Observations:

1. By reversing the steps in the Euclidean Algorithm we can always express the gcd of the integers a and b in the form 

                gcd = x*a + y*b with two integers x and y. 

Consequently, if a and b have a greatest common divisor different from 1 (that is the gcd(a,b) is not 1) a does not have an inverse mod b. I.e. 14 has no inverse mod 26. However, it has mod 27, namely 2. (How do I know?) Therefore, we first execute the Euclidean Algorithm to check if a and the modulus b have a greatest common divisor of 1. Only in that case, the back substitutions yield an inverse. 

2. Having performed the back substitutions, we may end up with a negative value for the inverse. I.e. to find the inverse of 23 mod 26, we first execute the Euclidean Algorithm as follows:

Back-substitutions yield:  

Is 9 the inverse of 23 mod 26? It can not be since 9*23 = 207 and 207 = 25 = -1 MOD 26 which is not 1. 
The correct inverse is -9. This can be better seen if I rewrite the last equation as follows: 
1 = 8*26 + (- 9)*23. 
Since we want the inverse to be a positive number less than the modulus 26 we simply add 26 to -9 yielding 17 as our desired inverse:
Check:  17*23 = 391 = 260 + 130 + 1 = 1 mod 26. 

Conclusion: Whenever the coefficient x is negative, we have to add the modulus b to it in order to obtain the proper inverse as our decoding key.     

Use the Back-Substitution for the following 3 exercises:

Exercise 1: Find the inverse of 5 mod 26.   21

Exercise 2: Find the inverse of 19 mod 26.   11

Exercise 3: Find the inverse of 13 mod 22.    17

The above procedure works well, however, it is quite time consuming because of the back substitutions we have to make. It is possible to reduce the amount of computation involved in finding x and y by doing some auxiliary computations when performing step 1. No back substitutions will be necessary. This procedure is known as the Extended Euclidean Algorithm which I explain to you now. 

The Extended Euclidean Algorithm finds the Modular Inverse 

The following explanations are more of a technical nature. Read them if intend to implement the Euclidean Algorithm, skip them if you don't and go straight to the bottom of this page to view the Extended Euclidean Algorithm in action.  

Notice that we do not have to calculate the value of y in gcd = x*a + y*b since x yields the inverse of a mod b. We first have to number the steps of the Euclidean algorithm since we will make use of the quotients q. Starting with step 0, the quotient obtained at step i will be denoted as q_i. How are these values used? They are part of the formula 

x_i = (x_i-2 - [x_i-1*q_i-2]) (mod b) 

which is carried from step 2 on of the Euclidean algorithm.  If we perform these calculations for one step beyond the last step of the Euclidean algorithm it will yield the desired inverse. In step 0 and step 1 we don't compute anything since the x-values are given: x₀ = 0 and x₁ = 1. 

As usual, let's take a look at a simple example:

Say, we want to find the inverse of 15 mod 26.

Check: 15*7 = 105 = 1 + 4*26 = 1 mod 26. Thus, 7 is the inverse of 15 mod 26.

Exercise 4:
Find the inverse of 5 mod 26 using the Extended Euclidean Algorithm by hand.         21. Check below.  

Exercise 5:
Find the inverse of 19 mod 26 using the Extended Euclidean Algorithm by hand.     11. Check below.

Exercise 6:
Find the inverse of 13 mod 22 using the Extended Euclidean Algorithm by hand.    17. Check below.

Afterwards, verify your computations below.