Skip to main content
11 of 18
deleted 8 characters in body
GH from MO
  • 105.3k
  • 8
  • 293
  • 398

The first observation follows from the law of quadratic reciprocity. Indeed, assume that $p\equiv 1\pmod{8}$ and $p=A^2+B^2$. Let $A'$ denote the odd part of $A$. Then $p\equiv B^2\pmod{A'}$, and hence $\left(\frac{p}{A'}\right)=1$. It follows that $\left(\frac{A'}{p}\right)=1$, and then by $\left(\frac{2}{p}\right)=1$ also $\left(\frac{A}{p}\right)=1$. In the same way, $\left(\frac{B}{p}\right)=1$.

The second observation lies deeper. I will use Gerry Myerson's helpful comment below the original post. For any prime $p=4n+1$, Gauss (1825) observed that $p=A^2+B^2$, where $A$ and $B$ are the absolute least residues modulo $p$ of $(2n)!/(2n!^2)$ and $(2n)!^2/(2n!^2)$. For a proof, see Jacobsthal (1907) or Barnes (1974). Hence it suffices to show that in case when $4$ divides $n$, these two integers are fourth powers modulo $p$. So let us assume that $4\mid n$. By Wilson's theorem, $$(2n)!^{(p-1)/4}=(2n)!^{n}\equiv(p-1)!^{n/2}\equiv(-1)^{n/2}=1\pmod{p},$$ hence $(2n)!$ is a fourth power modulo $p$. So we only need to prove that $2n!^2$ is a fourth power modulo $p$. Equivalently, $$2^{(p-1)/4}n!^{(p-1)/2}\equiv 1\pmod{p}.\tag{1}$$ However, this follows from Theorem 5 in Emma Lehmer's 1977 paper "Generalizations of Gauss's lemma", and we are done.

For completeness, I spell out the proof of $(1)$. We observe that $n!^{(p-1)/2}\equiv(-1)^\nu\pmod{p}$, where $\nu$ is the number of quadratic non-residues in $[1,n]$. Hence $(1)$ is equivalent to $$2^n(-1)^\nu\equiv 1\pmod{p}.\tag{2}$$ To see this, let $a_1,\dotsc,a_\nu$ be the quadratic non-residues in $[1,n]$, and let $a_{\nu+1},\dotsc,a_n$ be the quadratic non-residues in $[n+1,2n]$. Then $2a_1,\dotsc,2a_\nu$ are the even quadratic non-residues in $[2,2n]$, and $p-2a_{\nu+1},\dotsc,p-2a_n$ are the odd quadratic non-residues in $[1,2n-1]$. It follows that $$\prod_{i=1}^\nu(2a_i)\prod_{i=\nu+1}^n(p-2a_i)=\prod_{i=1}^n a_i.$$ Taking residues modulo $p$ on both sides, we obtain after simplification that $$2^\nu(-2)^{n-\nu}\equiv 1\pmod{p}.$$ This is equivalent to $(2)$, because $n$ is even.

Added. To make this post more self-contained, I provide a proof of Gauss's observation $p=A^2+B^2$, using Jacobi sums. Here $A$ and $B$ are the absolute least residues modulo $p$ of $(2n)!/(2n!^2)$ and $(2n)!^2/(2n!^2)$. I will rely on Chapter 8 of Ireland-Rosen: A classical introduction to modern number theory (2nd ed.), especially Theorem 1, Theorem 5, and Exercise 26 there.

Let $\chi$ be a character of order four on $\mathbb{F}_p^\times$, and let $\rho$ be the Legendre symbol on $\mathbb{F}_p^\times$. The number of solutions of $x^4+y^2=1$ over $\mathbb{F}_p$ can be expressed via Jacobi sums as \begin{align*} N&=p+J(\chi,\rho)+J(\chi^2,\rho)+J(\chi^3,\rho)\\ &=p+J(\chi,\rho)+J(\rho,\rho)+\overline{J(\chi,\rho)}\\ &=p-1+2a, \end{align*} where $J(\chi,\rho)=a+bi\in\mathbb{Z}[i]$. Note that $$p=|J(\chi,\rho)|^2=a^2+b^2.\tag{3}$$ The count $N$ can also be evaluated as $$N=\sum_{x=0}^{p-1}(1+\rho(1-x^4))=p+\sum_{x=0}^{p-1}\rho(1-x^4).$$ Now we express $a\bmod p$ from the two expressions for $N$. Recalling that $n=(p-1)/4$, $$2a-1=\sum_{x=0}^{p-1}\rho(1-x^4)\equiv\sum_{x=0}^{p-1}(1-x^4)^{2n}\pmod{p}.$$ We expand $(1-x^4)^{2n}$ by the binomial theorem: $$2a-1\equiv\sum_{m=0}^{2n}(-1)^m\binom{2n}{m}\sum_{x=0}^{p-1}x^{4m}\pmod{p}.$$ The inner sum on the right-hand side is $-1\bmod p$ when $m\in\{n,2n\}$, and $0\bmod p$ otherwise. As a result, $$2a\equiv(-1)^{n+1}\binom{2n}{n}\pmod{p}.$$ From here it is straightforward that $|a|=|A|$ and $|b|=|B|$, hence $p=A^2+B^2$ by $(3)$.

GH from MO
  • 105.3k
  • 8
  • 293
  • 398