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

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!

• – lab bhattacharjee May 7 at 7:36
• @labbhattacharjee But we are trying to find $a$ (as described in that link). So the discrete logarithm is answering the wrong question. – Arthur May 7 at 7:44
• @Arthur, Please find my answer below – lab bhattacharjee May 7 at 8:23

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

• 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? – Kami May 7 at 7:46
• @Kami You have $a \mod 73=8$, which is a totally different answer to what the order $a$ (8) has mod 73. – Ingix May 7 at 7:57
• The order of 64 (mod 73) would be 3 I believe. – Kami May 7 at 8:02

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