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

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

• 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. – André Nicolas Dec 14 '15 at 18:27
• For question 1 just compute all the different squares, there are only 13 of them. – Justpassingby Dec 14 '15 at 18:30
• $x^2\equiv -3\equiv 36\pmod{13}\iff x\equiv \pm 6\pmod{13}$. – user236182 Dec 14 '15 at 18:34
• @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? – GRS Dec 14 '15 at 19:14
• @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? – GRS Dec 14 '15 at 19:21

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