<s>[INST] Solving a congruence of the form $a^x = b \pmod m$ without indices or primitive roots Consider $9^x\equiv 7 \mod 19$. So $9^x\equiv 26 \equiv 45$, $9^{x-1} \equiv 5 \equiv 24 \equiv 43 \equiv 62 \equiv 81$, so $x=3$, and $19 \mid 722$.
But what I really want to solve is $12^x\equiv 17 \mod 25$. Using the same method, $$2^{2x}\cdot3^x \equiv 17 \equiv 42,$$ $$ 2^{2x- 1}3^{x-1}\equiv 7 \equiv 32,$$ $$2^{2x-6}3^{x-1}\equiv 1\equiv 26, $$ $$ 2^{2x-7}3^{x-1}\equiv 13 \equiv38,$$ $$ 2^{2x-8}3^{x-1} \equiv 19\equiv 44, $$ $$2^{2x-10}3^{x-1}\equiv 11 \equiv 36 \equiv (2^2)(3^2),$$ so $2x-10=2$, hence $x=6$, and $x-1=2$, so $x=3$. 
Why doesn't this work? Is it because $12$ is not the power of a prime and $9$ is? Any help is appreciated! 
 [/INST] There are several possible answers to your question. 


*

*You don't do the "same thing", since you are breaking the left hand side in two powers. In fact, it is not true that $a^xb^y\equiv a^zb^t \pmod n$ implies that $x=z$ and $y=t$, even not modulo the respective order $\pmod n$, or even if they are both "primes" (which has no meaning modulo n) or "coprimes" (again). 

*What you do works: you continue until you get the same $x$ from both powers: that $x$ will work. 

*Why do you repeated 6 times the procedure? In the third step you already got 
$$2^{2x−6}3^{x−1}\equiv 1\equiv 2^03^0$$
so $2x-6=0$ and $x-1=0$, hence $x=3$ and $x=1$! 

*What you do it is not really well defined. For example you could change $9$ in the first case to $9=28=2^27$, and try it again. In fact $2^{2x}7^x\equiv 7$, so $2x=0$ and $x=1$!!! Or you can change $12$ in the second case by $12=37$, which is prime, and do the same procedure. 

</s>