Algebra

[Eric Hughes]

   So, how is division defined in Fp?

There's a wonderful little theorem of broad technical use which says
(a, b, m, n are all integers, or more generally, elements of a
Euclidean domain)

   \forall a, b \in Z \exists m, n \in Z : a m + b n = gcd( a, b )

What this says is the greatest common divisor of 'a' and 'b' is a
linear combination of them.  The algorithm to find the gcd is the
Euclidean algorithm; the algorithm to find the constants 'm' and 'n'
is the extended Euclidean algorithm.

To define multiplicative inverses in F_p, substitute 'p' for 'b' in
the above equation.  The gcd of 'p' and any non-zero element of F_p is
1.  (And we already knew you can't divide by zero.)  Now, reduce the
equation modulo p; this turns elements of Z into elements of F_p and
the second term of the addition goes to zero.  What you get is

   \forall a \in F_p \exists m \in F_p : a m = 1 (mod p)

That's the existence of multiplicative inverses in F_p.  Use the
extended Euclidean algorithm to calculate them.

Eric