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

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

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

• Won't it be x≡{2,5}(mod7) Oct 19, 2015 at 23:32
• No. If $x \equiv \{2, 5\} \pmod{7}$, then $x^2 \equiv 4 \pmod{7}$. Oct 19, 2015 at 23:45
• @BrianTung How do you actually get {3,4}. Can you explain please? Oct 19, 2015 at 23:51
• Nevermind, understood. 2+7 =9 and sqrt is 3 2+7+7=16 and sqrt is 4 Oct 19, 2015 at 23:55
• @user236182 can you please verify my solution. I have added it into the questions itself. Oct 20, 2015 at 0:19

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

• I understand that is 2 & 1. But How do I prove congruence? Oct 19, 2015 at 23:34
• I would really appreciate your help? Oct 19, 2015 at 23:41
• Look at @user236182's answer, which takes the solution a little further. Oct 19, 2015 at 23:42
• I did. Won't it be x ≡ {2,5} (mod7). And now, do I have to compare these equations (1,2,1,1,4,2,5,1,10) Oct 19, 2015 at 23:44
• can you please verify my solution. I have added it into the questions itself. Oct 20, 2015 at 0:19