4
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Your proposed strategy is exactly right. I can write out part of an answer if you run into difficulties. $\endgroup$ Apr 5, 2013 at 18:30
  • $\begingroup$ Am I allowed to use the results from LQR to prove the statement? Or is that some sort of circular argument? $\endgroup$
    – Haikal Yeo
    Apr 5, 2013 at 18:46
  • $\begingroup$ 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. $\endgroup$ Apr 5, 2013 at 18:49
  • $\begingroup$ 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. :) $\endgroup$
    – Haikal Yeo
    Apr 5, 2013 at 18:51

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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}$? $\endgroup$
    – Haikal Yeo
    Apr 5, 2013 at 22:18
  • $\begingroup$ (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. $\endgroup$ Apr 5, 2013 at 22:59
  • $\begingroup$ My typo. I meant that I don't understand how you got $p\equiv\alpha^2\pmod{4}$. $\endgroup$
    – Haikal Yeo
    Apr 6, 2013 at 7:41
  • $\begingroup$ 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}$. $\endgroup$ Apr 6, 2013 at 7:47
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 6, 2013 at 18:49
2
$\begingroup$

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$.

Barring errors. Thanks in advance.

$\endgroup$
3
  • $\begingroup$ could you explain a little bit on the fact that $ (\frac{(-1)^{\frac{p-1}{2}}p}q)=1$ implies $p\equiv\pm\beta^2\pmod {4q}$ $\endgroup$ May 27, 2021 at 5:32
  • $\begingroup$ @PeterWang $(\frac{(-1)^{\frac{p-1}{2}}p}q)=1$ means $(-1)^{\frac{p-1}{2}}p\equiv\gamma^2\pmod q$ for some $\gamma$. If $\gamma$ is odd, take $\beta=\gamma$, otherwise let $\beta=q-\gamma$, so that $\beta$ is odd and $(-1)^{\frac{p-1}2}p\equiv\beta^2\pmod q$. Now $(-1)^{\frac{p-1}2}p\equiv1\equiv\beta^2\pmod 4$ by a direct examination, and hence we see that $(-1)^{\frac{p-1}2}p$ must be congruent to $\beta^2\pmod{4q}$. Feel free to ask more if this is not clear enough. $\endgroup$
    – awllower
    May 27, 2021 at 6:33
  • 1
    $\begingroup$ Thanks, I understand now. And have to say, It is pretty unexpected that $(-1)^{\frac{p-1}{2}}p\equiv 1\pmod 4$ hold. I think this is the reason for introducing $p^{*}=(-1)^{\frac{p-1}{2}}p$ $\endgroup$ May 27, 2021 at 6:48
1
$\begingroup$

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?)

$\endgroup$
1
  • $\begingroup$ Yes of course you can take $\gamma=1$ here: I do not know why you take this $\gamma$ into consideration in fact. $\endgroup$
    – awllower
    Apr 6, 2013 at 9:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .