Cryptography: Solve $x^2 \equiv 331 \pmod{385}$ using modular arithmetic

Question

How can I find (3) congruence equations to solve

$$x^2\equiv331\pmod{385}$$

using Legendre and Jacobi Symbols and use the Chinese Remainder Theorem to combine the solutions to those equations to produce the solutions to $x^2\equiv331\pmod{385}$

Solution

$$385=5\cdot7\cdot11$$

$$\begin{align} x^2&\equiv1\pmod5\\ x^2&\equiv2\pmod7\\ x^2&\equiv1\pmod{11}\\[10pt] x&\equiv\{1,4\}\pmod5\\ x&\equiv\{3,4\}\pmod7\\ x&\equiv\{1,10\}\pmod{11}\\ \end{align}$$

$$\begin{align} M1\implies&385/5=77\\ &77-1\pmod5=3\pmod5\\[5pt] M2\implies&385/7=55\\ &55-1\pmod7=6\pmod7\\[5pt] M2\implies&385/11=35\\ &35-1\pmod{11}=6\pmod{11}\\[5pt] \end{align}$$

$$a=1,4;\quad b=3,4;\quad c=1,10$$

$$\begin{align} x&\equiv a\cdot77\cdot3+b\cdot5\cdot6+c\cdot35\cdot6\\ &\equiv231a+330b+210c \end{align}$$

Therefore Congruence of 8 cases

Answer 1

$385=5\cdot 7\cdot 11$

$$\begin{align}&x^2\equiv 1\pmod{5}\\ &x^2\equiv 2\pmod{7}\\ &x^2\equiv 1\pmod{11}\end{align}$$

$$\iff \begin{align}&x\equiv \{1,4\}\pmod{5}\\ &x\equiv \{3,4\}\pmod{7}\\ &x\equiv \{1,10\}\pmod{11}\end{align}$$

Now check $8$ cases and use Chinese Remainder Theorem for each case.

Answer 2

Hint. $385 = 5 \times 7 \times 11$. And if $x^2 \equiv 331 \pmod{385}$, then

$$ x^2 \equiv 1 \pmod{5} $$ $$ x^2 \equiv \,\,? \pmod{7} $$ $$ x^2 \equiv \,\,? \pmod{11} $$