# Solving a congruence

• Aug 11th 2008, 02:46 PM
o_O
Solving a congruence
I was wondering if there was a 'smart' way to solving a congruence like: $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 $a = 6, 26, 30$ but I could only come up with a brute force way of finding them:

$a^{3} + 1 \equiv 0 \: (\text{mod } 31)$
$a^{3} + (1 + 31k) = 0 \quad k \in \mathbb{Z}^{+}$

$(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:
$a = \sqrt[3]{1 + 31k}$
$a^{3} = 1 + 31k$
$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 $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?
• Aug 11th 2008, 03:25 PM
NonCommAlg
Quote:

Originally Posted by o_O
I was wondering if there was a 'smart' way to solving a congruence like: $a^{3} \equiv -1 \: (\text{mod } 31)$ .

$a^3+1=(a+1)(a^2-a+1) \equiv 0 \mod 31.$ since 31 is prime, we'll get $a \equiv -1 \equiv 30 \mod 31,$ which is our first solution, or $a^2 -a+1 \equiv 0 \mod 31. \ \ \ (1)$

now (1) is equivalent to $(2a-1)^2 + 3 \equiv 0 \mod 31,$ which is equivalent to $9(2a-1)^2 - 4 \equiv 0 \mod 31,$ which is equivalent to $(6a-5)(6a-1) \equiv 0 \mod 31.$

if $6a \equiv 5 \mod 31,$ then multiplying both sides by $-5$ gives us $a \equiv -25 \equiv 6 \mod 31,$ and if $6a \equiv 1 \mod 31,$ then $a \equiv -5 \equiv 26 \mod 31. \ \ \ \square$
• Aug 15th 2008, 06:51 AM
whipflip15
If you know a primitive root mod 31 it is fairly simple to find all elements of order 6. (There are 8 primitive roots)
• Aug 15th 2008, 09:10 AM
ThePerfectHacker
Quote:

Originally Posted by whipflip15
If you know a primitive root mod 31 it is fairly simple to find all elements of order 6. (There are 8 primitive roots)

The problem is finding the primitive root.
I find the solution by NonCommAlg to be the best approach.
But it is not so bad because once the primitive root r is found the index of -1 is then $r^{(p-1)/2}$.
Thus, knowledge of the primitive root will basically solve the problem immediately.