Take the 2-minute tour ×

For fixed $n$ and $k$, how can I characterize the primes $p$ such that $x^k\equiv n\pmod p$?

Less important to me: Is there a similar characterization for composite moduli? Assume the factorization is known.

Example: the primes for which $x^4\equiv21$ is solvable are 2, 3, 5, 7, 17, 43, 47, 59, 67, 79, 83, 109, 127, 131, 151, 163, ...; is there an easier way to express this sequence?

This is the corrected version of this question where I clearly lost my train of thought while posting.

share|improve this question
If you can determine whether the congruence has solutions for prime power moduli, then you can determine it for composite moduli (Chinese Remainder Theorem). For any prime $p$ that does not divide $k$, Hensel's Lemma tells you that it can be solved modulo $p^m$ if and only if it can be solved modulo $p$. –  Arturo Magidin May 25 '11 at 19:15
@Arturo Magidin: I'm looking to characterize all such primes, not to check if the congruence holds for a single one. –  Charles May 25 '11 at 19:29
@Charles: Yes, I'm addressing the "less important to me". If you can figure out which prime moduli it works for, then you've essentially figured out which moduli (composite or prime) it works for, via CRT and Hensel, with only a handful or possible exceptions (the powers of primes that divide $k$). –  Arturo Magidin May 25 '11 at 19:30
For $k = 2$ the answer is given by quadratic reciprocity (en.wikipedia.org/wiki/Quadratic_reciprocity). There are higher-order reciprocity laws but I don't actually know how to state them: they all follow somehow from Artin reciprocity (en.wikipedia.org/wiki/Artin_reciprocity_law). –  Qiaochu Yuan May 25 '11 at 19:31
Not all the solutions, but since $F_p^X$ is cyclic of order $p-1$, i think the equation always has solution when $k$ and $p-1$ are relatively prime.... –  N. S. May 25 '11 at 19:32
show 3 more comments

1 Answer

up vote 4 down vote accepted

If $p|n$, we always have solution.

So assume $p$ does not divide $n$.

In this case, we have a solution to $x^k = n \pmod p$ if and only if $n^{\frac{p-1}{k_p}}\equiv 1 \pmod p$ where $k_p = \gcd(k,p-1)$.

Proof: Choose $u,v$ so that $k_p = (p-1)u + kv$.

If $x^k = n$, then $$n^{\frac{p-1}{k_p}} \equiv x^{(p-1)\frac{k}{k_p}} \equiv 1 \pmod p$$

On the other hand, if $n^{\frac{p-1}{k_p}} \equiv 1 \pmod p$, then $n \equiv x_0^{k_p}$ for some $x_0$. But: $$n\equiv x_0 ^{p_k} = x_0^{(p-1)u + kv} \equiv (x_0^v)^k$$ So $x=x_0^v$ is a solution.

This is a generalization of the theorem that (when $p$ is odd and $(n,p)=1$), $n$ is a square modulo $p$ if and only if $n^{\frac{p-1}2} \equiv 1 \pmod p$

There have been lots of attempts to generalize quadratic reciprocity to other powers, but I don't know much about the results - I don't know if they'd be useful for real computation.

share|improve this answer
add comment

Your Answer


