1
$\begingroup$

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 .

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Jun 24 '15 at 23:49
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Jun 24 '15 at 23:55
  • $\begingroup$ 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? $\endgroup$ – user2993422 Jun 25 '15 at 0:02
  • $\begingroup$ 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. $\endgroup$ – Shailesh Jun 25 '15 at 0:09
  • $\begingroup$ 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.. $\endgroup$ – user2993422 Jun 25 '15 at 0:16
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

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