Finding $n$-th root of $p_1$ modulo $p_2$

Question

How to calculate $n$-th root of a prime number $p_1\ \mbox{modulo}\ p_2$? That is: $x = p_1^\frac{1}{n}\ \bmod \ p_2$. I have a notion that somehow Legendre symbols can be use, however I can't quite grasp the concept.

Answer 1

I don't think there is a faster way to solve this problem other than checking all the numbers from $ 0 $ to $ p_2-1 $. In fact a lot of the time there is no solution.

If you want to check if there is a solution without actually finding it use this method:

If $n$ doesn't divide $p_2-1$ then there is a solution. If $n$ does divide $p_2-1$, then there is a solution iff $${p_1}^{\frac{p_2-1}{n}} \equiv 1 \pmod{p_2} $$

This may not seem much simpler but it is faster for a computer to do, especially if you are dealing with big numbers.

Answer 2

To ease the notations, write $p=p_2$ and $l=p_1$. The problem is to solve the congruence $x^n\equiv l\pmod p$. The map "raising to the $n$-th power" in $\mathbf F_p^*$ has kernel $\mu_n (\mathbf F_p)$ (= the group of $n$-th roots of $1$ contained in $\mathbf F_p^*$) and cokernel $\mathbf F_p^*/{\mathbf F_p^*}^n$. This can be conveniently summarized by the exact sequence $1 \to \mu_n (\mathbf F_p)\to\mathbf F_p^* \to \mathbf F_p^* \to \mathbf F_p^*/{\mathbf F_p^*}^n \to 1$ which shows, since we are dealing with finite cyclic groups, that $\mu_n (\mathbf F_p)$ and $\mathbf F_p^*/{\mathbf F_p^*}^n$ have the same order = gcd ($n, p-1$). Let us consider two extreme cases, then the general case : (i) if $n$ and $p-1$ are coprime, then $\mathbf F_p^*={\mathbf F_p^*}^n$, which means that for any integer $a$ not divisible by $p$, the congruence $x^n\equiv a\pmod p$ has one and only one solution ; (ii) if $n$ divides $p-1$, the previous congruence has a solution iff $a^{\frac {p-1}n }\equiv 1\pmod p$, and in this case, there are exactly $n$ solutions which differ (multiplicatively) by an $n$-th root of $1$ ; (iii) in the general case, denoting by $[a]$ the class of $a\pmod p$, the solvability of the congruence $x^n\equiv a\pmod p$ is equivalent to $[a]\in {\mathbf F_p^*}^n$. Again, since we are dealing with finite cyclic groups, this simply means that the order of $[a]\in {\mathbf F_p^*}$ divides the order of the subgroup group ${\mathbf F_p^*}^n$, which is $(p-1)/gcd (p-1, n)$. Note that we don't need to take $a=l$.

As you suspected, the main interest of this problem lies in the so called power residue symbol which generalizes the quadratic and cubic residue symbols (Gauss, Eisenstein) using class field theory (for CFT over number fields, see e.g. Cassels-Fröhlich, chap.VII by Tate). Let me try to give just an idea, sticking to the base field $K=\mathbf Q(\mu_n)$. For $p$ not dividing $a$ as above, suppose further that $p$ is unramified in $K$, i.e. $p$ does not divide $disc(K)$. Then, for any prime ideal $P$ of $K$ above $p$, $n$ divides $NP-1$ (where $NP$ is the norm of $P$). Moreover (and more deeply), given $L=K(\sqrt [n] a)$ with $a\in K^*$ and not divisible by $P$, one can construct the so called Frobenius map $F_{L/K}(P)$ (op. cit., §3) and define the symbol $(\frac aP)\in \mu_n$ by the equation $F_{L/K}(P)(\sqrt [n] a)/(\sqrt [n] a) = (\frac aP)$. In our particular case, $(\frac aP)$ is the unique $n$-th root of $1$ such that $(\frac aP)\equiv a^{\frac {NP-1}n}\pmod P$ (generalized Euler criterion). The name "power residue symbol" comes from the following property : $(\frac aP) =1$ iff the congruence $x^n\equiv a\pmod P$ has a solution $x$ in the ring of integers of $K_P$ (= the completion of $K$ at $P$). References : op. cit., exercises 1.4, 1.5, 1.9,2.14 .