A particular case of the quadratic reciprocity law

Solution 1:

If $p=8k+1$ then consider $a$ with $a^{4k}\equiv-1$ (mod $p$). Let $b=a^k-a^{7k}$. Then $$b^2=a^{2k}-2a^{8k}+a^{14k}\equiv a^{2k}(1+a^{4k})-2 \equiv-2\pmod{p}.$$ For $p\equiv3$ (mod $8$) this argument will also work but you need to use the Galois field $GF(p^2)$ rather than the integers modulo $p$.

Solution 2:

Similar arguments work for other cases as well. For example, if $p = 1 \mod 3k$, find $a$ such that $a^{3k}=1$ and $a^k \neq 1$. Set $z=a^k$, then $z^2+z+1=0$ and we deduce that $(z - z^2)^2 = -3$.

For a larger example, if $p=5k+1$, then there is an $a$ in $\mathbb{F}_p$ with $a^{5k}=1$ and $a^k \neq 1$. Let $z=a^k$, so $z^4+z^3+z^2+z+1=0$.

Let $b = z - z^2 - z^3 + z^4$. Then $$b^2 = z^8 - 2 z^7 - z^6 + 4 z^5 - z^4 - 2 z^3 + z^2=$$ $$-z^4 - z^3 - z^2 - z + 4 = 5.$$

So $p \equiv 1 \mod 5$ implies that $\left( \frac{5}{p} \right)=1$. Just as in Robin's answer, you can also prove that $p \equiv 4 \mod 5$ implies $\left( \frac{5}{p} \right)=1$ in this manner, but it is more difficult: the element $z$ will live in $\mathbb{F}_{p^2}$, and you will need to check that $b$ lives in $\mathbb{F}_{p}$.

In fact, for every squarefree $M$, let $\Delta$ be $|M|$ if $M \equiv 1 \mod 4$ and $\Delta=4 |M|$ otherwise. Then you can prove in this manner the statement "if $p = 1 + \Delta k$ then $\left( \frac{\Delta}{p} \right) = 1$." The first steps are the same in each case: find $a$ in $\mathbb{F}_p$ such that $a^{\Delta k}=1$ but $a^{d k} \neq 1$ for any proper divisor $d$ of $\Delta$. Let $z=a^k$, so $z$ is a primitive $\Delta$ root of unity in $\mathbb{F}_p$. At this point, some magic polynomial $g_M$ is introduced, such that $g_M(z)^2 = M$. If you want to prove the full quadratic reciprocity law, you can do so using this approach as well, but you will need to work in finite fields of non-prime order.

I often thought it would be fun to assign a class the job of finding the magic polynomials $g_M$, for various values of $M$, and see if they could guess the general pattern. Hint: $g$ stands for "Gauss sum".

Solution 3:

If I remember correctly, this approach with a Gauss sum (associated to an 8th root of 1 in a finite field) is used in the first page or two of Serre's Cours d'Arithmetique to determine the "supplementary law" for $\left( \frac{2}{p} \right)$. The magical algebraic identity in this case is that if $a^4 = -1$, then $(a \pm 1/a)^2 = \pm 2$.