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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .