I was wondering if there was a 'smart' way to solving a congruence like: $\displaystyle a^{3} \equiv -1 \: (\text{mod } 31)$ . This is a sub-problem to an overall problem but I think I'm on the right track.Things to note: there are exactly 3 solutions and all integers with ordre six satisfies the congruence (as a consequence of earlier work).

I know the solutions are $\displaystyle a = 6, 26, 30$ but I could only come up with a brute force way of finding them:

$\displaystyle a^{3} + 1 \equiv 0 \: (\text{mod } 31)$

$\displaystyle a^{3} + (1 + 31k) = 0 \quad k \in \mathbb{Z}^{+}$

$\displaystyle (a+\sqrt[3]{1 + 31k})(a^2 + a\sqrt[3]{1+31k} + (1 + 31k)^{\frac{2}{3}}) = 0$

To attain integer solutions to a, we see that:

$\displaystyle a = \sqrt[3]{1 + 31k}$

$\displaystyle a^{3} = 1 + 31k$

$\displaystyle k = \frac{a^{3}-1}{31}$

Now it's a matter of testing values of a from 1 to 31 until k is an integer. Luckily, it doesn't take long to find a = 6 works which implies that $\displaystyle 6^{5} \equiv 26$ works as well.

This is a rather inelegant way of doing it so is there a better way of doing this or would this suffice?