I was reading the wiki for Quadratic Reciprocity (QR) and found Euler's Formulation (EQR), which I decided to attempt to prove its equivalence with the standard statement as a simple exercise. I was having difficulty with this proof. As a reminder, I'll state them here:

Theorem. (QR) Let $p$ and $q$ be distinct odd primes. Then $$\left(\frac pq\right)=(-1)^{\frac{(p-1)(q-1)}{4}}\cdot \left(\frac qp\right)$$

This is a common phrasing of Quadratic Reciprocity, so it's the one whose equivalence I will try to prove. Now Euler's Formulation uses an important fact. Namely, if $m$ and $n$ are odd, then either $m+n$ or $m-n$ is divisible by $4$, but not both. This is pretty easy to prove using mod $4$. Now Euler's Formulation is as follows:

Theorem. (EQR) Let $p$ and $q$ be distinct odd primes. If $4a \mid p\pm q$ for positive integer $a$, then $\left(\frac{a}{p}\right)=\left(\frac{a}{q}\right)$.

(I added $a$'s positivity, since I found a simple counterexample when $a$ is allowed to be negative). Now I was able to show EQR$\implies$QR and I could also show QR$\implies$EQR, but only if I had the first and second supplements. So I figured EQR$\implies$QR also needed to prove the two supplements. I was able to prove the second supplement, but I've been having difficulty with the first one. With each other part I could at least get a footing, but while the first supplement is easy to prove in other ways, it seems like I can't get a good footing under the assumption of EQR. My question is how do I finish this proof?

  • 1
    $\begingroup$ What is the question? Edit: also, there seems to be a typo in your "EQR", right now it reads $$\left(\frac{a}{p}\right)=\left(\frac{a}{p}\right)$$ $\endgroup$ Apr 1 '20 at 2:27
  • 1
    $\begingroup$ I'm not sure why the downvote was necessary. The question is pretty straightforward: How do I complete this proof? Specifically, how to I prove the first supplement? I was merely catching the reader up on where I'm at in proving the equivalence. $\endgroup$
    – JasonM
    Apr 1 '20 at 2:34
  • $\begingroup$ Suggest you get D. A. Cox, Primes of the Form $x^2 + n y^2.$ The second edition fixed some typos. What you want is in roughly the first 60 pages; he makes a point of discussing your type of statement. $\endgroup$
    – Will Jagy
    Apr 1 '20 at 2:52
  • 1
    $\begingroup$ Evidently the specific thing I was remembering was on page 17, the "crucial property of the Jacobi symbol" $\endgroup$
    – Will Jagy
    Apr 1 '20 at 2:59
  • $\begingroup$ I've posted an answer. I hope you can all verify its validity. $\endgroup$
    – JasonM
    May 5 '20 at 20:18

I'm the OP. I figured out the solution. The first supplement of quadratic reciprocity, we will denote (1S), and the second supplement we will denote (2S). Furthermore, we denote by $\textrm{sgn}(x)$ the sign of $x$ (i.e. $\pm 1$). In what follows, all $\pm $ signs in the same equation take on the same sign, and to denote where they have opposite sign, we use the $\mp$ sign. Lastly, I found a better version of (EQR) that implies not only (2S) and (QR), but also (1S). This version is as follows:

(EQR*) For any $a$ satisfying $p\equiv \pm q \bmod 4a$, we have $\left(\frac ap \right)=\textrm{sgn}(a)^{\frac{p-q}{2}}\left(\frac aq \right)$.

Now we will attempt to prove its equivalence to $(1S)\wedge (2S) \wedge (QR)$.

Claim. $(1S)\wedge(2S)\wedge (QR) \iff (EQR^*)$

Proof: ($\Longrightarrow$) Let $p\equiv \pm q \bmod 4a$ for some $a$. It suffices to prove for primes and $-1$. Note when $a>0$, we have $\textrm{sgn}(a)=+1$, so $\textrm{sgn}(a)^{\frac{p-q}{2}}=+1$. We set $p=\pm q+4ab$ for some $ b$.

If $a=-1$, then since $p-q$ is even, by $(1S)$ we have \begin{align*} \left( \frac ap \right) &= \left( \frac {-1}{p}\right)\\ &= (-1)^{\frac{p-1}{2}}\\ &=(-1)^{\frac{p-q}{2}}(-1)^{\frac{q-1}{2}}\\ &=\textrm{sgn}(a)^{\frac{p-q}{2}}\left( \frac aq \right) \end{align*}

Now if $a=2$, then by $(2S)$ we have \begin{align*} \left( \frac ap \right) &=\left( \frac 2p \right)\\ &=(-1)^{\frac{p^2-1}{8}}\\ &=(-1)^{\frac{(\pm q +8b)^2-1}{8}}\\ &=(-1)^{\frac{q^2-1}{8}+\frac{\pm 16bq+16a^2b^2}{8}}\\ &=(-1)^{\frac{q^2-1}{8}}\\ &=\left( \frac 2q \right)\\ &=\left( \frac aq \right) \end{align*}

Lastly, if $a$ is an odd prime, then by (QR) we have \begin{align*} \left( \frac ap \right) &= (-1)^{\frac{(p-1)(a-1)}{4}}\left( \frac pa \right) \\ &= (-1)^{\frac{(p-1)(a-1)}{4}}\left( \frac{\pm q +4ab}{a}\right) \\ &=(-1)^{\frac{(p-1)(a-1)}{4}}\left( \frac{\pm q}{a}\right) \\ &=(-1)^{\frac{(p-1)(a-1)}{4}}(\pm 1)^{\frac{a-1}{2}}\left( \frac qa \right) \\ &=(-1)^{\frac{(p-1)(a-1)}{4}}(-1)^{\mp \frac{(q-1)(a-1)}{4}}(\pm 1)^{\frac{a-1}{2}}\left( \frac aq \right)\\ &=(-1)^{\frac{pa-p-a+1\mp qa\pm q\pm a\mp 1}{4}}(\pm 1)^{\frac{a-1}{2}}\left( \frac aq \right) \\ &=(-1)^{\frac{(p\mp q)(a-1)-(a\mp a)+1\mp 1}{4}}(\pm 1 )^{\frac{2a-2}{4}}\left( \frac aq \right)\\ &=(-1)^{\frac{(p\mp q)(a-1)}{4}}(-1)^{\frac{-(a\mp a)+1\mp 1}{4}}(\pm 1 )^{\frac{2a-2}{4}}\left( \frac aq \right)\\ &=\underbrace{(-1)^{b(a-1)}}_{=+1}\underbrace{(-1)^{\frac{-(a\mp a)+1\mp 1}{4}}(\pm 1 )^{\frac{2a-2}{4}}}_{=+1}\left( \frac aq \right)\\ &=\left( \frac aq \right) \end{align*}

Since $\left( \frac xp \right)$ and $\textrm{sgn}(x)$ are completely multiplicative functions, combining these results we know it holds for all $a$.

($\Longleftarrow$) Now let (EQR*) hold, and suppose $p=\pm q+4A$.
Now if $p\equiv 1 \bmod 4$, then $4\big| p-5$, and thus, $\left( \frac{-1}{p}\right)=\left( \frac {-1}{5}\right)=+1$. Furthermore, if $p\equiv 3 \bmod 4$, then $4 \big| p-3$, so $\left( \frac{-1}{p}\right)=\left( \frac{-1}{3}\right)=-1$. Therefore, $\left( \frac {-1}{p}\right)=(-1)^{\frac{p-1}{2}}$, so $(1S)$ holds.

Furthermore, since $p$ is odd, we have $p\equiv 1, 3, 5,$ or $ 7 \bmod 8$. Thus, $8\big| p-17, p-3, p-5, $ or $ p-7$. If $p\equiv \pm 1 \bmod 8$, then let $q =12\pm 5$. Then $\left( \frac 2p \right) = \left( \frac 2q\right)=+1$. Furthermore, if $p\equiv \pm 3 \bmod 8$, then let $q=4\mp 1$. Then $\left( \frac 2p \right) =\left( \frac 2q \right)=-1$. Therefore, $\left( \frac 2p \right) =(-1)^{\frac{p^2-1}{8}}$, so $(2S)$ holds.

Lastly, if $p=q+4A$, then \begin{align*} \left( \frac pq \right)&=\left( \frac{q+4A}{q}\right) \\ &=\left( \frac Aq \right) \\ &= \textrm{sgn}(A)^{\frac{p-q}{2}}\left( \frac Ap \right) \\ &=\textrm{sgn}(A)^{\frac{p-q}{2}}\left( \frac {-p+4A}{p}\right)\\ &=\textrm{sgn}(A)^{\frac{p-q}{2}}\left( \frac {-q}{p}\right) \\ &=\textrm{sgn}(A)^{\frac{p-q}{2}}(-1)^{\frac{p-1}{2}}\left( \frac qp \right) (*) \end{align*} If $A<0$, then we get $\textrm{sgn}(A)=-1$, so $\textrm{sgn}(A)^{\frac{p-q}{2}}(-1)^{\frac{p-1}{2}}=(-1)^{\frac{q-1}{2}}$. Otherwise, $\textrm{sgn}(A)^{\frac{p-q}{2}}(-1)^{\frac{p-1}{2}}=(-1)^{\frac{p-1}{2}}$. Since $p\equiv q \bmod 4$, know know $\frac{p-1}{2}\equiv\frac{q-1}{2}\equiv \frac{p-1}{2}\frac{q-1}{2}\bmod 2$, and therefore, ($*$) becomes $$\left( \frac pq \right) = (-1)^{\frac{(p-1)(q-1)}{4}}\left( \frac qp \right)$$

Similarly, if $p=-q+4A$, we know $A>0$. Also, we have either $p\equiv 1 \bmod 4$ or $q\equiv 1 \bmod 4$, so $\frac{(p-1)(q-1)}{4}$ is even. Then \begin{align*} \left( \frac pq \right) &=\left( \frac{-q+4A}{q}\right) \\ &=\left( \frac Aq \right) \\ &=\left( \frac Ap \right) \\ &=\left( \frac {-p+4A}{p}\right) \\ &=\left( \frac qp \right) \\ &=(-1)^{\frac{(p-1)(q-1)}{4}}\left( \frac qp \right) \end{align*} so $(QR)$ holds.


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.