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, 2020 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, 2020 at 2:17

2 Answers 2

Reset to default
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, 2020 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .