How to find the solutions for the n-th root of unity in modular arithmetic?

$$\begin{align*} x^n\equiv1&\pmod p\quad(1)\\ x^n\equiv-1&\pmod p\quad(2)\end{align*}$$

Where $n\in\mathbb{N}$,$\quad p\in\text{Primes}$ and $x\in \{0,1,2\dots,p-1\}$.

How we can find the solutions for x without calculate all numbers (from 0 to p-1) high power n?

Or, in other words, how to find the n-th root of unity (and the negative of unity) using modular arithmetic without do all calculus table?

Solution 1:

Let $p$ be an odd prime. For the congruence $x^n \equiv 1 \pmod{p}$, let $g$ be a primitive root of $p$. There are very good probabilistic algorithms for finding a primitive root of $p$. After that, everything is easy.

Let $d=\gcd(n,p-1)$. Then our congruence has $d$ incongruent solutions modulo $p$. One solution is $h$, where $h \equiv g^{(p-1)/d}\pmod{p}$. To get them all, we look at $h^t$, where $t$ ranges from $0$ to $d-1$.

For the congruence $x^n \equiv -1\pmod{p}$, we must first determine whether there is a solution. There is a solution if and only if $(p-1)/d$ is even. One solution is then $g^{(p-1)/2d}$. The other solutions can be obtained by multiplying by $n$-th roots of $1$.

Solution 2:

The first equation is easier. The solution is based on the bit of knowledge that $G=\mathbb{Z}/p\mathbb{Z}^*$ is a cyclic group of order $p-1$. Let $d=\gcd(n,p-1)$. In a cyclic group of order $p-1$ the number of solutions of $x^n=1$ is equal to $d$. We can find these $d$ solutions, at least in theory, as follows. Let $g$ be a primitive element, i.e. a generator of $G$, so $$G=\{g^0=1,g^1,g^2,\ldots,g^{p-2}\}.$$ The solution is based on the fact that $g^j\equiv 1$, if and only if $(p-1)\mid j$. So $x=g^j$ is a solution of the equation $x^n=1$, if and only if $(p-1)\mid jn$. Here always $d\mid n$, so this holds if and only if $(p-1)/d \mid j$. Thus all the distinct solutions are $$ g^{j(p-1)/d},\ \text{for}\ j=0,1,\ldots,d-1. $$

The other equation is a bit trickier. We need the bit that $-1\equiv g^{(p-1)/2}$. This follows from the earlier part in the sense that the solutions to $x^2=1$ are $x=\pm1$. Therefore $x=g^j$ is a solution of $x^n=-1$, if and only if $$ nj\equiv (p-1)/2 \pmod{p-1}. $$ Here $nj$ is always divisible by $d$ that is also a factor of the modulus $(p-1)$. So if $d$ is not a factor of $(p-1)/2$ there will be no solutions. But if $d\mid(p-1)/2$, then $j=j_0=(p-1)/2d$ is one solution, and, as in the case of the first eqaution we get the others $j_k$ from the formula $j_k=j_0+kd$, $k=1,2,\ldots, d-1.$

Solution 3:

You can do this using primitive roots I think but I will just mention a few explicit points:

1) You only need to consider $n$ to be between $1$ and $p-2$ inclusive by Fermat's little theorem.

2) The non-zero integers mod $p$ form a multiplicative group of order $p-1$. Lagrange's theorem applies and tells us that no "non-$1$" number can satisfy $x^n \equiv 1 \bmod p$ for any $n$ coprime to $p-1$. So you need only solve the problem for powers sharing a proper factor with $p-1$.

3) The number $1$ will solve all of the congruences.

4) The congruence $x^2 \equiv 1 \bmod p$ has exactly $2$ solutions, $\pm 1$, as expected.

5) Solving $x^{\frac{p-1}{2}} \equiv 1 \bmod p$ is the same as finding the quadratic residues mod $p$ by Euler's criterion.

6) The solutions to $x^m \equiv 1 \bmod p$ will all be solutions to $x^{mn} \equiv 1 \bmod p$ for any $n$.