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