Why Is the Legendre Symbol (3/p) Determined by p Modulo 12?

Assume throughout that $p>3$ is a prime. The notation $(\frac{3}{p})$ is the Legendre symbol: it is $1$ if 3 is a nonzero square modulo $p$, and $-1$ if 3 is not a square modulo $p$. The claim follows directly from the quadratic reciprocity law, together with the possible prime residues modulo 12.

Why only four residue classes occur

Every prime greater than 3 is odd and is not divisible by 3. Its residue modulo 12 must therefore be relatively prime to 12. The possibilities are

$$p\equiv 1,5,7,11\pmod{12}.$$

It remains to evaluate the Legendre symbol in these four cases.

Apply quadratic reciprocity

For distinct odd primes $a$ and $b$, quadratic reciprocity states

$$\left(\frac{a}{b}\right)\left(\frac{b}{a}\right) =(-1)^{\frac{a-1}{2}\frac{b-1}{2}}.$$

Take $a=3$ and $b=p$. Since $(3-1)/2=1$, this becomes

$$\left(\frac{3}{p}\right) =(-1)^{\frac{p-1}{2}}\left(\frac{p}{3}\right).$$

The symbol $(\frac{p}{3})$ is easy to determine: the nonzero squares modulo 3 consist only of 1. Consequently,

$$\left(\frac{p}{3}\right)= \begin{cases} 1,&p\equiv 1\pmod{3},\\ -1,&p\equiv 2\pmod{3}. \end{cases}$$

The other factor depends on whether $p$ is 1 or 3 modulo 4:

$$(-1)^{\frac{p-1}{2}}= \begin{cases} 1,&p\equiv 1\pmod{4},\\ -1,&p\equiv 3\pmod{4}. \end{cases}$$

So the answer is the product of two signs: one determined by $p$ modulo 3 and one determined by $p$ modulo 4.

Evaluate the four cases

$p$ modulo 12	$p$ modulo 4	$p$ modulo 3	$(-1)^{(p-1)/2}$	$(p/3)$	$(3/p)$
1	1	1	1	1	1
5	1	2	1	$-1$	$-1$
7	3	1	$-1$	1	$-1$
11	3	2	$-1$	$-1$	1

For example, if $p\equiv 7\pmod{12}$, then $p\equiv3\pmod4$ and $p\equiv1\pmod3$. The reciprocity sign is $-1$, while $(\frac{p}{3})=1$, so $(\frac{3}{p})=-1$. If $p\equiv11\pmod{12}$, both factors are $-1$, and their product is $1$.

This proves the stated result:

$$\left(\frac{3}{p}\right)= \begin{cases} 1,&p\equiv1,11\pmod{12},\\ -1,&p\equiv5,7\pmod{12}. \end{cases}$$

Equivalently, among primes greater than 3, the congruence $3$ is a square modulo $p$ exactly when $p\equiv\pm1\pmod{12}$.

Worked checks

Take $p=13$. Since $13\equiv1\pmod{12}$, the formula predicts $(\frac{3}{13})=1$. Indeed, $4^2=16\equiv3\pmod{13}$, so 3 is a square modulo 13.

Take $p=17$. Since $17\equiv5\pmod{12}$, the formula predicts $(\frac{3}{17})=-1$. The reciprocity calculation gives the same result: $17\equiv1\pmod4$, so the sign factor is 1, and $17\equiv2\pmod3$, so $(\frac{17}{3})=-1$. Their product is $-1$.

Common mistakes

• Forgetting that $p$ must be prime. The Legendre symbol $(\frac{3}{p})$ is defined here for an odd prime denominator. The statement is not a claim about every integer $p>3$.
• Using only the residue modulo 3. Quadratic reciprocity also contributes the sign $(-1)^{(p-1)/2}$, which depends on $p$ modulo 4. Ignoring it gives the wrong answer for classes such as $p\equiv7\pmod{12}$.
• Including $p=3$. Reciprocity in this form uses distinct primes, and the Legendre symbol $(\frac{3}{3})$ is 0, not 1 or $-1$. The condition $p>3$ excludes this case.
• Confusing a Legendre symbol with a congruence. A value of 1 means that some integer $x$ satisfies $x^2\equiv3\pmod p$; it does not mean that 3 itself is congruent to a square as an ordinary integer.