# “Consecutive” square residues in odd-order finite fields

Let $\mathbb F = \mathrm{GF}(p^r)$ be finite field for $p$ an odd prime, and define \begin{align} Q &= \bigl\{ u^2 \,\big|\, u \in \mathbb F^\times \bigr\} \\ N &= \mathbb F^\times \smallsetminus Q \end{align} As $\mathbb F^\times$ is a cyclic group of even order, we have $\lvert Q \rvert = \lvert N \rvert = \tfrac{1}{2}(p^r - 1)$. A classic result of number theory for the case $r = 1$ is that $$\# \bigl\{ q \in Q \;\big|\; q+1 \in Q \bigr\} = \begin{cases} (p-5)/4, & \text{if p \equiv 1 \pmod{4}}; \\[1ex] (p-3)/4, & \text{if p \equiv 3 \pmod{4}}. \end{cases}$$ Is there a corresponding result for $r > 1$ as well, and how is it shown?

• This is known. Too busy to derive the result now, sorry. Basically you want to look at the number of solutions of the equation $x^2=1+y^2$ which is equivalent to $(x-y)(x+y)=1$. Then you use $x-y$ and $x+y$ as new variables. This is a bijective linear substitution in odd characteristic. You do need to observe what happens to the solutions, where one of the variables is zero. IIRC you just replace $p$ with $p^r$ everywhere. – Jyrki Lahtonen Apr 11 '15 at 4:43
• @JyrkiLahtonen: Thanks! I found a yet simpler, turn-the-crank sort of proof once it occurred to me that the answer might possibly be a straightforward extension of the standard result (and that the standard result might not only be well-known but might also itself be proven simply). – Niel de Beaudrap Apr 11 '15 at 6:35

We can in fact adapt a standard proof of the result for $r = 1$, such as the one presented in this answer to the related question for the integers modulo $p$. Below, let $\chi: \def\F{\mathbb F}\F \to \{-1,0,+1\}$ be the quadratic character of $\F^\times$ extended to the whole field, so that $$\chi(a) = \begin{cases} +1 & \text{for a \in Q}, \\ -1 & \text{for a \in N}, \\ 0 & \text{for a = 0}. \end{cases}$$ Let $C = \# \bigl\{ q \in Q \,\big|\, q+1 \in Q \bigr\}$: then we have $$C = \sum_{a \in \F}\Bigl(\frac{1+\chi(a)}2 \Bigr)\Bigl(\frac{1+\chi(a{+}1)}{2}\Bigr) - \frac{1}{2} - \Bigl(\frac{1 +\chi(-1)}{4}\Bigr),$$ where the first subtracted term is to correct for the $a = 0$ contribution, and the second subtracted term is to correct for the $a = -1$ contribution. Since $\lvert N \rvert = \lvert Q \rvert$, we have $$\sum_{a \in \F} \chi(a) = \sum_{a \in \F} \chi(a+1) = 0;$$ then because $\chi$ is a multiplicative homomorphism, and as $a^{-1} \in Q \iff a \in Q$, we have
\begin{align} C &= \frac{\lvert \F \rvert}{4} + \frac{1}{4}\sum_{a \in \F} \chi(a) \chi(a+1) -\frac{1}{2} - \Bigl(\frac{1 + \chi(-1)}{4}\Bigr) \\&= \frac{1}{4}\biggl[\lvert \F \rvert + \sum_{a \in \F^\times} \chi\bigl(a^{-1}(a+1)\bigr) - 2 - \Bigl(1 + \chi(-1)\Bigr)\biggr] \\&= \frac{1}{4}\biggl[ p^r - 3 - \chi(-1) + \sum_{a \in \F^\times} \chi\bigl(1+a^{-1}\bigr) \biggr] \\&= \frac{1}{4}\biggl[ p^r - 3 - \chi(-1) + \!\sum_{\! b \in \F \smallsetminus \{1\}\!\!} \chi(b) \biggr] \\&= \frac{1}{4}\Bigl[ p^r - 4 - \chi(-1) \Bigr], \end{align} which is precisely the same as for the case as $r=1$ (in which $\chi(-1) = +1$ for $p \equiv 1 \pmod{4}$ and $\chi(-1) = -1$ otherwise) except with an included exponent. In particular: as $$\chi(-1) = \begin{cases} +1 &\text{if \F\:\!{:}\:\!\mathbb Z_p is an even degree extension or p \equiv 1 \pmod{4}}; \\ -1 &\text{otherwise}, \end{cases}$$ we have $\chi(-1) = +1$ if $p^r \equiv 1 \pmod{4}$, and $\chi(-1) = -1$ otherwise. Thus we have $$C = \begin{cases} (p^r-5)/4, & \text{if p^r \equiv 1 \pmod{4}}; \\[1ex] (p^r-3)/4, & \text{if p^r \equiv 3 \pmod{4}}. \end{cases}$$