Uso de raíces primitivas para resolver congruencias.

Question

Pregunta. Resuelva $7x^5 = 3 \bmod 19$ utilizando raíces primitivas.

Conozco el procedimiento para solucionarlo. Multiplicamos por la inversa de $7\bmod 19$ demuestre que $2$ es una raíz primitiva $\bmod 19$ y luego escribir todo en términos de potencias de $2$ . De este modo, obtenemos $$2^{5i}\equiv 2^7\bmod 19\Rightarrow 5i\equiv 7\bmod 18\Rightarrow i\equiv 5\bmod 18.$$ Entonces, la respuesta es $2^5\equiv 13\bmod 19$ . Sin embargo, acabo de darme cuenta de que en realidad no tengo ni idea de por qué debemos trabajar en modulo $18$ o, más en general, $\bmod\varphi(n)$ para elaborar el $i$ . Sé que hay alguna conexión entre $\Bbb Z/19\Bbb Z$ y $U(19)$ pero no puedo precisarlo.

Agradeceríamos cualquier aclaración al respecto. Gracias de antemano.

Answer 1

Si p es un número primo y $(a,p)=1$ entonces tenemos: $$ a^{p-1}\equiv1 (mod p)$$ $$therefor: a^{18}\equiv1 (mod 19)$$ $$7x^5\equiv3 \Longrightarrow 77x^5\equiv33 (mod 19)\Longrightarrow$$ $$x^5\equiv14(mod19) \Longrightarrow (x^5)^{11}\equiv(14)^{11}(mod19)$$ $$(x^{18})^3.x\equiv14^{11} (mod19)$$ $$x\equiv13\ (mod19)$$