Primero observemos que si $x$ es una solución, entonces $x$ es primo con $p$ (si tuviesen un divisor común $d$, éste también sería divisor común de $a$ y $p$). Es decir, $x,p$ coprimos es condición necesaria para una solución.
Tomemos pues una de las $\phi(p-1)$ raíces primitivas de $p$ y llamémosla $g$ (vamos a aplicar la propiedad logarítmica de las potencias de g y el hecho de que éstas generan cualquier primo con p).
Como $a$ y $x$ son primos con $p$, entonces existen exponentes $i,j$ tales que $g^i\equiv a(\mod p)$ y $g^j\equiv x(\mod p)$. Esto reduce la congruencia que estamos analizando a $g^{jn}\equiv{g^i}(\mod p)$.
Pero, por la propiedad logarítmica de las potencias de una raíz primitiva (módulo un primo), es posible reducirla a la congruencia lineal $nj\equiv i(\mod{p-1})$. Es decir, la ecuación congruencial de potencias se reduce a encontrar los exponentes $i,j$ que generan $x,a$, vía una raíz primitiva $g$.
Ahora solamente tenemos que traer a presencia un teorema conocido sobre congruencias lineales: $nj\equiv i(\mod{p-1})$ tiene solución si y sólo si el MCD(n,p-1) --llamémosle $G$-- divide a $i$; y, en ese caso, el número de soluciones es $G$. Entonces, hay $G$ soluciones si $G$ divide a $i$ y ninguna en cualquier otro caso.
Pero, si $G$ es divisor de $i$, entonces $i(p-1)/G$ es múltiplo de $p-1$ (buscando el antilogaritmo y la traducción de la condición sobre $i$ a una condición sobre $a$). Así que (módulo p) $1\equiv{(g^{p-1})^{i/G}=g^{i(p-1)/G}\equiv{a^{(p-1)/G}}$. En resumen, la condición para G soluciones es $a^{(p-1)/G}}\equiv 1(\mod p)$.
Por otro lado, si $G$ no es divisor de $i$ entonces $i(p-1)/G$ no es múltiplo de $p-1$ y, por tanto, $a^{(p-1)/G}}\equiv{g^{i(p-1)/G}}$ no puede ser congruente con 1 respecto al módulo p (pues $p-1$ es el mínimo exponente para el que $g^e$ es equiresidual con el 1, por definición de raíz primitiva). Entonces, la condición para ninguna solución es que $a^{(p-1)/G}$ no sea congruente con el 1 respecto al módulo $p$.
