Let $p$ be a prime. Prove that $x^m \bmod p = 1$ has at most $m$ solutions for $x \in U(p)$ using only group theory (no polynomials allowed)

Question

This is part of a homework problem I am working on. In light of this, please do not post an entire solution. I've been told that we do not have to use anything but Fermat's little theorem and a bit of group theory to prove this result. And I'm honestly out of ideas on how to do it. Every resource I've found seems to suggest that polynomial roots and field theory is necessary.

Answer 1

Rule Number 1. $(\mathbb Z/p\mathbb Z)^\times$ is cyclic, generated by some element $a$ of order $p-1$. So whatever solution you are after, it must be a power of $a$.

Answer 2

We can try to "hide" the polynomial part, for example: look at the Vandermonde determinant (the polynomial is hidden here) $$ \det\begin{bmatrix}1&x_1&x_1^2&\dots&x_1^m\\1&x_2&x_2^2&\dots&x_2^m\\1&x_3&x_3^2&\dots&x_3^m\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_{m+1}&x_{m+1}^2&\dots&x_{m+1}^m\end{bmatrix}=\prod_{1\leq i<j\leq m}(x_j-x_i) $$ If $x_1,\dots,x_{m+1}$ are solutions to $x^m\equiv 1\pmod{p}$, then the matrix has two identical columns (mod $p$) so LHS is $\equiv 0\pmod{p}$. So $p$ must divide one of the factor on the RHS.