# Euler's Formulation of Quadratic Reciprocity

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?

• 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)$$ Apr 1 '20 at 2:27
• 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. Apr 1 '20 at 2:34
• 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. Apr 1 '20 at 2:52
• Evidently the specific thing I was remembering was on page 17, the "crucial property of the Jacobi symbol" Apr 1 '20 at 2:59
• I've posted an answer. I hope you can all verify its validity. 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.