solving cubic congruences

• Sep 27th 2010, 02:01 AM
FGT12
solving cubic congruences
Find all the solutions of $\displaystyle x^3+3x-8\equiv 0mod(33)$

I can only see
$\displaystyle x^3+3x-8\equiv 0 mod(3)$ and $\displaystyle x^3+3x-8 \equiv 0 mod(11)$

however i cannot seem to condense these further and mod 11 by inspection does seem right
• Sep 27th 2010, 04:07 AM
undefined
Quote:

Originally Posted by FGT12
Find all the solutions of $\displaystyle x^3+3x-8\equiv 0mod(33)$

I can only see
$\displaystyle x^3+3x-8\equiv 0 mod(3)$ and $\displaystyle x^3+3x-8 \equiv 0 mod(11)$

however i cannot seem to condense these further and mod 11 by inspection does seem right

well i'll be the one who brings up thoughtless brute force, someone else could discuss more intelligently.

easiest to just show you a screenshot from pari/gp. as you can see i solved it in two ways and the answers match.
• Sep 27th 2010, 06:18 AM
melese
Quote:

Originally Posted by FGT12
Find all the solutions of $\displaystyle x^3+3x-8\equiv 0mod(33)$

I can only see
$\displaystyle x^3+3x-8\equiv 0 mod(3)$ and $\displaystyle x^3+3x-8 \equiv 0 mod(11)$

however i cannot seem to condense these further and mod 11 by inspection does seem right

This is my attempt.
For the first congruence: $\displaystyle x^3\equiv x\bmod3$ by Fermat's Theorem, and replacing coefficients modulo 3 gives $\displaystyle x^3+3x-8\equiv x-8\equiv x+1\bmod3$ or $\displaystyle x\equiv-1\bmod3$.
Similarly, we replace coefficients modulo 11 and hence $\displaystyle x^3+3x-8\equiv 12x^3+3x+3\equiv0\bmod11$. Dividing by 3 gives $\displaystyle 4x^3+x+1\equiv0\bmod11$. Here by simply checking integers $\displaystyle 0\le x\le10$ gives $\displaystyle x\equiv5, 8, 9\bmod11$.

Now we have to consider three systems: $\displaystyle x\equiv-1\bmod 3$ and $\displaystyle x\equiv5\bmod11$; $\displaystyle x\equiv-1\bmod3$ and $\displaystyle x\equiv8\bmod11$; $\displaystyle x\equiv-1\bmod3$ and $\displaystyle x\equiv9\bmod11$. By inspection, the solutions are $\displaystyle x\equiv 5, 8, 20\bmod 33$ .