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

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.

• Legendre symbols are great if $n=2$. They would also be helpful if $n$ is a power of $2$, beyond that, not so much. – G Tony Jacobs Oct 10 '17 at 14:36
• You probably want to think of this in terms of solving the polynomial congruence $x^n-p_1\equiv 0\pmod{p_2}$. – G Tony Jacobs Oct 10 '17 at 14:38
• Apparently no way other than brute force. For example $x^3\equiv p \pmod q$ has no solution for $p=2,3,5$ and $q=7$ but how can you act if $p$ and $q$ are big? – Piquito Oct 10 '17 at 14:44
• This seems to be a really hard problem in general, even if we are just asking about the existence of a solution and not how to calculate it. I know of some special cases like $p_1=2$ $n=3$, but that case requires cubic reciprocity to answer for which $p_2$ there exists a solution and it's not a particularly simple answer. – MatheinBoulomenos Oct 10 '17 at 14:46
• I found something that can be useful:oxfordmathcenter.com/drupal7/node/179 – blaz11 Oct 10 '17 at 15:07

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