Purpose of Fermat's Little Theorem What is the purpose of using Fermat's Little Theorem, and a proof of it?
 A: In modular arithmetic e.g. mod m you can reduce big numbers down to numbers between 0 and m.
Fermat's little theorem lets you reduce the exponents (of numbers of the form $b^e$) down to numbers between 0 and $\varphi(m)$ (without knowing anything about the base).

For example of the first, $x = 0,1,2$ or $3$ mod 4 so the number $x^2$ must be equal to 0 or 1 mod 4. So $x^2$ is of the form 4k or 4k+1.
For an example of the second, if p is prime $\varphi(p) = p-1$ then  $p^2 = 1$ mod p-1 so $x^{(p^2)} = x$ mod p. I just made that up but you can probably see from it that you can use this for lots of things.
A: Fermat's little theorem states that, for a prime $p$:
$$ a^p \equiv a \pmod{p} $$
alternatively:
$$ a^{p-1} \equiv 1 \pmod{p} $$
The easiest proof that I've seen is as follows:  Consider any integer, $g$, that is relatively prime to $p$.  Let $x$ be the product of all of the (distinct) integers $\pmod{p}$.  i.e.:
$$ x = 1 \cdot 2 \cdot 3 \dots (p-1) \pmod{p} $$
Now, multiply each term on the right by $g$:
$$ g^{p-1} x = (g \cdot 1) (g \cdot 2) (g \cdot 3) \dots (g \cdot (p-1)) \pmod{p} $$
Since multiplication is 1-1 and onto, all this does is permute the values involved in the product on the right to give back $x$.  So:
$$ g^{p-1} x = x \pmod{p} $$
$$ g^{p-1} = 1 \pmod{p} $$
One needs to prove multiplication is 1-1 and onto (for $p$ prime), but once that's done, the proof above is (in my opinion) straight forward and simple.
EDIT:  I originally restricted the product, $x$, to be the product of powers of a generator, $g$.  As lhf points out, this can be any number.  I've changed the above to reflect this.
A: Below is what Weil wrote on proofs of Fermat's little theorem, from p. 56 of his Number theory: An approach through history. As for its purpose, it helps serve to reveal the  multiplicative structure  of $\rm\:\mathbb Z/p\:,\:$ and problems in $\rm\:\mathbb Z\:$ are often best solved by reducing them to much simpler problems in its finite images $\rm\:\mathbb Z/p\:,\:$ e.g. so-called "local-global" principles. No doubt a search on "Fermat little" will uncover many applications - both here and elsewhere.


A: We prove by fermat's little theorem by induction. Firstly, the base case tells us that 
$1^{p} \equiv 1$ (mod $p$), which is true.
Assume true for $a=k$, namely that we assume $k^{p} \equiv k $ (mod $p$).
Then for $a = k+1$, we observe that $(k+1)^p - (k^p +1) = pk$ + $p \choose 2$ $k^2$ + $\ldots$ $k^{p-1}$ $p\choose p-1$.
I leave it as an exercise to check that the R.H.S. is divisible by $p$, and so we have the chain of congruences (using the induction hypothesis) that $(k+1)^p \equiv k^p + 1 \equiv k+1 $ (mod $p$). So the statement of fermat's little theorem is true for $a = 1$, $a = k$ and $a = k+1$ and hence is true for all natural numbers $k$.
$\hspace{6in}\blacksquare$
Ben
