4
$\begingroup$

Question 1) Solve $$x^2\equiv -3\pmod {13}$$

I see that $x^2+3=13n$. I don't really know what to do? Any hints?

The solution should be $$x\equiv \pm 6 \pmod {13}$$

Question 2) $\ $ [note $\bmod 7\!:\ x^2\equiv -3\equiv 4\iff x\equiv \pm 2.\,$ Here we lift to $\!\!\pmod{\!91}\ $ -Bill]

Given $x\equiv \pm 6 \pmod {13}$ and $x\equiv \pm 2 \pmod {7}$ find solutions $\pmod {91}$. I see that $91=13 \times 7$, does it mean I have to use chinese remainder theorem on 4 equations? If,so $x=6\times 13\times 7 \times 7\times (13\times 7 \times 7)^{-1}...$

$\endgroup$
  • 1
    $\begingroup$ You do have to use the CRT on $4$ systems of congruences. Luckily much of the work can be recycled, and the answers come in two $\pm$ pairs. $\endgroup$ – André Nicolas Dec 14 '15 at 18:27
  • 1
    $\begingroup$ For question 1 just compute all the different squares, there are only 13 of them. $\endgroup$ – Justpassingby Dec 14 '15 at 18:30
  • 2
    $\begingroup$ $x^2\equiv -3\equiv 36\pmod{13}\iff x\equiv \pm 6\pmod{13}$. $\endgroup$ – user236182 Dec 14 '15 at 18:34
  • $\begingroup$ @AndréNicolas When I apply CTR I seem to always need to find the inverse of 0, because no matter which other 3 I pick, since I'm always mulitpying $7$ and $13$ I always get 0 mod 13 and 0 mod 7? $\endgroup$ – GRS Dec 14 '15 at 19:14
  • $\begingroup$ @AndréNicolas I know that they should be coptime, which they are not since 7 is clearly not coprime with itself. Same for 13. But How can I work around it? $\endgroup$ – GRS Dec 14 '15 at 19:21
2
$\begingroup$
  1. Just try all candidates $0,1,2,3,4,5,6$. You can stop at $6$ because $(13-x)^2\equiv x^2$. This will also give you a second solution if you find one.
$\endgroup$
1
$\begingroup$

The numbers are small, and one could find the answers without the full CRT machinery. But we will go ahead and use a "general" procedure.

The idea is that to solve $x\equiv a\pmod{7}$, $x\equiv b\pmod{13}$, you use $$x\equiv (C)(13)(a)+(D)(7)(b)\mod{91},$$ where $C$ is the inverse of $13$ modulo $7$ and $D$ is the inverse of $7$ modulo $13$. We can see I think easily that $C=-1$ and $D=2$ will work, so we get $$x\equiv -13a+14b\pmod{91}.\tag{1}$$ Now let us for example take $a=-2$ and $b=6$, one of your $4$ possibilities. That gives $x\equiv 110\equiv 19\pmod{91}$.

$\endgroup$
  • $\begingroup$ Thank you very much. My mistake was that I was considering all 4 of them at the same time, as opposed to only consider 2, but with 4 cases. $\endgroup$ – GRS Dec 14 '15 at 19:43
  • $\begingroup$ You are welcome. A favour please, you had accepted another answer to another part. I felt uncomfortable answering. The only reason I did is that comments are awkward if they are of any length. It would make me feel better if the accept reverted to the previous one. $\endgroup$ – André Nicolas Dec 14 '15 at 20:30
  • $\begingroup$ Nicolas I was reading this over today and I noticed I didn't change the answer, as you requested I changed it back. $\endgroup$ – GRS Dec 16 '15 at 23:52
1
$\begingroup$

For Question 2), you can use the Chinese Remainder Theorem on the one equation $$ 13x+7y=1\tag{1} $$ Using the Extended Euclidean Algorithm, an implementation of which is in this answer, compute $$ \begin{array}{r} &&1&1&6\\\hline 1&0&1&-1&7\\ 0&1&-1&2&-13\\ 13&7&6&1&0 \end{array}\tag{2} $$ that is, $$ 13(-1)+7(2)=1\tag{3} $$ From $(3)$, we can get $$ \begin{align} 14&\equiv1\pmod{13}\\ 14&\equiv0\pmod{7} \end{align}\tag{4} $$ and $$ \begin{align} -13&\equiv0\pmod{13}\\ -13&\equiv1\pmod{7} \end{align}\tag{5} $$ Now adding $6$ times $(4)$ to $2$ times $(5)$, we get $$ \begin{align} 58&\equiv6\pmod{13}\\ 58&\equiv2\pmod{7} \end{align}\tag{6} $$ Adding other multiples of $(4)$ and $(5)$, we can get the other answers you are looking for.

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