Jacobi symbols for two-square sums of primes

Question

Given a prime $p\equiv 1\pmod 4$, Fermat's two-squares theorem discovered by Girard states that there exists two integers $A,B$ such that $p=A^2+B^2$.

For all primes up to $10^7$ the integers $A$ and $B$ are squares modulo $p$ if $p\equiv 1\pmod 8$ and they are fourth powers modulo $p$ if $p\equiv 1\pmod {16}$. This pattern breaks then down: $A$ and $B$ are not necessarily $8$-th powers modulo $p$ for primes $p\equiv 1\pmod{32}$.

Is there an explanation (proof or reference) for these observations? Is there an explanation why they fail to carry on?

Details: We start with $p=A^2+B^2\equiv 1\pmod{4}$. Since we have obviously $(A/B)^2\equiv -1\pmod p$ this implies that $\left(\frac{AB}{p}\right)=(-1)^{(p-1)/4}$ with $\left(\frac{x}{p}\right)$ denoting the Jacobi-symbol (which equals $1$ on non-zero squares and $-1$ on non-squares in $\mathbb F_p$).

This shows that $\left(\frac{A}{p}\right)=\left(\frac{B}{p}\right)$ if $p\equiv 1\pmod 8$. Surprisingly, negative Jacobi-symbols do not occur for small primes and we have $\left(\frac{A}{p}\right)=\left(\frac{B}{p}\right)=1$ for all 165976 primes $p\equiv 1\pmod 8$ up to $10^7$.

Given a prime $p=A^2+B^2\equiv 1\pmod 8$ with $\left(\frac{A}{p}\right)=\left(\frac{B}{p}\right)=1$ we can choose square roots $a,b$ of $A\equiv a^2\pmod p$ and $B\equiv b^2\pmod p$. We have then $(ab^{-1})^4\equiv -1\pmod p$ which shows $\left( \frac{ab}{p}\right)\equiv (-1)^{(p-1)/8}$ and we get therefore $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)$ if $p\equiv 1\pmod{16}$. (The choice of initial signs for $A,B$ and the choice between the two possible square-roots for $a$ or $b$ do not change the values of the Jacobi-symbols.)

We get again $\left(\frac{a}{p}\right)=\left(\frac{b}{p}\right)=1$ for all 82967 primes $p\equiv 1\pmod{16}$ up to $10^7$ and we can then choose square roots $\alpha,\beta$ of $a\equiv \alpha^2\pmod{p}$ and $b\equiv \beta^2\pmod{p}$ (or, equivalently, fourth-roots of $A\equiv \alpha^4\pmod p$ and $B\equiv \beta^4\pmod p$ where $p=A^2+B^2\equiv 1\pmod{16}$). We have again $\left(\frac{\alpha\beta}{p}\right)=(-1)^{(p-1)/16}$.

We have therefore $\left(\frac{\alpha}{p}\right)=\left(\frac{\beta}{p}\right)$ if $p\equiv 1\pmod{32}$.

The pattern observed experimentally above breaks down at this point. We have for example

$193=7^2+12^2$ with $83^4\equiv 7\pmod{193},\ 75^4\equiv 12\pmod{193}$ and $\left(\frac{83}{193}\right)=\left(\frac{75}{193}\right)=1$,

$673=12^2+23^2$ with $194^4\equiv 12\pmod{673},\ 206^4\equiv 23\pmod{673}$ and $\left(\frac{194}{673}\right)=\left(\frac{206}{673}\right)=1$

but we have

$97=4^2+9^2$ with $14^4\equiv 4\pmod{97},\ 10^4\equiv 9\pmod{97}$ and $\left(\frac{14}{97}\right)=\left(\frac{10}{97}\right)=-1$,

$1153=8^2+33^2$ with $425^4\equiv 8\pmod{1153},\ 269^4\equiv 33\pmod{1153}$ and $\left(\frac{425}{1153}\right)=\left(\frac{269}{1153}\right)=-1$.

(More precisely, there are 41453 primes congruent to $1\pmod {32}$ up to $10^7$. These primes yield 20613 times $\left(\frac{\alpha}{p}\right)=\left(\frac{\beta}{p}\right)=1$. Both Jacobi-symbols are equal to $-1$ for the remaining 20840 primes congruent to $1\pmod{32}$ up to $10^7$.)

Answer 1

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 give three proofs (which actually yield more than we need).

First proof. I will use some results of Gauss, Jacobi, and Eisenstein collected in Section III.13.5 of Hasse's 1965 book: Bericht über neuere Untersuchungen und Probleme aus der Theorie der algebraischen Zahlkörper, Teil II: Reziprozitätsgesetz. Assume that $p\equiv 1\pmod{16}$. Without loss of generality, $A$ is odd and $B$ is even. As $A/B$ is a square-root of $-1$ modulo $p$, it has order four modulo $p$, hence it is actually a fourth power modulo $p$. Therefore, it suffices to show that $B$ is a fourth power modulo $p$. Let us write $B=2^k B'$, where $k\geq 2$ and $B'$ is odd. By the results in Hasse's book, every prime divisor of $B'$ is a fourth power modulo $p$, hence $B'$ is a fourth power modulo $p$. It remains to show that $2^k$ is a fourth power modulo $p$. If $k\geq 3$, then $2$ is a fourth power modulo $p$ (see Hasse's book), hence we are done. If $k=2$, then we are also done upon noting that $2$ is a quadratic residue modulo $p$.

Second proof. This proof is based on the properties of the quartic residue symbol in $\mathbb{Z}[i]$. I will rely on Chapter 9 of Ireland-Rosen: A classical introduction to modern number theory (2nd ed.), especially Theorem 2, Proposition 9.8.5, and Proposition 9.8.6 there. Assume that $p\equiv 1\pmod{16}$. There are $8$ pairs representing $p$, hence we can assume that our pair $(A,B)$ is the one with $$A\equiv 1\pmod{8}\qquad\text{and}\qquad B\equiv 0\pmod{4}.$$ As $A/B$ is a square-root of $-1$ modulo $p$, it has order four modulo $p$, hence it is actually a fourth power modulo $p$. Therefore, it suffices to show that $A$ is a fourth power modulo $p$. Equivalently, $A$ is a fourth power in $\mathbb{Z}[i]/(A+Bi)$. However, this follows from the law of quartic reciprocity and the conditions on $(A,B)$: $$\left(\frac{A}{A+Bi}\right)_4=\left(\frac{A+Bi}{A}\right)_4 =\left(\frac{Bi}{A}\right)_4=\left(\frac{i}{A}\right)_4=(-1)^{(A-1)/4}=1.$$

Third proof. 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 the "Added" section below. 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_{j=1}^\nu(2a_j)\prod_{j=\nu+1}^n(p-2a_j)=\prod_{j=1}^n a_j.$$ 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 determine $a\bmod p$ using 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)$.

Answer 2

It is not an answer but a comment to GH from MO's answer.

As I understand, Jacobstahl proved Gauss's congruences in a more direct way. He didn't use Jacobi sums. In Jacobstahl's representation $p=A^2+B^2$ numbers $A$ and $B$ are expressed in terms of sums of Legendre symbols: $$2A=\sum_{x=1}^{p-1}\left(\frac{x^3+rx}p\right),\quad 2B=\sum_{x=1}^{p-1}\left(\frac{x^3+nx}p\right),$$ where $r$ and $n$ are quadratic residue and non-residue modulo $p$. From these representations desired congruences follow directly. For $r=1$ $$\begin{split}2A\equiv\sum_{x=1}^{p-1}\left({x^3+x}\right)^{\frac{p-1}2}\equiv\sum_{k=1}^{p-1}\left({g^{3k}+g^k}\right)^{\frac{p-1}2}\equiv\sum_{j=0}^{(p-1)/2}\binom{(p-1)/2}{j}\sum_{k=1}^{p-1}(g^{3k})^{j}(g^k)^{\frac{p-1}{2}-j}\\\equiv\sum_{j=0}^{(p-1)/2}\binom{(p-1)/2}{j}\sum_{k=1}^{p-1}g^{k\left(2j+\frac{p-1}{2}\right)}\pmod p.\end{split}$$ The inner sum is not zero modulo $p$ iff $2j+\frac{p-1}2=p-1,$ or $j=\frac{p-1}4$. So $2A\equiv \binom{(p-1)/2}{(p-1)/4}.$ Also we know that $(A/B)^2\equiv -1\pmod p$, hence $B\equiv \pm (\frac{p-1}2)!A.$