Solve $x^2\equiv -3\pmod {\!91}$ by CRT lifting roots $\!\bmod 13\ \&\ 7$

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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.