0
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ $3$ is a primitive root mod $43$ $\endgroup$ – J. W. Tanner Sep 27 '20 at 1:54
  • $\begingroup$ See here for one simple way to compute solutions when they exist (Shanls's baby-giant step). $\endgroup$ – Bill Dubuque Sep 27 '20 at 2:17
1
$\begingroup$

$\bmod 43\!:\ \left[2^{\large 3x}\equiv 3\right]^{\large 14}\,\overset{\rm Fermat}\Longrightarrow\ 1\equiv 3^{\large 14}\equiv 36\,\Rightarrow\!\Leftarrow$

$\endgroup$
1
  • $\begingroup$ i.e. raise both sides of the congruence to power $14,\, $ using $\,2^{\large 42}\equiv 0\,$ by Fermat. $\endgroup$ – Bill Dubuque Sep 27 '20 at 2:08
1
$\begingroup$

We have

$$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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.