Find all four solutions to $x^2 \equiv 133 \pmod {143}$

Question

My question pertains to the below problem. The problem is in a book, but I'm trying break it down and really understand all of the steps.

Find all four solutions $x^2\equiv 133 \pmod {143}$
Here's what I have so far:

1) \begin{align}x^2 \equiv 133 \pmod {11}\\ x^2 \equiv 1 \pmod {11}\\ x \equiv \pm 1 \pmod {11} \end{align}

2) \begin{align}x^2 \equiv 133 \pmod {13}\\ x^2 \equiv 3 \pmod {13}\\ x \equiv \pm 4 \pmod {13}\end{align}

How does $x^2 \equiv 3 \pmod {13}$ turn into $x \equiv \pm 4 \pmod {13}$ ?

Answer 1

How does $x^2 \equiv 3 (mod 13)$ turn into $x \equiv \pm 5 (mod 13)$ ?

It doesn't, it gives $x \equiv \pm 4 (mod 13)$.

Answer 2

You could benefit from some preamble before you jump into the separate modular solutions.

Since $143=11\cdot 13$, with $11$ and $13$ prime, we can find the solutions, if any, by considering the problem of $x^2\equiv 133 \bmod 143$ to each prime modulus and then combining those results with the Chinese Remainder theorem.

So then ( as you already have):

$ \begin{align} x^2 &\equiv 133 \pmod {11}\\ x^2 &\equiv 1 \pmod {11}\\ x &\equiv \pm 1 \pmod {11} \end{align}$ $\qquad \qquad \qquad$ $\begin{align} x^2 &\equiv 133 \pmod {13}\\ x^2 \equiv 3 &\equiv 16 \pmod {13}\\ x &\equiv \pm 4 \pmod {13}\end{align} $

Finding a number which squares to a given value under a particular modulus may not be simple. For small modulus values like this it's easy enough to spot squares just by adding the modulus to look for natural squares though.

Given two values for each of the contributing prime moduluses, the Chinese remainder theorem will give you four answers in range, but note that two of them will simply be the negation of the other two. So we can pick $x\equiv 1 \bmod 11$ for example and combine with both the answers on the $\bmod 13$ side:

As a preliminary, $11^{-1}\equiv (-2)^{-1} \equiv -7\equiv 6 \bmod 13$

$\left . \begin{array}{r} x\equiv 1 \bmod 11 \\ x\equiv 4 \bmod 13 \end{array} \right\}\space 1+11k \equiv 4 \implies k\equiv 11^{-1}\cdot 3 \equiv 6\cdot 3 \equiv 5 \bmod 13 \\\implies x\equiv 1+11\cdot 5 \equiv 56 \bmod 143$

$\left . \begin{array}{r} x\equiv 1 \bmod 11 \\ x\equiv -4\equiv 9 \bmod 13 \end{array} \right\}\space 1+11k \equiv 9 \implies k\equiv 11^{-1}\cdot 8 \equiv 6\cdot 8 \equiv 9 \bmod 13 \\\implies x\equiv 1+11\cdot 9 \equiv 100 \bmod 143$

Then taking $x\equiv -1\bmod 11$ will give the negation of these values, $-56\equiv 87$ and $-100\equiv 43\bmod 143$ (which you can work through to check if you are not sure about this) so $x\equiv \{43,56,87,100\} \bmod 143$