More on Legendre symbol

From Legendre symbol: An exact sequence point of view we know that the Legendre symbol is the unique group homomorphism $U_p\to \{-1,1\}$$U_p\to\{-1,1\}$.

In this blog, we would like to introduce some useful fact about it.

Proposition.

$$\begin{array}{c}\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}=\{\begin{array}{l}1,p\equiv 1\mathrm{mod}4\\ -1,p\equiv 3\mathrm{mod}4\end{array}\end{array}$$

Firstly let me explain why we only need to consider $p\equiv 1\mathrm{mod}4$$p\equiv 1\mod 4$ or $p\equiv 3\mathrm{mod}4$$p\equiv 3\mod 4$.

Since $p\ge 3$$p\ge 3$, $p$$p$ has to be odd number. If $p\equiv 0\mathrm{mod}4$$p\equiv 0\mod 4$ or $p\equiv 2\mathrm{mod}4$$p\equiv 2\mod 4$, then obviously $p$$p$ is even number.

Proof.

If $p\equiv 1\mathrm{mod}4$$p\equiv 1\mod 4$, $p=4k+1$$p=4k+1$

$$\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}=(-1{)}^{\frac{4k+1-1}{2}}=(-1{)}^{2k}=1$$

If $p\equiv 3\mathrm{mod}4$$p\equiv 3\mod 4$

$$\left(\frac{-1}{p}\right)=(-1{)}^{\frac{p-1}{2}}=(-1{)}^{2k+1}=-1◻$$

Gauss Lemma.

We already know that the Legendre symbol is nothing but $U_P\to \{-1,1\}$$U_P\to\{-1,1\}$.

We could embed $i:U_P\hookrightarrow S_{p-1}$$i:U_P\hookrightarrow S_{p-1}$. If $i(a)$$i(a)$ is an odd permutation, then $\begin{array}{c}\left(\frac{-1}{p}\right)=-1\end{array}$$\left(\frac{-1}{p}\right)=-1\\$, if $i(a)$$i(a)$ is even, then $\begin{array}{c}\left(\frac{-1}{p}\right)=1\end{array}$$\left(\frac{-1}{p}\right)=1\\$​.

As we know, $\mathrm{sign}:S_{p-1}\to \{-1,1\}$$\mathrm{sign}:S_{p-1}\to\{-1,1\}$ is defined by

$$\prod _{1\le i<i\le p-1}(aj-ai)=\mathrm{sign}(a)\prod _{1\le i<i\le p-1}(j-i)$$

Traditionaly we should consider the unit group $U_p$$U_p$, let $a\in U_p$$a\in U_p$ acts on it self, we get:​

$$\left(\begin{array}{ccccc}1& 2& 3& ...& p-1\\ a& 2a& 3a& ...& a(p-1)\end{array}\right)$$

But we already know that

$$\left(\frac{a}{p}\right)\equiv a^{\frac{p-1}{2}}\mathrm{mod}p$$

Hence let us consider the $a\in U_p$$a\in U_p$ acts on $\begin{array}{c}S=\{1,2,3,...,\frac{p-1}{2}\}\end{array}$$S=\left\{1,2,3,...,\frac{p-1}{2}\right\}\\$ and see what happens.

Let us rewrite the set $\{1,2,3,...,p-1\}$$\{1,2,3,...,p-1\}$ to $\{-\frac{p-1}{2},...,-1,1,...,\frac{p-1}{2}\}$$\{-\frac{p-1}{2},...,-1,1,...,\frac{p-1}{2}\}$

Hence

$$\{a,2a,3a,...,a\frac{p-1}{2}\}\equiv \{\pm s_1,\pm s_2,\pm s_3,...,\pm s_{\frac{p-1}{2}}\}$$

Where $\begin{array}{c}{s}_k\in \{1,2,3,...,\frac{p-1}{2}\}\end{array}$$s_k\in\left\{1,2,3,...,\frac{p-1}{2}\right\}\\$ . Since the acttion is faithful, or image that ${\mathbb{F}}_{\mathbb{p}}$$\mathbb{F_p}$ as a one dimensional vector space,

then $v_1\ne \pm v_2⟹a{v}_1\ne \pm a{v}_2$$v_1\ne \pm v_2\implies a v_1\ne\pm av_2$, since $a$$a$ is invertible.

Then we claim that:

$$\{s_1,...,s_{\frac{p-1}{2}}\}=\{1,...,\frac{p-1}{2}\}$$

Let $\begin{array}{c}\mu =\left|\{x\in S|ax\ge \frac{p}{2}\}\right|\end{array}$$\mu=\left|\left\{x\in S|ax\ge \frac{p}{2} \right\}\right|\\$. The Gauss Lemma tell us that

$$\left(\frac{a}{p}\right)=(-1{)}^{\mu }$$

Proof.

Since

$$\{a,2a,3a,...,a\frac{p-1}{2}\}\equiv \{\pm s_1,\pm s_2,\pm s_3,...,\pm s_{\frac{p-1}{2}}\}$$

Take the product both sides, we get

$$a^{\frac{p-1}{2}}\left(\frac{p-1}{2}\right)!\equiv (-1{)}^{\mu }{s}_1...s_{\frac{p-1}{2}}\equiv (-1{)}^{\mu }\left(\frac{p-1}{2}\right)!\mathrm{mod}p$$

Hence

$$a^{\frac{p-1}{2}}\equiv (-1{)}^{\mu }\mathrm{mod}p$$

Proposition.

$$\begin{array}{c}\left(\frac{2}{p}\right)=(-1{)}^{\frac{p^2-1}{8}}=\{\begin{array}{l}1,p\equiv \pm 1\mathrm{mod}8\\ -1,p\equiv \pm 3\mathrm{mod}8\end{array}\end{array}$$

According to Gauss Lemma, we need to find the number that $\begin{array}{c}\frac{p-1}{2}<2k\le 2\frac{p-1}{2}\end{array}$$\frac{p-1}{2}<2k\le 2\frac{p-1}{2}\\$.

i.e

$$\frac{p-1}{4}<k\le \frac{p-1}{2}⟺\lfloor \frac{p-1}{4}\rfloor <k\le \frac{p-1}{2}$$

When $p=8k+1,8k+3,8k+5,8k+7$$p=8k+1,8k+3,8k+5,8k+7$:

$\begin{array}{c}\frac{p-1}{2}=4k,4k+1,4k+2,4k+3\end{array}$$\frac{p-1}{2}=4k,4k+1,4k+2,4k+3\\$, $\begin{array}{c}\lfloor \frac{p-1}{4}\rfloor =2k,2k,2k+1,2k+1\end{array}$$\left \lfloor \frac{p-1}{4} \right \rfloor=2k,2k,2k+1,2k+1\\$

Hence

$$\mu =\frac{p-1}{4}-\lfloor \frac{p-1}{4}\rfloor =2k,2k+1,2k+1,2k+2$$

By Gauss Lemma

$$\begin{array}{c}\left(\frac{2}{p}\right)=(-1{)}^{\frac{p^2-1}{8}}=\{\begin{array}{l}1,p\equiv \pm 1\mathrm{mod}8\\ -1,p\equiv \pm 3\mathrm{mod}8\end{array}\end{array}$$

For the proof of quadratic reciprocity law, I recommend this paper:

[1804.00199] Yet another proof of the quadratic reciprocity law (arxiv.org)