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 ϕ(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 gi≡a(modp) y gj≡x(modp). Esto reduce la congruencia que estamos analizando a gjn≡gi(modp).
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≡i(modp−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≡i(modp−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≡(gp−1)i/G=gi(p−1)/G≡a(p−1)/G$.Enresumen,lacondiciónparaGsolucioneses$a(p−1)/G≡1(modp).
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 ge 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.