more inverse

how could I forget fermat's little..
a^(p-1) = 1 mod p if p does not devide a, and 0 otherwise.
Multiply a^(p-2) with a and we will get:

a^(-1)= a^(p-2) mod p


together with fast powering algorithm this is handy and to some limit efficient!
An alternativ to the euclidian algorithm.

About fast powering algorithm:

toy example

5^11 mod 13
write 11 as a sum of power of 2 (like binary)
11= 1011, which means 11= 5^(2^3+2^1+2^0)= 5^(2^3)*5^2*5. Reduce mod 13 in each step and the numbers will stay low
so the result is 1*12*5= 60 mod 13= 8

In general:
create a table with relevant powers mod p to some limit, The easy part is that each number is just the square of the preceding one.