## Applying Fermat's Little Theorem to Factorising Modulo p

For any prime
$p$
,
$x^{p-1}=1 \equiv (x-1)(x-2)...(x-(p-1)) \; (mod \; p)$
.
It is a consequence of Lagrange's Theorem that a polynomial of degree
$k$
has at most
$k$
possible roots. Any polynomial of the form above has exactly
$p-1$
roots
$(mod \; p)$
.
This is a direct consequence of Fermat's Little Theorem since the equation
$x^{p-1} -1 \equiv 0 \; (mod \; p)$
is satisfied by the
$p-1$
incongruent number
$x \equiv 1, \; 2, \; 3,..., \; p-1$
. Hence, by Factorising a Congruence

$x^{p-1}=1 \equiv (x-1)(x-2)...(x-(p-1)) \; (mod \; p)$
.