$$\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?

  • $\begingroup$ I think the best way to do this might be to find a primitive root mod p. Even for large $p$, you can usually find a small primitive root - according to Wikipedia and assuming Riemann the smallest ist $\mathcal{O}(\log^6 p)$ $\endgroup$ – Cocopuffs Jun 14 '12 at 17:27

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$.


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.$


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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.