The hunt for multiplicative inverses

The inverse of a, a^1=z mod m. Calculation aint easy for large m, this is where all the computing power goes.
a does have an inverse mod m if and only if a*z=1 mod m. Otherwice there is no inverse.
If our finite field is prime, then all members sport this property

We can find the inverse by using euclid. We know that in the Euclidean Algorithm you repeatedly divide the divisor by the remainder until the remainder is 0.
The gcd is then the last non-zero remainder.
We can write
za + mb = 1. This says that za = 1 + (-b)m, which means za=1 (mod m). We dont care about -b in this case of cause. So z is the inverse of a.

The extended version gives us z.
Nice tiny toy example here:
http://www-math.cudenver.edu/~wcherowi/courses/m5410/exeucalg.html