In Cryptography it is often necessary to find the multiplicative inverse of a number in Zn. Zn is the set of integers {0,1,2,3,...,n-1} so, for example, Z7 is the set {0,1,2,3,4,5,6}. If we are multiplying two elements in Z7, say 3 and 5, then we can obtain a result in Z7 if we use modular arithmetic i.e. 3x5=15=2x7+1, so 3x5=1 (mod 7).
If j and k are elements of Zn, 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 Z7. Note that j has a multiplicative inverse in Zn 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 Zn is to use Euclid's Algorithm. Armed with a programmable calculator, however, the multiplicative inverse can be found by brute force.
