Proof That if d Divides p-1, the Congruence x^d-1 =0 mod p has Exactly d Solutions
If
\[p\]
is a prime and \[d\]
is a divisor of \[p-1\]
then the congruence \[x^d-1 \equiv 0 \; (mod \; p)\]
has exactly \[d\]
solutions.Proof
Let
\[p-1=dr\]
for some integer \[r\]
. If \[r-1\]
then \[d=p-1\]
and the result follows from tApplying Fermat's Little Theorem to Factorising Modulo p. Assume \[r \gt 2\]
.\[x^{p-1}-1=(x^d-1)(x^{d(r-1)}+x^{d(r-2)}+...+x^+1)=(x^d-1)Q(x) \; (mod \; p) \]
where
\[Q(x)\]
has degree \[d(r-1)\]
.We know from Applying Fermat's Little Theorem to Factorising Modulo p that
\[x^{p-1}-1 \equiv 0 \; (mod \; p)\]
has \[p-1\]
solutions If \[a\]
is such a solution then \[a^{p-1}-1 \equiv (a^d-1)Q(a) \equiv 0 \; (mod \; p)\]
.Euclid's Lemma informs us that either
\[x^d-1 \equiv 0 \; (mod \; p)\]
or \[Q(x) =(x^{d(r-1)}+x^{d(r-2)}+...+x^+1) \equiv 0 \; (mod \; p)\]
, so these two congruences between them have at least \[p-1\]
solutions.Apply Lagrange's Theorem. The congruence
\[x^d-1 \equiv 0 \; (mod \; p)\]
has at most \[d\]
solutions. and the congruence \[Q(x) \equiv 0 \; (mod \; p)\]
has at most \[d(r-1)\]
solutions so between them they have at most \[d+d(r-1)=dr=p-1\]
solutions. It follows that \[x^d-1 \equiv 0 \; (mod \; p)\]
has exactly \[d\]
solutions. 
