Prove or disprove. For $m,n\in\mathbb{N}$ (natural numbers), $x^n = 1\mod m$ has maximum $n$ roots. Also, does $x^n = 1\mod m$ always have $n$ roots?
Since in real numbers $x^n = 1$ has maximum n roots, I also want to make sure if this is true or false in $\mathbb{Z}_m$. Can someone prove/disprove it for me?
Lagrange proved the following theorem.
Suppose $p$ is a prime and $f(x)$ is a polynomial of degree $n$ with integral coefficients. Then either $f$ is identically $0$ as a polynomial mod $p$ or the congruence $f(x) \equiv 0\mod{p}$ has at most $n$ solutions.
Proof. If $f$ is identically $0$ as a polynomial modulo $p$, there is nothing to prove. Henceforth suppose $f(x)=\sum_{i=0}^n c_ix^i$ with $p \nmid c_n$. We show that $f(x) \equiv 0\pmod{p}$ has at most $n$ solutions modulo $p$ by induction on the degree of $f$.
When $n=1$ the congruence $c_0+c_1x \equiv 0\pmod{p}$ has exactly one solution since $p \nmid c_1$. Suppose the theorem holds for all polynomials of degree $\le n-1$. Assume that $f$ is of degree $n$, and that the congruence $f(x) \equiv 0\mod{p}$ has $n+1$ solutions $x_0,\ldots,x_n$ that are incongruent mod $p$. Since
$$ f(x)-f(x_0) = \sum_{i=1}^n c_i(x^i-x_0^i) = (x-x_0)g(x), $$
where $g(x)$ is a polynomial with integer coefficients of degree $n-1$ and with leading coefficient $c_n$, we have
$$ f(x_k)-f(x_0) = (x_k-x_0)\,g(x_k) \equiv 0\pmod{p}. $$
Since $p \nmid (x_k-x_0)$ for $k \ne 0$, we must have $g(x_k) \equiv 0\pmod{p}$ for each $k \ne 0$. But then the congruence $g(x) \equiv 0\pmod{p}$ has $n$ incongruent solutions modulo $p$, contradicting our induction hypothesis. $\blacksquare$
Remark 1. Lagrange's Theorem implies that if a polynomial of degree $n$ with integer coefficients admits more than $n$ incongruent solutions modulo $p$, then every coefficient of $f$ must be divisible by $p$.
Remark 2. The result of this theorem does not hold for non-prime modulus. For example,
$$ x^2 \equiv 1\pmod{8} $$
has the four solutions $x \equiv \pm 1, \pm 3\pmod{8}$.