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!

Multiplicative Inverses in Zn - execution of the program

This program will give the multiplicative inverse of a number in Z_n. As discussed previously suppose we wish to find the inverse of 3 in Z₇. On running the program, the dispay shows A? This is the number whose inverse we require. Enter 3 and press [EXE]. The display then shows B? This is the number n. Enter 7 and press [EXE]. The display then shows AX-C+B-1=>X and the number 5. This indicates that the inverse 5 has been found and this matches what we expect.

We can look at bigger values of n. Consider n=211 which is a prime number. As 211 is prime then any number j>1 chosen from Z₂₁₁ will be coprime with 211 and so will have a multiplicative inverse. For example, running the program with j=33 and n=211 we find that its inverse is 32 in Z₂₁₁. This is because 33x32=1056=5x211+1.

What if j and n are not coprime. Running the program with j=8 and n=32 the calculator displays X<B=>Goto 0 and 0. This indicates that no multiplicative inverse has been found and this is to be expected as 8 and 32 have a common factors of 2, 4 and 8 and so are not coprime.

Multiplicative Inverses in Zn - the program

The logic for the multiplicative inverses program was discussed previously. Here is the logic converted into a program for the fx-50F:-

?→A:?→B:2→X:Lbl 0:B→C:While C<AX:C+B→C:WhileEnd:AX-C+B=1=>X▲X+1→X:X<B=>Goto 0:

This is pretty much how the program looks when keyed into the calculator in edit mode. Special Program Commands (? → => : Lbl While WhileEnd = < ▲ Goto) are input using the [SHIFT] [P-CMD] keys. The cursor key (marked Replay) is used to switch between various screens of commands. Memory variables A, B, C, and X are input using [ALPHA] [A], [B] etc keys. The ":" Separator Code command is used frequently and can be alternatively input using the [EXE] key.

This program is 57 steps in length.

Multiplicative Inverses in Zn - the logic

So how do we go about finding, say, the multiplicative inverse of 3 in Z₇? What we want is to find the number k such that 3xk=1 (mod 7). When you have a programmable calculator, the answer can be found in a systematic way. As Z₇ is the finite set {0,1,2,3,4,5,6}, we can assign each element of this set to k and then calculate the value of 3xk (mod 7). When we find that the result is 1, then the element we assigned to k is the multiplicative inverse of 3 in Z₇.

Following this method then, the results would be:-

3x0=0 (mod 7)
3x1=3 (mod 7)
3x2=6 (mod 7)
3x3=2 (mod 7) as 3x3=9=7+2
3x4=5 (mod 7) as 3x4=12=7+5
3x5=1 (mod 7) as 3x5=15=2x7+1

So we can stop the processing at this point as we have found the solution to the problem, i.e. 3x5=1 (mod 7). So 5 is the multiplicative inverse of 3 in Z₇.

Note that we can actually start the processing with k=2 since it is always true that jx0=0 (mod n) and jx1=j (mod n) (neither of which result in the value of 1) and we assume that we are not looking for the multiplicative inverse of either 0 or 1 (since 0 has no multplicative inverse and 1 is always its own inverse, i.e. 1x1=1 (mod n))

The logic for this processing is as follows:-

Input A (the number j whose inverse is sought)
Input B (the value of n)
Store 2 in X (the first value of k to try)
Label 0
Store B in C (C holds multiples of n)
While C is less than AX (AX is the product of jxk)
   Store C+B in C
WhileEnd
If AX-C+B=1 then
   Display X (this is the multiplicative inverse of j)
EndIf
Store X+1 in X (try the next value of k in the ordered set)
If X less than B then
   Goto Label 0
EndIf

Multiplicative Inverses in Zn

In Cryptography it is often necessary to find the multiplicative inverse of a number in Z_n. Z_n is the set of integers {0,1,2,3,...,n-1} so, for example, Z₇ is the set {0,1,2,3,4,5,6}. If we are multiplying two elements in Z₇, say 3 and 5, then we can obtain a result in Z₇ if we use modular arithmetic i.e. 3x5=15=2x7+1, so 3x5=1 (mod 7).

If j and k are elements of Z_n, then k is the multiplicative inverse of j (and vice versa) if jxk=1 (mod n). So in the above example, 5 is the multiplicative inverse of 3 in Z₇. Note that j has a multiplicative inverse in Z_n if and only if j and n are coprime (i.e. j and n have no common factor apart from 1).

One way in which to calculate the multiplicative inverse of a number in Z_n is to use Euclid's Algorithm. Armed with a programmable calculator, however, the multiplicative inverse can be found by brute force.

Approximate Integration - execution of the program

This program will produce the definite integral of the function f(x)=x² between the limits x=A and x=B (B>A). On running the program, the display shows A? (the lower limit of integration). To begin with, enter 0 and then press [EXE]. The display then shows B? (the upper limit of integration). Enter 3 and press [EXE]. The display then shows D?. This is the number of pairs of strips that the interval between x=A and x=B is to be divided into. Enter 2 and press [EXE]. The display then shows M and 9.

This value is correct because the integral of f(x)=x² between the limits x=0 and x=a is (1/3)a³ and with a=3, this is (1/3)3³=9. This is a useful way to check that the code has been implemented correctly.

Let's try something harder. It is very difficult to obtain an expression for the integral of the function f(x)=exp(-x³) with respect to x but an estimate of the definite integral can be obtained numerically. Changing the function in the program from x² to exp(-x³) can be done by following the notes in this previous post. For the new function key in [SHIFT] [e^x] [(-)] [ALPHA] [X] [x³] [)].

Integrating this new function between the limits of x=0 and x=1 we obtain the following results as the number of pairs of strips is increased from 1 to 9:-

D=1 M=0.816311175
D=2 M=0.807843586
D=3 M=0.807572494
D=4 M=0.807530216
D=5 M=0.807518914
D=6 M=0.807514894
D=7 M=0.807513181
D=8 M=0.807512351
D=9 M=0.807511911

As can be seen, the results show that an estimate of this integral is 0.808 to 3 significant figures (as there is no change in the fifth significant figure for D>5) and this value agrees with other estimates.

Approximate Integration - further comments on the program

One of the other things to note about this program is that I have had to reuse several of the memory variables. The fx-50F comes with six memory variables (A, B, C, D, X and Y) and one independent memory (M) but this was not sufficient for the purposes of the program. For example, I calculate the value of the x-ordinate and store it in memory variable X, but then immediately calculate the y-ordinate, x², and store that in memory X too. This can be done because the x-ordinate is not needed after the y-ordinate has been calculated.