素数 $p$ に対し，$a$ を$p$の倍数でない自然数とすると，
$a^{p-1} \equiv 1 ~(\mbox{mod}~~ p) $，
が成り立つ．
定理中に現れた式は合同式というもので，両辺を$p$で割った時の余りは等しいことを示す．
$1 \le k \le p-1$ を満たす自然数$k$を用意する．次に，以下のような合同式を考え，自然数$r_k$ （$1 \le r_k \le p-1$) を考える．
$k \cdot a \equiv r_k ~(\mbox{mod}~~ p).$ (1)
つまり$r_k$は $k \cdot a$を$p$で割った余りである．余りが $0$ にならないのは，$p$ が素数であり，$a$ と $p$ が互いに素だからである．式(1)を $1 \le k \le p-1$の範囲で全て掛け算する．
$(p-1)! \cdot a^{p-1} \equiv \Pi_{k=1}^{p-1} r_k ~(\mbox{mod}~~ p).$ (2)
ここでもしある $i, j$ を選び $i \ne j$ だとする．この時に $r_i = r_j$ が成り立つと，式(1)を $i, j$ の場合について選んで引き算することで，
$(i-j) a \equiv (r_i -r_j)~(\mbox{mod}~~ p),$
となる．$a, p$は互いに素で，$1 \le i, j \le p$ であるから，$|i-j| < p$であり，$i-j$ と $p$ が互いに素である．よって左辺は$p$で割り切れないから右辺も割り切れない．このことから，
$r_i - r_j \ne 0 ,$
が示される．つまり $r_k ~(1 \le k \le p-1)$ には $1$ から $p-1$ までの自然数が1個ずつ含まれる．このことを用いると，
$(p-1)! = \Pi_{k=1}^{p-1} r_k$ ,
となる．これらは $p$ で割り切れないので，合同式 (2) の両辺に割り算が適用でき，
$a^{p-1} \equiv 1 ~(\mbox{mod}~~ p) $，
が示される．