2
$\begingroup$

I want to find solutions to the equation $x^3 + 2x - 3 \equiv 0 (mod 45)$. I have already found solutions to $x^3 + 2x - 3 \equiv 0 (mod 5)$ and $x^3 + 2x - 3 \equiv 0 (mod 9)$, simply by brute force. Respectively, $x = 1, 3 (mod 5)$ and $x = 1, 2, 6 (mod 9)$ are zeros of the equations. However, the brute force method doesn't seem like a wise way to approach this problem for $mod 45$.

I'm aware of the CRT, I'm just unsure how to apply that here if applicable. This is for homework, so I'd prefer a hint or something to point me in the right direction rather than an answer.

$\endgroup$
2
$\begingroup$

Using CRT we can work out the general solution of $\,x\equiv a\pmod 9,\ x\equiv b\pmod 5,\,$ then specialize it for each pair $\,a,b.$

${\rm mod}\ 9\!:\ x\equiv a\,\Rightarrow\,x = a+9n.\,$ $\,{\rm mod}\ 5\!:\ b\equiv x\equiv a+9n\equiv a-n\,\Rightarrow\,n\equiv a-b\,$ therefore $\, n = a-b+5k,\,$ so $\,x = a+9n = a+9(a-b + 5n) = 10a-9b + 45k.\,$

For example if $\,x\equiv a\equiv 2\pmod 9,\,$ and $\,x\equiv b\equiv 3\pmod 5\,$ then from the above we deduce $\,x\equiv 10a-9b\equiv 10(2)-9(3)\equiv -7\equiv 38\pmod{45}.\,$

Computing $\,10a-9b\pmod{45}\,$ for all other pairs $a,b$ yields all $6$ solutions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.