Multiplicative Inverses in Zn - Euclid's Algorithm

Previously we saw that the multiplicative inverse of 33 in Z₂₁₁ was 32 because 33x32=1 (mod 211). I also mentioned that this inverse could be calculated using Euclid's Algorithm. Here I will explain how this is done.

We begin by writing 211 in terms of multiples of 33 and a remainder, i.e. 211=6x33+13. We then split 33 into multiples of the remainder 13, i.e. 33=2x13+7. Repeating this process we continue until the remainder is 1. This repeated use of the division algorithm gives the following set of divisions and remainders:-

211=6x33+13
33=2x13+7
13=1x7+6
7=1x6+1

We now reverse the equations and express the remainder 1 in terms of the other remainders:-

1=7-1x6
6=13-1x7
7=33-2x13
13=211-6x33

We now eliminate the remainder 6 from the first equation using the second:-

1=7-1x(13-1x7)=-1x13+2x7

We now eliminate the remainder 7 from this equation using the third:-

1=-1x13+2x(33-2x13)=2x33-5x13

Finally we eliminate the remainder 13 from this equation using the fourth:-

1=2x33-5x(211-6x33)=-5x211+32x33

Rewriting this we get 33x32=5x211+1 which is what we obtained with the fx-50F.

It is not difficult to see that such a calculation is quite time consuming and it is easy to get lost in the process. If you had quite a few of these calculations to do, then the brute force method using a calculator seems much the better option!