0
$\begingroup$

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}$ ?

$\endgroup$
  • $\begingroup$ $3\equiv 16 \bmod 13$... $\endgroup$ – Joffan Oct 21 '17 at 20:31
  • $\begingroup$ Where did the 16 come from? $\endgroup$ – hnewbie Oct 21 '17 at 20:32
  • $\begingroup$ Any two numbers which differ by a multiple of $13$ are equivalent modulo $13$. $\endgroup$ – Joffan Oct 21 '17 at 20:33
  • $\begingroup$ ok. understood. so do I $\sqrt 16$ to get $\pm 4$ or is this a completely different answer? $\endgroup$ – hnewbie Oct 21 '17 at 20:37
  • $\begingroup$ That's all you need. You already know that $(\pm 4)^2=16$, to put it the other way round. $\endgroup$ – Joffan Oct 21 '17 at 20:40
1
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ well how does $x^2 \equiv 3 (mod13)$ turn into $x \equiv \pm 4 (mod13)$ $\endgroup$ – hnewbie Oct 21 '17 at 20:27
  • $\begingroup$ Just check the six values $x=1,2,3,4,5,6$ to see if anyone of them gives $x^2 \equiv 3 (mod 13)$. $\endgroup$ – Donald Splutterwit Oct 21 '17 at 20:30
  • $\begingroup$ is there a reason just six values? why not 39 values? $\endgroup$ – hnewbie Oct 21 '17 at 20:33
  • $\begingroup$ $7 \equiv -6 (mod13)$ so they will have the same square modulo $13$. Similarly $8 \equiv -5 (mod13)$ etc ... so we only need to try half the values. $\endgroup$ – Donald Splutterwit Oct 21 '17 at 20:36
  • $\begingroup$ why the -6 and -5? I get that when you add 7+6 = 13 and 8+5 = 13, but why replace 3 with the negative numbers? $\endgroup$ – hnewbie Oct 21 '17 at 20:48

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.