14
$\begingroup$

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

  • 0
    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)$2012-06-14

3 Answers 3