# Solve congruence for unknown power

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!

• $3$ is a primitive root mod $43$ Sep 27, 2020 at 1:54
• See here for one simple way to compute solutions when they exist (Shanls's baby-giant step). Sep 27, 2020 at 2:17

$$\bmod 43\!:\ \left[2^{\large 3x}\equiv 3\right]^{\large 14}\,\overset{\rm Fermat}\Longrightarrow\ 1\equiv 3^{\large 14}\equiv 36\,\Rightarrow\!\Leftarrow$$
• i.e. raise both sides of the congruence to power $14,\,$ using $\,2^{\large 42}\equiv 0\,$ by Fermat. Sep 27, 2020 at 2:08
$$8^{x}\equiv 8, 21, -4, 11, 2, 16, -1,-8, -21, 4, -11, -2, -16, 1, 8...\mod 43$$ as $$x=1, 2,...$$
So $$8^x$$ is never $$3\mod 43$$.