Fermat's Little Theorem
The crux to the RSA algorithm is another discovery by Fermat, called Fermat's little theorem. It is a statement about powers in modular arithmetic in the special case where the modular base is a prime number. The theorem is stated like this:
a(p-1) = 1 (mod p) (unless a is a multiple of p)
We proved this theorem in class, but just in case you'd like to check: try it out here, for a few values of p, and several values of a each time. Try also what happens if p is not prime ...
(HINT: try setting a value for p and changing values for a)