26
= 1 * 15 + 11 
15
= 1 * 11 + 4 
11
= 2 * 4 + 3 
4
= 1 * 3 + 1 
3
= 3 * 1 + 0 
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 

Backsubstituting
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:
1
= 4  (11  2*4) 
= 3 * 4  11 
Next, I replace 4
by 1511:
1
= 3 * (1511)  11 
= 3*15  4*11 
I
finally replace 11 by the 2615:
1
= 3*15  4*(2615)

1 = 7*15  4*26

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:
26
= 1 * 23 + 3 
23
= 7 * 3 +
2 
3
= 1 * 2 + 1 
2
= 2 * 1 + 0. 

Backsubstitutions yield:
1

= 3  2 

= 3  (23  7*3) 

= 8*3  23 

= 8*(2623)  23 

= 8*26  9*23 
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
BackSubstitution 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_{i2}  [x_{i1}*q_{i2}])
(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 xvalues are given: x_{0} = 0 and
x_{1} = 1.
As usual, let's take a look at a simple example:
Say, we want to find the inverse
of 15 mod 26.
Step 0: 
26 = 1*15
+ 11 
x_{0} = 0 
Step 1: 
15 = 1*11
+ 4 
x_{1} = 1 
Step i: 

From step 2 on we
compute:
x_{i} = (x_{i2}  [x_{i1} * q_{i2}])
mod 26. 
Step 2: 
11 = 2*4
+ 3 
x_{2} =
(x_{0}
 [x_{1} * q_{0}])
= 0
 1*1 mod 26 = 25 
Step 3: 
4 = 1*3
+ 1 
x_{3} =
(x_{1}
 [x_{2} * q_{1}])
=
1  25*1 = 24 mod 26 = 2 
Step
4: 
3 = 3*1
+ 0 
x_{4} =
(x_{2}
 [x_{3} * q_{2}])
= 25  2*2 mod 26 = 21 


x_{5} =
(x_{3}
 [x_{2} * q_{3}])_{
}=
2  21*1 = 19 mod 26 = 7 
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.
