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?
 A: 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.$
A: 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$.
A: 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$.  
