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

Question

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!

Answer 1

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

Answer 2

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$