Does the equation $x^n\equiv 1\pmod p$ has at most $n$ solutions?

Question

Does the equation $x^n\equiv 1\pmod p$, $p$ being a prime has at most $n$ solutions? If it does, how to show it? (I don't know a thing about fields.)

Answer 1

Theorem (Lagrange). If $\newcommand{\polynn}[3]{{#1_{#3}#2^{#3}+#1_{#3-1}#2^{#3-1}+\ldots+#1_0}}f(x)=\polynn axn$ is a polynomial with integer coefficients, $p$ is a prime and $p\nmid a_n$, then the congruence $\newcommand{\kong}[3]{{#1\equiv #2\pmod{#3}}}\kong{f(x)}0p$ has at most $n$ solutions (modulo $p$).

Equivalently, if this congruence has more than $n$ (non-congruent) solutions, then $p$ divides all coefficients of the polynomial $f(x)$.

Proof. By induction on $n$.

For $n=1$ this follows from the well-known result about solutions of linear congruences $\kong{ax+b}0p$. (We know that the number of solutions is $\gcd(a,p)=1$.

Suppose the claim is true for $n-1$. Suppose $x_0,\dots,x_n$ would be $n+1$ diferent solutions of $\kong{f(x)}0p$. Then we have $$f(x)-f(x_0)=\sum_{k=1}^n a_k(x^k-x_0^k)= (x-x_0)\sum_{k=1}^n a_k(x^{k-1}+x^{k-2}x_0+x^{k-3}x_0^2+\ldots +x_0^{k-1})=(x-x_0)g(x),$$ where $g(x)$ is a polynomial of degree $n-1$ with the leading coefficient $a_n$.

So we get $\kong{(x_i-x_0)g(x_i)}0p$ and $\kong{g(x_i)}0p$ for each $i=1,\ldots,n$. Thus $\kong{g(x)}0p$ has $n$ solutions. None of these solutions are congruent modulo $p$. This contradicts the inductive hypothesis. $\hspace{3cm}\square$

Answer 2

Disclaimer: The OP wants an elementary proof, which this is not.

Yes. We can show by induction that for any monic polynomial $P$ of degree $n$, $P(x) \equiv 0 \pmod p$ has at most $n$ solutions. In particular, take $P(x) = x^n - 1$.

• Base case $x + c \equiv 0$ has exactly one solution.

• Inductive step Consider the equation $P(x) \equiv 0 \pmod p$, where $P(x)$ is monic of degree $n+1$. If it has no solutions, we are done. Otherwise, it has some solution $a$. Then, because the ring of polynomials over a base field forms a PID (hence a UFD), we can factor $P(x) = (x - a)Q(x)$ for some monic $Q$ of degree $n$. By inductive hypothesis, $Q$ has at most $n$ solutions, so $P$ has at most $n+1$.