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

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 .

• I'd just write $x\equiv 0\pmod 2$ rather than $x\equiv 0,2\pmod {4}$. But it's the same thing, and yes, so far you are correct. – Thomas Andrews Jun 24 '15 at 23:49
• For modulo $5$, there are two possibilities, $x\equiv 2$ and $x\equiv 3$. So you need to consider two separate sets of congruences. (i) $x\equiv 0\pmod{2}$, $x\equiv 0\pmod{3}$, $x\equiv 2\pmod{5}$ and (ii) $x\equiv 0\pmod{2}$, $x\equiv 0\pmod{3}$, $x\equiv 3\pmod{5}$. Solve each system separately. – André Nicolas Jun 24 '15 at 23:55
• thanks for both answers. after I get the solutions to both systems seperately. what are the final answers? both answers i got ? or do i need to combine them somehow? – user2993422 Jun 25 '15 at 0:02
• Look at it this way. $60$ has one square factor. So essentially you can reduce the problem to solving this congruence $mod 30$ . can you now get the two solutions mod 30 ? So really there will be 4 solutions mod 60. If you think about this, it should help you gain better intuition. supinf has already written an answer. – Shailesh Jun 25 '15 at 0:09
• Im trying to finish my solution. didn't understand why 60 has one square root and how this fact let me reduce to 30? thanks for the help! another question I have is when solving these systems with the chinese reminder theorm, do I need to do something different because of a = 0? because the final result is given by $x = \sum_{i=1}^n {M_i*M'_i*a_i}$ and two of my $a_i$ are zero.. – user2993422 Jun 25 '15 at 0:16

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

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.