Los números primos para que $x^k\equiv n\pmod p$ es solucionable: la versión fija

Question

Fijo $n$$k$, ¿cómo puedo caracterizar los números primos $p$ tal que $x^k\equiv n\pmod p$?

Menos importante para mí: hay una similar caracterización de compuestos de módulos? Asumir la factorización es conocido.

Ejemplo: los números primos para que $x^4\equiv21$ es solucionable son 2, 3, 5, 7, 17, 43, 47, 59, 67, 79, 83, 109, 127, 131, 151, 163, ...; hay una manera más fácil para expresar esta secuencia?

---

Esta es la versión corregida de esta pregunta donde claramente me perdí mi tren de pensamiento, mientras que la publicación.

Answer 1

Si $p|n$, siempre tenemos la solución.

Así que supongamos $p$ no divide $n$.

En este caso, tenemos una solución a $x^k = n \pmod p$ si y sólo si $n^{\frac{p-1}{k_p}}\equiv 1 \pmod p$ donde $k_p = \gcd(k,p-1)$.

Prueba: Elija $u,v$, de modo que $k_p = (p-1)u + kv$.

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

Por otro lado, si $n^{\frac{p-1}{k_p}} \equiv 1 \pmod p$, $n \equiv x_0^{k_p}$ algunos $x_0$. Pero: $$n\equiv x_0 ^{p_k} = x_0^{(p-1)u + kv} \equiv (x_0^v)^k$$ Por lo $x=x_0^v$ es una solución.

Esto es una generalización del teorema de que, cuando se $p$ es impar y $(n,p)=1$), $n$ es una plaza modulo $p$ si y sólo si $n^{\frac{p-1}2} \equiv 1 \pmod p$

Han habido muchos intentos de generalizar la reciprocidad cuadrática a otros poderes, pero no sé mucho acerca de los resultados - no sé si te será de gran utilidad para el cálculo.