# Law of Quadratic Reciprocity Equivalent Statement

Let $p,q$ be two distinct odd primes. Then $(\frac{q}p)=1 \iff p=\pm\beta^2 \pmod{4q}$ for some odd $\beta$. Show that this statement is eqivalent to the Law of Quadratic Reciprocity.

I'm trying to grapple with what the question is actually asking me to show.

Do I split into various cases of what $p$ and $q$ could possibly be (ie. $1 \pmod 4$ and $3 \pmod 4$) and then show that in each case, the statement holds?

-
Your proposed strategy is exactly right. I can write out part of an answer if you run into difficulties. –  André Nicolas Apr 5 '13 at 18:30
Am I allowed to use the results from LQR to prove the statement? Or is that some sort of circular argument? –  Haikal Yeo Apr 5 '13 at 18:46
It seems like the goal is to deduce this statement using QR, and also to deduce QR from this statement - it asks to show equivalence, not to show that the statement is true. –  Thomas Andrews Apr 5 '13 at 18:49
Perhaps writing out one of the cases may help so that I have an idea of how it should actually work and then I can try writing out the rest of cases. :) –  Haikal Yeo Apr 5 '13 at 18:51

We do one of the four cases. Because $p$ and $q$ both of the shape $4k+1$ is "too easy" and does not fully illustrate the problems we can bump into, we deal with the case $p$ of the form $4k+3$ and $q$ of the form $4k+1$.

Suppose that $(q/p)=1$, with $p$ of the form $4k+3$ and $q$ of the form $4k+1$. We want to show that $p\equiv \pm \beta^2\pmod{4q}$ for some odd $\beta$.

Note that by Quadratic Reciprocity we have $(p/q)=1$. So $p$ is a quadratic residue modulo $q$. This means that $p\equiv \alpha^2\pmod{q}$ for some $\alpha$. But $-1$ is a quadratic residue of $q$, since $q$ is of the form $4k+1$. So $-1\equiv \gamma^2\pmod{q}$ for some $\gamma$, and therefore $$p\equiv -(\alpha\gamma)^2\pmod{q}.$$ Without loss of generality we may assume that $\alpha\gamma$ is odd. If it isn't, replace it by $q-\alpha\gamma$.

Since the square of an odd number is congruent to $1$ modulo $4$, we have $$p\equiv -(\alpha\gamma)^2\pmod{4}.$$

It follows that $p\equiv -(\alpha\gamma)^2\pmod{4q}$.

The reverse direction is straightforward. Reverse directions are not really needed if we deal with the "forward" direction in all four cases.

-
I don't quite understand how you got $p\equiv -(\alpha\gamma)^2\pmod{4q}$. Also, can I just check that you have covered the $p$ is a positive square case by the part on $p\equiv\alpha^2 \pmod{q}$? –  Haikal Yeo Apr 5 '13 at 22:18
(1) If $x\equiv a\pmod{m}$ and $x\equiv a\pmod{n}$, where $m$ and $n$ are relatively prime, then $x\equiv a \pmod{mn}$. (2) The meaning of the $\pm$ here is that one of them holds. They can't, in this case, both be solvable, since $p$ is of the form $4k+3$, so the congruence $p\equiv 1\pmod{4q}$ cannot hold. –  André Nicolas Apr 5 '13 at 22:59
My typo. I meant that I don't understand how you got $p\equiv\alpha^2\pmod{4}$. –  Haikal Yeo Apr 6 '13 at 7:41
I did not assert that, the line says $p\equiv -(\alpha\gamma)^2\pmod{4}$. This is because (i) $\alpha\gamma$ is odd and therefore (ii) its square is congruent to $1$ mod $4$ and (iii) therefore $-(\alpha\gamma)^2$ is congruent to $-1$ mod $4$. But $p$ is of the form $4k+3$, so $p\equiv -1\pmod{4}$. –  André Nicolas Apr 6 '13 at 7:47
It goes similarly. Suppose $(q/p)=1$. Then $(p/q)=-1$. But $(-1/q)=-1$. So $-p$ is a QR. Thus $-p\equiv \alpha^2$. And so on, very similar to other one. They are so similar they could be done together, but with separate you retain more concrete control. –  André Nicolas Apr 6 '13 at 18:49

Just to show that I'm on the right track, I'll try solving the easier case and hopefully somebody can check it for me.

Suppose that $(q/p)=1$, with $p$ of the form $4k+1$ and $q$ of the form $4k+1$. We want to show that $p\equiv \pm \beta^2\pmod{4q}$ for some odd $\beta$.

Note that by Quadratic Reciprocity we have $(p/q)=1$. So $p$ is a quadratic residue modulo $q$. This means that $p\equiv \alpha^2\pmod{q}$ for some $\alpha$. But $1$ is a quadratic residue of $q$. So $1\equiv \gamma^2\pmod{q}$ for some $\gamma$, and therefore $$p\equiv (\alpha\gamma)^2\pmod{q}.$$ Without loss of generality we may assume that $\alpha\gamma$ is odd. If it isn't, replace it by $q-\alpha\gamma$.

Since the square of an odd number is congruent to $1$ modulo $4$, we have $$p\equiv (\alpha\gamma)^2\pmod{4}.$$

It follows that $p\equiv (\alpha\gamma)^2\pmod{4q}$.

(I suppose we can just take $\gamma=1$ here?)

-
Yes of course you can take $\gamma=1$ here: I do not know why you take this $\gamma$ into consideration in fact. –  awllower Apr 6 '13 at 9:18

This an approach through which you have not to split into cases, but have to be more careful.
The canonical, or traditional, reciprocity law is: Let $p, q$ be primes. Then $$(\frac{q}p)=(\frac{p}q)(\frac{-1}q)^{\frac{p-1}{2}}$$.
Now, if $p\equiv \pm \beta^2\pmod {4q}$, then $(\frac{q}p)=(\frac{\pm1}q)(\frac{-1}q)^{\frac{p-1}{2}}$, where the sign is determined by $\pm p\equiv 1\pmod 4$, i.e. $\pm1=(-1)^{\frac{p-1}{2}}$. Hence it follows that $(\frac{q}p)=1$. Conversely, if $(\frac{q}p)=1$, then $(\frac{p}q)=(\frac{-1}q)^{\frac{p-1}{2}}$, so $(\frac{(-1)^{\frac{p-1}{2}}p}q)=1$, namely, $p\equiv\pm\beta^2\pmod {4q}$.
Also, we have to travel back in this directin. That is, we have to show that, if our statement holds, then so does the traditional statement. So, let us see what our statement means: $p\equiv \pm\beta^2\pmod{4q}$ means that $(-1)^{\frac{p-1}{2}}p\equiv \beta^2 \pmod{q}$, or, equivalently, $(\frac{(-1)^{\frac{p-1}{2}}p}q)=1$. But his is nothing else than our traditional law.

Conclusion:
This particular formulation needs barely any errort to verify its equivalence with the classical one, once one realizes how the plus or minus sign in the statement is determined by $p$.