0
$\begingroup$

I'm working through some problems with primitive roots and needed some help on this problem, specifically how do we use the fact that $5$ is a primitive root to solve this?

Given: $5$ is a primitive root of $73$, find all solutions to $x^3 - 1 ≡ 0$ (mod $73$).

Thanks!

$\endgroup$
2
$\begingroup$

From the fact that $5$ is a primitive root, we know that $5$ has order $72$ in the multiplicative group. Let $a = 5^{24}$. Can you tell me the order of $a$ modulo $73$? What about the order of $a^2$, what about the order of $a^3$?

$\endgroup$
  • $\begingroup$ I'm getting order a mod 73 as 8 and the order of a^2 and a^3 as 9. Am I on the right track? $\endgroup$ – Kami May 7 at 7:46
  • $\begingroup$ @Kami You have $a \mod 73=8$, which is a totally different answer to what the order $a$ (8) has mod 73. $\endgroup$ – Ingix May 7 at 7:57
  • $\begingroup$ The order of 64 (mod 73) would be 3 I believe. $\endgroup$ – Kami May 7 at 8:02
0
$\begingroup$

Using Discrete Logarithm

$3$ind$_5x\equiv0\pmod{\phi(73)}$

$\iff$ind$_5x\equiv0\pmod{24}\implies$ind$_5x=24k,x\equiv5^{24k}\pmod{73}$

But $0\le$ind$_5x<72\implies0\le k<3$

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