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.