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.

  • 1
    $\begingroup$ 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$. $\endgroup$ – Arturo Magidin May 25 '11 at 19:15
  • $\begingroup$ @Arturo Magidin: I'm looking to characterize all such primes, not to check if the congruence holds for a single one. $\endgroup$ – Charles May 25 '11 at 19:29
  • 1
    $\begingroup$ @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$). $\endgroup$ – Arturo Magidin May 25 '11 at 19:30
  • 2
    $\begingroup$ 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). $\endgroup$ – Qiaochu Yuan May 25 '11 at 19:31
  • 1
    $\begingroup$ 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.... $\endgroup$ – N. S. May 25 '11 at 19:32

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.


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.