I need to solve $x^2 \equiv 24 \pmod {60}$
My first question which confuses me a lot –
isn't a (24 here) has to be coprime to n (60)???
most of the theorems requests that.
what i tried –
$ 60 = 2^2 * 3 * 5$
So I need to solve $x^2 \equiv 24$ modulo each one of $2^2, 3, 5$ so i get –
$x^2 \equiv 0 \pmod 4$
$x^2 \equiv 0 \pmod 3$
$x^2 \equiv 4 \pmod 5$
so if Im correct I have 5 equations –
$x \equiv 0 \pmod 4$
$x \equiv 2 \pmod 4$
$x \equiv 0 \pmod 3$
$x \equiv 2 \pmod 5$
$x \equiv 3 \pmod 5$
Now my questions are – am I correct until now.
and second is, how to solve this? I know to use the Chinese reminder theorem
but what confuses me here is that I have more then one equation modulo the same number.
any help will be appreciated .
Best Answer
You were correct.
$$x^2\equiv 24\pmod{\! 60}\iff \begin{cases}x^2\equiv 24\equiv 0\pmod{\! 3}\\ x^2\equiv 24\equiv 0\pmod{\! 4}\\ x^2\equiv 24\equiv 4\pmod{\! 5}\end{cases}$$
$$\iff \begin{cases}x\equiv 0\pmod{\! 3}\\ x\equiv 0\pmod{\! 2}\\ x\equiv \pm 2\pmod{\! 5}\end{cases}$$
If and only if at least one of the two cases holds:
$1)$ $\ x\equiv 0\pmod{\! 6},\ x\equiv 2\pmod{\! 5}$
$2)$ $\ x\equiv 0\pmod{\! 6},\ x\equiv -2\pmod{\! 5}$
You can use Chinese Remainder theorem as follows (when I create new variables, they're integers):
$$x\equiv 0\pmod{\! 6}\iff x=6k$$
$$1)\ \ \ x\equiv 2\pmod{\! 5}\iff \color{#00F}6k\equiv \color{#00F}1k\equiv 2\pmod{\! 5}$$
$x=6(5n+2)=30n+12$.
$$2)\ \ \ x\equiv 3\pmod{\! 5}\iff \color{#00F}6k\equiv \color{#00F}1k\equiv 3\pmod{\! 5}$$
$x=6(5n+3)=30n+18$.
Another way you can use CRT (which is basically just finding an $x$ that works in $[0,30)$):
$1)\ \ \ (x\equiv 0\equiv 12\pmod{\! 6}$ and $x\equiv 2\equiv 12\pmod{\! 5})\iff x\equiv 12\pmod{\! 6\cdot 5},$
because (since $(6,5)=1$):
$$6,5\mid x-12\iff 6\cdot 5\mid x-12$$
Using this, in case $2)$ in the same way you find that $18$ works ($18\equiv 0\pmod{\! 6}$ and $18\equiv 3\pmod{\! 5}$).
So you have the congruence holds iff $x=30m\pm 12$ for some $m\in\Bbb Z$.