Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I try to find Legendre symbol for $\left(\dfrac{3}{p}\right)$.

This is what I did so far:
case 1: $p=3\mod{4}. $ so $\left(\dfrac{3}{p}\right)=-\left(\dfrac{p}{3}\right)$. now $\left(\dfrac{3}{p}\right)=-1$ iff $p=2 \mod{3}$

case 2: $p=1\mod{4}$ so $\left(\dfrac{3}{p}\right)=\left(\dfrac{p}{3}\right)$. now $\left(\dfrac{3}{p}\right)=1$ iff $p=1 \mod{3}$

Now, I don't know how to combine the cases (each case with itself and together).

share|improve this question
1  
The question has been asked on MSE very recently, and probably several times before that. –  André Nicolas Mar 28 '13 at 17:29

2 Answers 2

up vote 3 down vote accepted

As you've noted, the cases are as follows:

  • If $p\equiv 3\bmod 4$, then $(\frac{3}{p})=-(\frac{p}{3})$.

    • If $p\equiv 1\bmod 3$, then $(\frac{p}{3})=1$, so $(\frac{3}{p})=-1$.
    • If $p\equiv 2\bmod 3$, then $(\frac{p}{3})=-1$, so $(\frac{3}{p})=1$.
  • If $p\equiv 1\bmod 4$, then $(\frac{3}{p})=(\frac{p}{3})$.

    • If $p\equiv 1\bmod 3$, then $(\frac{p}{3})=1$, so $(\frac{3}{p})=1$.
    • If $p\equiv 2\bmod 3$, then $(\frac{p}{3})=-1$, so $(\frac{3}{p})=-1$.

Thus,

$$\left(\frac{3}{p}\right)=\begin{cases} 1 & \text{ if }\begin{cases}p\equiv 3\bmod 4 \text{ and }p\equiv 2\bmod 3,\text{ or }\\ p\equiv 1\bmod 4\text{ and }p\equiv 1\bmod 3, \end{cases}\\[0.1in] -1 & \text{ if }\begin{cases}p\equiv 3\bmod 4 \text{ and }p\equiv 1\bmod 3,\text{ or }\\ p\equiv 1\bmod 4\text{ and }p\equiv 2\bmod 3, \end{cases} \end{cases}$$

The Chinese remainder theorem tells you that any statement of the form $$n\equiv a\bmod 3\quad\text{ and }\quad n\equiv b\bmod 4$$ can be converted, essentially uniquely, into a statement of the form $$n\equiv c\bmod 12.$$ The best way of solving this sort of thing in general is to find an $x$ and $y$ such that $$x\equiv 1\bmod 3 \quad\text{ and }\quad x\equiv 0\bmod 4$$ $$y\equiv 0\bmod 3\quad\text{ and }\quad y\equiv 1\bmod 4$$ so that the statement "$n\equiv a\bmod 3$ and $n\equiv b\bmod 4$" is equivalent to $$n\equiv xa+yb\bmod 3\quad\text{ and }n\equiv xa+yb\bmod 4,$$ hence $$n\equiv xa+yb\bmod 12.$$ For example, one choice that works is $x=4$ and $y=9$. Thus, to reformulate the statement that $$p\equiv 1\bmod 4\quad\text{ and }\quad p\equiv 2\bmod 3,$$ you have that $9\cdot 1+4\cdot 2=17$, and $$p\equiv 1\equiv 17\bmod 4\quad\text{ and }\quad p\equiv 2\equiv 17\bmod 3,$$ so that $$p\equiv 17\equiv 5\bmod 12.$$ You can check that this is correct: $$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|} n \bmod 12 & 0 & 1 & 2 & 3 & 4 & \color{red}{\large \mathbf{5}} & 6 & 7 & 8 & 9 & 10 & 11 \\\hline n\bmod 3 & 0 & 1 & 2 & 0 & 1 & \color{red}{\large \mathbf{2}} & 0 & 1 & 2 & 0 & 1 & 2 \\\hline n\bmod 4 & 0 & 1 & 2 & 3 & 0 & \color{red}{\large \mathbf{1}} & 2 & 3 & 0 & 1 & 2 & 3 \end{array}$$

share|improve this answer
    
thanks! so (3/p)=1 iff p=1,5mod12 . right? –  user1932595 Mar 28 '13 at 17:32
    
No, what I proved was that $$p\equiv 1\bmod 4\text{ and }p\equiv 2\bmod 3\iff p\equiv 5\bmod 12.$$ Look at where that is in the list of cases in the beginning of my answer. –  Zev Chonoles Mar 28 '13 at 17:36
    
yes..i forgot. so the answer is (3/p)=1 iff p=1,5mod12 . –  user1932595 Mar 28 '13 at 17:37
    
The case of $$p\equiv 1\bmod 4\text{ and }p\equiv 2\bmod 3$$ is in the $(\frac{3}{p})=-1$ side. –  Zev Chonoles Mar 28 '13 at 17:38

It's easy. You've shown $\rm\:(3\mid p) = ab,\:$ for $\rm\ a = (p\ mod\ 4) = \pm1,\:$ and $\rm\: b = (p\ mod\ 3) = \pm1.\:$ From CRT, $\rm\:p \equiv (a,b)\ mod\ (4,3)\iff p\equiv 4b\!-\!3a\,\ (mod\ 12).$ Thus for $\rm\:p\ne 2,3\:$ we have

$$\rm \left(\dfrac{3}p\right) = \left(\frac{3}{4b\!-\!3a}\right) = ab$$

e.g. $\rm\quad \begin{eqnarray}\rm 17\,=\,4(8)\!-\!3(5)\\ \rm so\ \ (a,b)=(5,8)\end{eqnarray}\,\bigg\rbrace\ \Rightarrow\ \left(\dfrac{3}{17}\right) = ab = (5\ mod\ 4)(8\ mod\ 3) = (1)(-1) = -1.$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.