Solving a congruence of the form $a^x = b \pmod m$ without indices or primitive roots

Question

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!

Answer 1

It is probably quickiest & easiest to calculate the powers of $12$ modulo $25$ .. \begin{eqnarray*} 12,19,3,11,7,9,8,21,2,24 \\ 13,6,22,14,18,16,\color{red}{17} \cdots \end{eqnarray*} So \begin{eqnarray*} 12^{17}=17 \pmod{25}. \end{eqnarray*}

Answer 2

There are several possible answers to your question.

1. 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).
2. What you do works: you continue until you get the same $x$ from both powers: that $x$ will work.
3. 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$!
4. 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.

Answer 3

Prime factorization is not unique under modulus so $a^mb^n \equiv a^kb^j$ should not imply $m =k, n=j$.

You can reduce powers however if the base is relatively prime to the modulus.

$17\equiv 42 \mod 25$ but $6|42$; not $12|42$. $42 = 17 + 1*25$ so the next value that $6$ divides will be $17+ 7*25 = 192$ and $12|192$.

But multiplication is easy than division. So lets figure out what $\frac 1{12} \mod 12$ is.

$2*12 \equiv -1 \mod 25$ so $4*12^2 \equiv 1\mod 25$ so $\frac 1{12}\equiv 48 \equiv 23\equiv -2\mod 25$.

$12^x \equiv 42\mod 25$ so

$12^{x-1} \equiv -84 \mod 25$

$12^{x-2}\equiv -7 \mod 25$

$12^{x-3}\equiv 14 \mod 25$

$12^{x-4}\equiv -28\equiv -3 \mod 25$

$12^{x-5}\equiv 6 \mod 25$

$12^{x-6}\equiv -12\mod 25$

$12^{x-7}\equiv -1\mod 25$

$12^{x-8}\equiv 2\mod 25$

$12^{x-9}\equiv -4\mod 25$

$12^{x-10}\equiv 8\mod 25$

$12^{x-11}\equiv -16\equiv 9\mod 25$

$12^{x-12}\equiv -18\equiv 7\mod 25$

$12^{x-13}\equiv -14\mod 25$

$12^{x-14}\equiv 28\equiv 3\mod 25$

$12^{x-15}\equiv -6\mod 25$

$12^{x-16}\equiv 12\mod 25$

So $x = 17$.

This is way too inefficient to be a useful method.

====

Here's a creative way of doing it:

$17\equiv -8$. Figure $\frac 18\equiv -3$ as $3*8\equiv -1$.

$12\equiv -\frac 12 $ as $2*12\equiv -1$.

$(-\frac 12)^3 = -\frac 18\equiv \frac 1{17}$

So $12^{-3} \equiv 17$

$\phi(25)= 20$ so $12^{20}\equiv 1$ and $12^{20-3}=12^{17}\equiv 17$.

The idea being that in taking powers if you keep your eye out not just of $17$ but for $\pm8$ and $\pm \frac 1{17}=\pm 3$ you will find a relevant value for quicker. In this case $12^2 \equiv -6$ and $12^3\equiv -72\equiv 3$ and $3*17\equiv 1 $ so we are done. By keeping an eye out not just for $17$ but for $8$ and $3$ we caught it in three moves and not $17$.

However noticing $12 \equiv -\frac 12$ we note $2^3 = 8$ so we are done even faster.