Euler’s Formulation of Quadratic Reciprocity

number theory

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?

Best Answer

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.

Related Question