QN: Solve $8^x \equiv 3 $ mod 43.
I am inspired by the method here: (https://math.stackexchange.com/a/1332788/737799) However there seems to be no solutions in this case.
Firstly convert both sides of the congruence to base-8. I have found that $3^{39} \equiv 8$ mod 43. Then $8^{39x} \equiv 3^{39} \equiv 8$ mod 43.
Then solving $39x \equiv 1$ mod $\phi(43)=42$. There is no solution to this congruence.
However the theorem (also in the link) for the last step states: if 𝑎 is a primitive root modulo 𝑝, then $a^x\equiv a^y $ mod p if and only if $x\equiv y$ mod $\phi(p)$. For this problem 8 is not a primitive root mod 43. What can I do in this case? Thanks in advance!
Best Answer
$\bmod 43\!:\ \left[2^{\large 3x}\equiv 3\right]^{\large 14}\,\overset{\rm Fermat}\Longrightarrow\ 1\equiv 3^{\large 14}\equiv 36\,\Rightarrow\!\Leftarrow$