solve $x^2 \equiv 24 \pmod {60}$

Question

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 .

Answer 1

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$.

Answer 2

So far you are correct. Note that you have $x \equiv 0 \mod 3$ and $x \equiv 0 \mod 2$, this gives you $x \equiv 0 \mod 6$. At this time you could also try every possibility for $0 \leq x < 60$, which satisfies this and which have the remainder $2$ or $3$ $\mod 5$. these numbers are: $12,18,42,28$. Check those numbers, if they really give you a solution to your equation.