Applying Fermat's Little Theorem to Factorising Modulo p
\[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) \]
.
