Fermat's theorem proofFermatsTheoremProof2001-10-15 21:58:592008-01-30 16:37:57ProofFermat's little theorem0\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xypic}Consider the sequence $a,\,2a,\,\ldots,\,(p-1)a$.
They are all different (modulo $p$), because if $ma=na$ with $1\le m<n\le p-1$ then
$0=a(m-n)$, and since\, $p\nmid a$, we get $p\mid(m-n)$,\, which is impossible.
Now, since all these numbers are different, the set \,$\{a,\,2a,\,3a,\,\ldots,\,(p-1)a\}$\, will have the $p-1$ possible congruence classes (although not necessarily in the same order) and therefore
$$a\cdot2a\cdot3a\cdots (p-1)a\equiv (p-1)!a^{p-1}\equiv (p-1)!\pmod{p}$$
and using\, $\gcd((p-1)!,\;p)=1$\, we get
$$a^{p-1}\equiv 1\pmod{p}.$$