# testing for quadratic residues using Legendre's symbol

So I am a bit confused about an example in the book Elementary Number Theory by Jones. I am doing a problem which makes me show 3 is a quadratic residue of 13, but not of 7. I did this question numerically using the law of quadratic reciprocity. I am a bit confused about the example it gives though.

First lets see what the theorem says. It says that if $p, q$ are distinct odd primes, then $$\left( \frac{q}{p} \right) = \left( \frac{p}{q} \right)$$ except when the case $p \equiv q \equiv 3 \pmod 4$. An equivalent result by Legendre is $$\left( \frac{q}{p} \right) \cdot \left( \frac{p}{q} \right) =(-1)^{(p-1)(q-1)/4}$$

Note that I have shown $3$ is not a quadratic residue of 7. The example states the following

For which primes $p$ is 3 a quadratic residue. Since 3 is a QR of 2 and 3 is NOT a QR of 3, we may assume $p>3$. If $p \equiv 1 \mod 4$ then the law gives $$\left( \frac{3}{p} \right) = \left( \frac{p}{3} \right) = \begin{cases} +1 & \text{if p \equiv 1 \pmod 3, that is if p \equiv 1 \pmod {12}} \\ -1 &\text{if p \equiv 2 \pmod 3, that is if p \equiv 5 \pmod {12}} \end{cases}$$

It further has more case when $p \equiv 3 \pmod 4$ .

So my questions are (though basic):

1) Why do they assume $p>3$.

2) How can $p \equiv 1 \pmod 3$ mean $p \equiv 1 \pmod 12$

and if we take $p = 7$ then since $7 \equiv 1 \pmod 3$ it must be that $$\left( \frac{3}{7} \right) = 1$$ by the above example/theorem. No? but I am certain that 3 is NOT a QR for 7.

-
The Legendre symbol is not defined for odd prime denominator so $p=2$ is not valid. Also we do not want $p|3$... – fretty Feb 24 '13 at 10:38
Question 2 - By itself $p\equiv 1 \bmod 3$ does not imply $p\equiv 1 \bmod 12$, but we also know that $p\equiv 1 \bmod 4$, so the chinese remainder theorem says... – fretty Feb 24 '13 at 10:43

Since $3$ and $7$ are both of the form $4k+3$, by Reciprocity we have $(3/7)=-(7/3)=-(1/3)=-1$.

As to why start past $3$, there is a special "rule" for determining whether $(2/p)$ is $1$ or $-1$. We have for the odd prime $p$ that $(2/p)=1$ if $p\equiv \pm 1\pmod{8}$, and $(2/p)=-1$ if $p\equiv \pm 3\pmod{8}$. This is much easier to establish than Reciprocity.

-
Notice that OP claims to have finished this part, though. – awllower Feb 24 '13 at 4:40
OP is certain that $3$ is not a QR of $7$, presumably by checking that nothing works. But OP seems to think this contradicts the result obtained by applying Quadratic Reciprocity – André Nicolas Feb 24 '13 at 4:43
@awllower, Andrew is right. I manually checked that 3 is not a QR for 7. I see the reasoning now. I failed to see the exception in the theorem. The theorem does not apply since 3 = 7 = 3 mod 4. I wonder if there is enough room in the comments to explain WHY it fails for this case? – Tyler Hilton Feb 24 '13 at 4:45
Sorry. I assumed that OP showed this by quadratic reciprocity law. – awllower Feb 24 '13 at 4:50
For sure not! There is no really short proof of the Law of Quadratic Reciprocity. You can check easily that if $p\equiv q\equiv 3\pmod{4}$, then $(p-1)(q-1)/4$ is odd, so when you raise $-1$ to this power, you get $-1$, meaning that $(q/p)=-(p/q)$. But that is not a proof, just an indication that the formula produces the right result. – André Nicolas Feb 24 '13 at 4:52

For (1), because they have examined the cases for $p$ less than $3$, they can assume $p$ is greater than $3$.
For (2), the theorem assumes at the beginning that $p\equiv 1\pmod4$; this, combined with $p\equiv1\pmod3$, then gives $p\equiv1\pmod{12}$.Moreover, since $7\equiv3\pmod4$, the theorem does not apply in this case, so there is no contradiction here.
Edit:
Actually the example is only to specify a case of the quadratic reciprocity law. And in fact, as $7\equiv3\pmod4$, the law tells us that $(\frac{3}{7})=-(\frac{7}{3})=-1$.If one wonders why the above example fails, it is because that both $3$ and $7$ are $\equiv3\pmod4$, so that the result of the theorem should be reversed, thus coinciding with your result of manual chack.

-
I see. Thank you. I failed to notice a few things. For (2), you can multiply the modulus together because they are coprime? OR is this condition not neccessary – Tyler Hilton Feb 24 '13 at 4:46
For (2), I used the Chinese remainder theorem, which is logically what one already learned before the reciprocity. – awllower Feb 24 '13 at 4:51
yes thats exactly what I was thinking off, and yes the coprimality is a condition of CRT – Tyler Hilton Feb 24 '13 at 4:55
Good. If there is more quesition, feel free to ask. :) – awllower Feb 24 '13 at 4:56