Solving a depressed cubic polynomial in modulus.

Question

Is there a general technique for solving depressed cubic modulus polynomial? For instance, how would you solve the equation $a^3 + a + 21 = 0 \pmod{43}$?. My attempts eventually ended up with solving $x^3 = k \pmod{43}$. In other words, what is the technique for solving the second equation without guessing and checking?

Answer 1

You can use the Cardano method. Set up $a=u+v$, then

$(u^3+3uv(u+v)+v^3)+(u+v)+21\equiv0.$

Then setting $uv\equiv-3^{-1}\equiv14$

to cancel out the $u+v$ terms gives

$u^3+v^3+21=0$

$u^3+(14u^{-1})^3+21=0$

$(u^3)^2+21u^3+35\equiv0.$

Note that $14^3=2744\equiv35$. Then we have a quadratic equation for $u^3$, which is solved by the quadratic formula:

$u^3\equiv(-21\pm\sqrt{21^2-4×35})(2^{-1})$

in which the discriminant turns out $\equiv0$! We therefore have a double root for $u$, which then implies a double root for $a$. Thus $u^3\equiv(-21)2^{-1}\equiv11$.

We then must find a cube root of $11\bmod43$. If such a root exists for $u$, then we must have $11^{42/3}\equiv11^{14}\equiv1$, so $u^3\equiv11\equiv11^{15}$ and we have the candidate root

$u\equiv11^5\equiv16.$

This residue cubed does give $4096\equiv11\bmod 43$. Thus $u\equiv16,v\equiv14×16^{-1}\equiv17$, and we have a root $a\equiv33$.

Either this is the double root for $a$ or the other root must be the double root. With all roots summing to zero counting the double root twice, we must therefore have one of the root possibilities

$5,5,33, or$

$20,33,33.$

We check that $a\equiv5$ fails whereas $a\equiv20$ and $a\equiv33$ both hit, so the latter is indicated and we end with $20$ and $33$ as the distinct solutions.