0
$\begingroup$

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

|cite|improve this question
$\endgroup$
0
$\begingroup$

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

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

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I understand that is 2 & 1. But How do I prove congruence? $\endgroup$ – nversusp Oct 19 '15 at 23:34
  • $\begingroup$ I would really appreciate your help? $\endgroup$ – nversusp Oct 19 '15 at 23:41
  • $\begingroup$ Look at @user236182's answer, which takes the solution a little further. $\endgroup$ – Brian Tung Oct 19 '15 at 23:42
  • $\begingroup$ 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) $\endgroup$ – nversusp Oct 19 '15 at 23:44
  • $\begingroup$ can you please verify my solution. I have added it into the questions itself. $\endgroup$ – nversusp Oct 20 '15 at 0:19

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.