Congruence with powers and primitive roots

Question

Determine all the solutions of the congruence
$x^{85} ≡ 25 \pmod{31}$
using index function in base $3$ module $31$.
It is clear to me that $3$ is primitive root module $31$, but how do I use this information in the solution?

Answer 1

$3^22^2\equiv5 $ and $2^2\equiv(-3)^3$, so $3^5\equiv -5$, and $3^{10}\equiv25\pmod{31}$.

Let $x=3^y$, so you're asking for $(3^y)^{85}\equiv3^{10}\pmod{31},$ which means $85y\equiv10\pmod{30}$

$\iff 17y\equiv2\bmod6\iff y\equiv4\bmod6\iff y\equiv 4, 10, 16, 22, $ or $28\pmod{30}$.

Now do you see how $x^{85}\equiv25\pmod{31}$ can be solved using indices with base $3$?

Answer 2

Using Discrete logarithm with respect to base $3$,

$85\cdot$ind$_3x\equiv2\cdot$ind$_35\pmod{30}$

As $85\equiv-5\pmod{30},$

$-5\cdot$ind$_3x\equiv2\cdot$ind$_35\pmod{30}\ \ \ \ (1)$

$3^3\equiv-4,3^5\equiv9\cdot(-4)\equiv-5\pmod{31}$

As $3$ is a primitive root $\pmod{31}, -1\equiv3^{30/2}\pmod{31}$

$\implies5\equiv3^{15}\cdot3^5\pmod{31}$

By $(1), -5\cdot$ind$_3x\equiv2\cdot20\pmod{30}\equiv-20$

Dividing through out by $-5$

ind$_3x\equiv4\pmod6$

$\implies x\equiv3^{4+6k}\pmod{31}$ where $0\le4+6k\le30\iff0\le k\le4$