Distribution of Quadratic Residues

Question

Let $N_1(p)$ denotes the number of pairs of consecutive integers in $[1,p-1]$ in which the first is a quadratic residue and the second is a quadratic nonresidue modulo $p$. Prove that:
$$N_1(p)=\frac{1}{4}(p-(-1)^{\frac{(p-1)}{2}})$$

My thoughts:
I know that $N(p)=\frac{1}{4}(p-4-(-1)^\frac{(p-1)}{2})$ is the number of pairs of consecutive quadratic residues modulo p in $[1,p-1]$. And in I'm assuming I have to do manupluation to this formula to narrow it down to the pairs of quadratic residues where the first is and the first is not. However, I am stuck in figuring out what first move to make.

Answer 1

For $0 \leq i, j \leq 1$, define $A_{ij}=\{k \in \{1, 2, \ldots , p-2\}: (\frac{k}{p})=(-1)^i, (\frac{k+1}{p})=(-1)^j\}$. Let $|A_{ij}|=a_{ij}$. Then you want to count $N_1(p)=a_{01}$.

---

$a_{11}+a_{10}+a_{01}+a_{00}=p-2$ (Total number of pairs is $p-2$)

$a_{00}+a_{10}$ is the number of quadratic residues from $2$ to $p-1$, so $a_{00}+a_{10}=\frac{p-1}{2}-1=\frac{p-3}{2}$.

$a_{11}+a_{01}=p-2-\frac{p-3}{2}=\frac{p-1}{2}$.

If $k, k+1$ are both quadratic nonresidues, then $(\frac{k^{-1}}{p})=(\frac{k^{-1}}{p})(\frac{k}{p})^2=(\frac{k}{p})=-1$ and $(\frac{k^{-1}+1}{p})=(\frac{k^{-1}+1}{p})(\frac{k}{p})^2=(\frac{k+1}{p})(\frac{k}{p})=1$, so $k^{-1}$ is a quadratic non-residue and $k^{-1}+1$ is a quadratic residue. Also, for $k \in \{1, 2, \ldots , p-2\}$, we have $k^{-1} \in \{1, 2, \ldots , p-2\}$.

We get a bijection between $A_{11}$ and $A_{10}$, so $a_{11}=a_{10}$.

It now helps to consider $p \equiv 1 \pmod{4}$ and $p \equiv 3 \pmod{4}$ seperately:

---

$p \equiv 1 \pmod{4}$:

$(\frac{-x}{p})=(\frac{-1}{p})(\frac{x}{p})=(\frac{x}{p})$

Then if $k$ is a quadratic residue and $k+1$ is a quadratic non-residue, then $p-i-1$ is a quadratic non-residue and $p-k=(p-k-1)+1$ is a quadratic non-residue. Also, for $k \in \{1, 2, \ldots , p-2\}$, we have $p-k-1 \in \{1, 2, \ldots , p-2\}$.

We get a bijection between $A_{01}$ and $A_{10}$, so $a_{01}=a_{10}$.

Thus $a_{11}=a_{10}=a_{01}=\frac{a_{11}+a_{01}}{2}=\frac{p-1}{4}$ and $a_{00}=\frac{p-1}{2}-a_{10}=\frac{p-3}{2}-\frac{p-1}{4}=\frac{p-5}{4}$.

---

$p \equiv 3 \pmod{4}$:

$(\frac{-x}{p})=(\frac{-1}{p})(\frac{x}{p})=-(\frac{x}{p})$

Then if $k, k+1$ are both quadratic residues, then $p-k-1$ and $p-k=(p-k-1)+1$ are both quadratic non-residues. Also, $1 \leq k \leq p-2$ implies $1 \leq p-k-1 \leq p-2$.

We thus have a bijection between $A_{00}$ and $A_{11}$, so $a_{00}=a_{11}$.

Thus $a_{00}=a_{11}=a_{10}=\frac{a_{00}+a_{10}}{2}=\frac{p-3}{4}$ and $a_{01}=\frac{p-1}{2}-a_{11}=\frac{p-1}{2}-\frac{p-3}{4}=\frac{p+1}{4}$.

---

We can combine the results to get \begin{cases} a_{00}=\frac{1}{4}(p-4-(-1)^{\frac{p-1}{2}}) \\ a_{01}=\frac{1}{4}(p-(-1)^{\frac{p-1}{2}}) \\ a_{10}=\frac{1}{4}(p-2+(-1)^{\frac{p-1}{2}}) \\ a_{11}=\frac{1}{4}(p-2+(-1)^{\frac{p-1}{2}}) \\ \end{cases}