When computing the Legendre symbol $(\frac{3}{p})$, how to combine different congruences together into one statement?

Question

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

Answer 1

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

Answer 2

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