Some examples:
Let's use p=7
 $2^{\small{71}}1%3D2^61%3D641%3D63,$ a multiple of 7
 $3^{\small{71}}1=3^61=7291=728,$ a multiple of 7
 $4^{\small{71}}1=4^61=40961=4095,$ a multiple of 7
Let's use p=5
 $2^{\small{51}}1=2^41=161=15,$ a multiple of 5
 $3^{\small{51}}1=3^41=811=80,$ a multiple of 5
 $4^{\small{51}}1=4^41=2561=255,$ a multiple of 5


Fermat's little
theorem (not to be confused with
Fermat's last theorem)
states that if p is a
prime number, then for any
integer a, $a^pa$ will
be evenly divisible by p. This can be expressed in the notation of
modulo arithmetic as follows:
$a^p\equiv{a}$ (mod p)
A variant of this theorem is stated in the following form:
Fermat's little
theorem is the basis for the
Fermat primality test.
Euler's extension of Fermat's little theorem is the basis of the RSA publickey cryptosystem.
This theorem only works in one direction. Every prime
satisfies the equation, but there are nonprimes that
also satisfy it.
Can you find one?


 If n is a positive integer
 and $\phi(n)$ is how many numbers that are
 less than n and have no factors in common with n,
 then if a is one of those numbers,
 then $a^{\small\phi(n)}1$ is a multiple of n.
Let
p be a
prime. What we're going to do is write down one product, and then evaluate it
in two different ways. One way will give some
number $F,$ the other will give $a^{p1}F,$
and so these are equal.
So suppose we have a number $a$ which is between 1 and $p1$ inclusive.
Everything is being done modulo p.
We start by looking at the product $(p1)!$ which is $F=1\text{x}{2}\text{x}\ldots\text{x}(p1).$
This is some number which, because we are working modulo a prime, has a multiplicative inverse, $F^{1}.$
Now let's look at the product
 $P{\equiv}(1.a)\text{x}(2a)\text{x}(3a)\text{x}\ldots\text{x}((p1)a).$
This is the magic formula that we'll evaluate in two different ways.
If $ma{\equiv}na,$ multiplying by $a^{1}$ shows that $m=n.$
That means that each of the terms $a,~2a,~3a,~\ldots~(p1)a$
must be different. 

Firstly, each of the elements here are different. The element
a has a multiplicative
inverse, so multiplying all the
number from 1 up to
p1 can be undone. That means we
can't get the same answer twice, so they're all different. That means that the product
is just the same elements multiplied in a different order, and so the product is again
F.
But let's rearrange it to bring all the a's to the front. Then
 $P{\equiv}(1.a)\text{x}(2a)\text{x}(3a)\text{x}\ldots\text{x}((p1)a)\quad\quad$ (equation 1)
is the same as
 $P{\equiv}a^{p1}(1)\text{x}(2)\text{x}(3)\text{x}\ldots\text{x}(p1)\quad\quad$ (equation 2)
Equation (1) shows that $P{\equiv}F$
(because it's the same product in a different order)
Equation (2) shows that $P{\equiv}a^{p1}F$
So $F{\equiv}a^{p1}F$
Now we can multiply by $F^{1}$ and we can see that $1{\equiv}a^{p1}$
which is the result we wanted!