# How does law of quadratic reciprocity work?

From the book,
Suppose $p \equiv 1 \pmod{4}$, then by law of quadratic reciprocity, we have: $$\left(\frac{3}{p}\right) = \left(\frac{p}{3}\right)$$ Next, if $p \equiv 2 \pmod{3}$, then $p \equiv 5 \pmod{12}$ Hence, $$\left(\frac{3}{p}\right) = \left(\frac{p}{3}\right) = -1$$

How do they get those Legendre fraction equal to $-1$? From my understanding: $$\left(\frac{q}{p}\right) \cdot \left(\frac{p}{q}\right) = (-1)^{\frac{p-1}{2}\cdot\frac{q-1}{2}}$$ So $q = 3 \implies \frac{q-1}{2} = \frac{3-1}{2} = 1$ For $p$, I take $p \equiv 5 \pmod{12} \implies p = 5 + 12k$, for some integers k.
Hence, $\frac{p-1}{2} = \frac{12k + 5 - 1}{2} = \frac{12k + 4}{2} = 6k + 2.$ And this $6k + 2$ is even :( ! How does $(-1)^{even} = -1$?
Any idea? I think I made some logic mistakes somewhere, but I couldn't find where.

Update
The problem was from Elementary Number Theory and Its Application - Kenneth H.Rosen 5th Edition.

Problem
Using the law of quadratic reciprocity, show that if $p$ is an odd prime, then $$\left(\frac{3}{p}\right) = 1 \text{ if } p \equiv \pm 1 \pmod{12}$$ $$\left(\frac{3}{p}\right) = -1 \text{ if } p \equiv \pm 5 \pmod{12}$$

Solution Thanks,

Now I'm even more confused :(!
Consider two cases:
Case 1 $$p \equiv 1 \pmod{4} \text{ and } p \equiv 1 \pmod{3}$$ Then,
$$p \equiv 1 \pmod{12} \implies p = 12k + 1$$
Hence,
$$\frac{p - 1}{2} \cdot \frac{3 - 1}{2} = \frac{12k}{2} = 6k = \text{ even }$$
Which implies
$$\left(\frac{3}{p}\right) \cdot \left(\frac{p}{3}\right) = 1$$
So both must be $1$ or $-1$.

Case 2 $$p \equiv 1 \pmod{4} \text{ and } p \equiv 2 \pmod{3}$$ Then,
$$p \equiv 5 \pmod{12} \implies p = 12k + 5$$
Hence,
$$\frac{p - 1}{2} \cdot \frac{3 - 1}{2} = \frac{12k + 4}{2} = 6k + 2 = 2(3k + 1) = \text{ even }$$ Which implies
$$\left(\frac{3}{p}\right) \cdot \left(\frac{p}{3}\right) = 1$$ So both must be $1$ or $-1$.

I don't see how these arguments can be deduced to the solution. Any suggestion?

-
Please cite the "book" and page number. – Bill Dubuque Mar 28 '11 at 23:59
It's called the "Legendre symbol", not the "Legendre fraction". – Arturo Magidin Mar 29 '11 at 3:13
@Bill Dubuque: See my edit. Thank you. @Arturo Magidin: Thank you. – Chan Mar 29 '11 at 3:39

I believe you can find the value of $(3|p)$ without finding $p\equiv 5\pmod{12}$, by use of the second supplement to quadratic reciprocity. Recall that $$\left(\frac{2}{p}\right)=(-1)^{(p^2-1)/8}.$$ Since $p\equiv 2\pmod{3}$, you then have $(p|3)=(2|3)=-1$. So altogether, $$\left(\frac{3}{p}\right)\left(\frac{p}{3}\right)=\left(\frac{3}{p}\right)\left(\frac{2}{3}\right)=\left(\frac{3}{p}\right)(-1)=(-1)^{(p-1)(3-1)/4}=(-1)^{(p-1)/2}=1$$ This implies $(3|p)=-1$.

-
Many thanks. Now I got it ;). – Chan Mar 29 '11 at 4:03

If $\rm\:q\:$ and $\rm\:p = 4\:k+1\:$ are distinct odd primes then by the law of quadratic reciprocity we have

$\displaystyle\rm\quad\quad\quad\quad\ \ \frac{p-1}{2}\ =\ 2\:k\ \ \Rightarrow\ \ \left(\frac{q}{p}\right)\ \times\ \left(\frac{p}{q}\right)\ =\ (-1)^{\frac{p-1}{2}\ \frac{q-1}{2}}\: =\ 1$

Therefore we deduce that $\rm\displaystyle\ \ \left(\frac{q}{p}\right)\ =\ \left(\frac{p}{q}\right)$

So $\displaystyle\rm\ q=3,\ p = 2+3\:n\ \Rightarrow\ \left(\frac{3}{p}\right)\ =\ \left(\frac{2+3\:n}{3}\right)\ =\ \left(\frac{2}{3}\right)\ =\:-1\$ since $\rm\:2\:$ is not a square $\rm\:(mod\ 3)\:.$

-

Personally I find that a huge step in understanding things is knowing motivation behind the theorem. Douglas and yunone have both probably explained the meaning behind those equations pretty well but take a look at this Wikipedia article for more historical context: http://en.wikipedia.org/wiki/Quadratic_reciprocity#History_and_alternative_statements

-

If $p\equiv 2 \mod 3$ then $p$ is not a square mod $3$. That is the justification for the second line.

As you correctly calculated, if $p$ is $5 \mod 12$ (and $q$ is odd) then $(-1)^{\frac {p-1}{2} \cdot \frac {q-1}{2}}$ is $(-1)^{\text{even}} = 1$.

You have an incorrect statement of the main case of quadratic reciprocity, for $p$ and $q$ odd primes. Instead of an equal sign between $(\frac p q)$ and $(\frac q p)$ there should be no symbol, or perhaps $\times$. The product $(\frac p q) (\frac q p)$ equals $(-1)^{\frac {p-1}{2} \cdot \frac {q-1}{2}}$, which is to say the product is $1$ except when $p$ and $q$ are both $3 \mod 4$, in which case it is $-1$.

-