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.

  • $\begingroup$ The Legendre symbol is not defined for odd prime denominator so $p=2$ is not valid. Also we do not want $p|3$... $\endgroup$ – fretty Feb 24 '13 at 10:38
  • $\begingroup$ 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... $\endgroup$ – 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.

  • $\begingroup$ Notice that OP claims to have finished this part, though. $\endgroup$ – awllower Feb 24 '13 at 4:40
  • $\begingroup$ 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 $\endgroup$ – André Nicolas Feb 24 '13 at 4:43
  • $\begingroup$ @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? $\endgroup$ – Tyler Hilton Feb 24 '13 at 4:45
  • $\begingroup$ Sorry. I assumed that OP showed this by quadratic reciprocity law. $\endgroup$ – awllower Feb 24 '13 at 4:50
  • $\begingroup$ 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. $\endgroup$ – 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.
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.

  • $\begingroup$ 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 $\endgroup$ – Tyler Hilton Feb 24 '13 at 4:46
  • $\begingroup$ For (2), I used the Chinese remainder theorem, which is logically what one already learned before the reciprocity. $\endgroup$ – awllower Feb 24 '13 at 4:51
  • $\begingroup$ yes thats exactly what I was thinking off, and yes the coprimality is a condition of CRT $\endgroup$ – Tyler Hilton Feb 24 '13 at 4:55
  • $\begingroup$ Good. If there is more quesition, feel free to ask. :) $\endgroup$ – awllower Feb 24 '13 at 4:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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