1
$\begingroup$

I've read through this answer to get some ideas: Solving a congruence using a primitive root

But my problem is slightly different and it's thrown me off in terms of understanding the logic.

I have $ x^5 \equiv 8\pmod{53}$ , I know 3 is a primitive root mod 53, how can I use this information to find a solution to this congruence?

$\endgroup$
3
  • $\begingroup$ Take "logarithms": $5\operatorname{ind}_3(x)\equiv \operatorname{ind}_3(8)\pmod{52}$ Since $21*5\equiv 1\pmod{52}$. Then $\operatorname{ind}_3(x)=21\cdot \operatorname{ind}_{3}(8)\pmod{52}$. Now, $\operatorname{ind}_3(8)=43$. So $\operatorname{ind}_3(x)\equiv 21\cdot 43\equiv 19\pmod{52}$ $\endgroup$
    – plop
    Dec 6, 2021 at 15:29
  • 1
    $\begingroup$ So, $x\equiv 3^{19}\equiv 34\pmod{53}$. Note that in this computation, what is "hard" to compute is $\operatorname{ind}_3(8)$. $\endgroup$
    – plop
    Dec 6, 2021 at 15:36
  • $\begingroup$ You don't need to use the given primitive root. Since $5 \cdot 21 \equiv 1 \bmod 52$, we have $x \equiv 8^{21} \bmod 53$. $\endgroup$
    – lhf
    Dec 6, 2021 at 18:12

0

Reset to default

You must log in to answer this question.