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

$\endgroup$

2 Answers 2

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.

$\endgroup$
9
  • $\begingroup$ Won't it be x≡{2,5}(mod7) $\endgroup$
    – nversusp
    Oct 19, 2015 at 23:32
  • $\begingroup$ No. If $x \equiv \{2, 5\} \pmod{7}$, then $x^2 \equiv 4 \pmod{7}$. $\endgroup$
    – Brian Tung
    Oct 19, 2015 at 23:45
  • $\begingroup$ @BrianTung How do you actually get {3,4}. Can you explain please? $\endgroup$
    – nversusp
    Oct 19, 2015 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, 2015 at 23:55
  • $\begingroup$ @user236182 can you please verify my solution. I have added it into the questions itself. $\endgroup$
    – nversusp
    Oct 20, 2015 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} $$

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