Exercise 3.3.18* (Probability to draw consecutive residues)

Proof.

(a)

Let $E=[[1,p-2]]$. Then $|E|=p-2$.

Write $R_{\text{++}}$ the set of integers $n\in E$ such that $n$ and $n+1$ are both quadratic residues modulo $p$, and $N_{\text{++}}=|R_{\text{++}}|$ its cardinality, and similar definitions for $R_{\text{+−}},R_{\text{−+}},R_{\text{−−}}$. So

$$\begin{array}{lll}\hfill R_{\text{++}}=\left\{n\in [[1,p-2]]\mid \left(\frac{n}{p}\right)=+1\text{ and }\left(\frac{n+1}{p}\right)=+1\right\},N_{\text{++}}=|R_{\text{++}}|,& & \hfill \\ \hfill R_{\text{+−}}=\left\{n\in [[1,p-2]]\mid \left(\frac{n}{p}\right)=+1\text{ and }\left(\frac{n+1}{p}\right)=-1\right\},N_{\text{+−}}=|R_{\text{+−}}|,& & \hfill \\ \hfill R_{\text{−+}}=\left\{n\in [[1,p-2]]\mid \left(\frac{n}{p}\right)=-1\text{ and }\left(\frac{n+1}{p}\right)=+1\right\},N_{\text{−+}}=|R_{\text{−+}}|,& & \hfill \\ \hfill R_{\text{−−}}=\left\{n\in [[1,p-2]]\mid \left(\frac{n}{p}\right)=-1\text{ and }\left(\frac{n+1}{p}\right)=-1\right\},N_{\text{−−}}=|R_{\text{−−}}|.& & \hfill \end{array}$$

As $E=R_{\text{++}}\cup R_{\text{+−}}\cup R_{\text{−+}}\cup R_{\text{−−}}$ (disjoint union),

$$N_{\text{++}}+N_{\text{+−}}+N_{\text{−+}}+N_{\text{−−}}=|E|=p-2.$$

$\text{∙}$ The union $R_{\text{++}}\cup R_{\text{+−}}$ is the set of $n\in E$ such that $n$ is a quadratic residue. Its cardinality is the number of quadratic residues in $[[1,p-2]]$, that is the number of quadratic residues in $[[1,p-1]]$, minus $s$, where $s=1$ if $p-1\equiv -1$ is a residue, $s=0$ otherwise. Since $\left(\frac{-1}{p}\right)={(-1)}^{(p-1)∕2}$, we obtain $s=\frac{1+{(-1)}^{\frac{p-1}{2}}}{2}$, and the total number of quadratic residues is $(p-1)∕2$, thus

$$N_{\text{++}}+N_{\text{+−}}=\frac{p-1}{2}-s=\frac{p-1}{2}-\frac{1+{(-1)}^{\frac{p-1}{2}}}{2}=\frac{1}{2}(p-2-{(-1)}^{\frac{p-1}{2}}).$$

$\text{∙}$ Similarly, $N_{\text{−+}}+N_{\text{−−}}$ is the number of quadratic nonresidues in $[[1,p-1]]$, minus $t$, where $t=1$ if $p-1$ is a quadratic nonresidue, $t=0$ otherwise : $t=\frac{1-{(-1)}^{\frac{p-1}{2}}}{2}$, so

$$N_{\text{−+}}+N_{\text{−−}}=\frac{1}{2}(p-2+{(-1)}^{\frac{p-1}{2}})$$

(the sum of these two results is indeed $p-2=|E|$).

$\text{∙}$ Since $1$ is a residue, $N_{\text{++}}+N_{\text{−+}}$ is the number of quadratic residues in $[[1,p-1]]$, minus $1$ :

$$N_{\text{++}}+N_{\text{−+}}=\frac{p-1}{2}-1.$$

$\text{∙}$ $N_{\text{+−}}+N_{\text{−−}}$ is the number of quadratic nonresidues in $[[2,p-1]]$, equal to the number of quadratic residues in $[[1,p-1]]$ :

$$N_{\text{+−}}+N_{\text{−−}}=\frac{p-1}{2}.$$

(b)

Let $\chi$ be the characteristic function of $R_{\text{++}}\cup R_{\text{−−}}$. If $1\le n\le p-1$, $\chi (n)=1$ if $n,n+1$ are both quadratic residues, or if $n,n+1$ are both quadratic nonresidues. Then $$\chi (n)=\frac{1}{2}\left(1+\left(\frac{n}{p}\right)\left(\frac{n+1}{p}\right)\right)$$

(if $\chi (n)=1,\left(\frac{n}{p}\right)\left(\frac{n+1}{p}\right)=1$, and $\left(\frac{n}{p}\right)\left(\frac{n+1}{p}\right)=-1$ otherwise.)

Similarly, let ${\chi }^{\prime }$ be the characteristic function of the complement $R_{\text{+−}}\cup R_{\text{−+}}$. Then $\chi (n)=1$ if exactly one of the integer $n,n+1$ is a residue, $0$ otherwise. Then ${\chi }^{\prime }(n)=1-\chi (n)$, so that

$${\chi }^{\prime }(n)=\frac{1}{2}\left(1-\left(\frac{n}{p}\right)\left(\frac{n+1}{p}\right)\right).$$

Since

$$\begin{array}{llll}\hfill |R_{\text{++}}\cup R_{\text{−−}}|& =\underset{n=1}{\overset{p-1}{\sum }}\chi (n)& \hfill & \\ \hfill |R_{\text{+−}}\cup R_{\text{−+}}|& =\underset{n=1}{\overset{p-1}{\sum }}{\chi }^{\prime }(n),& \hfill & \end{array}$$

we obtain

$$\begin{array}{llll}\hfill N_{\text{++}}+N_{\text{−−}}-N_{\text{+−}}-N_{\text{−+}}& =|R_{\text{++}}\cup R_{\text{−−}}|-|R_{\text{+−}}\cup R_{\text{−+}}|& \hfill & \\ \hfill & =\underset{n=1}{\overset{p-1}{\sum }}(\chi (n)-{\chi }^{\prime }(n)).& \hfill & \end{array}$$

Therefore

$$\begin{array}{llll}\hfill N_{\text{++}}+N_{\text{−−}}-N_{\text{+−}}-N_{\text{−+}}& =\underset{n=1}{\overset{p-1}{\sum }}(\chi (n)-{\chi }^{\prime }(n))& \hfill & \\ \hfill & =\frac{1}{2}\underset{n=1}{\overset{p-1}{\sum }}\left(1+\left(\frac{n(n+1)}{p}\right)\right)-\left(1-\left(\frac{n(n+1)}{p}\right)\right)& \hfill & \\ \hfill & =\underset{n=1}{\overset{p-1}{\sum }}\left(\frac{n(n+1)}{p}\right)& \hfill & \end{array}$$

By Problem 17,

$$\underset{n=1}{\overset{p-1}{\sum }}\left(\frac{n(n+1)}{p}\right)=\underset{n=1}{\overset{p}{\sum }}\left(\frac{n(n+1)}{p}\right)=s(1,p)=-1.$$

Therefore

$$N_{\text{++}}+N_{\text{−−}}-N_{\text{+−}}-N_{\text{−+}}=\underset{n=1}{\overset{p-1}{\sum }}\left(\frac{n(n+1)}{p}\right)=-1.$$

(c)

To summarize the results of parts (a) and (b), $$\begin{array}{lll}\hfill N_{\text{++}}+N_{\text{+−}}+N_{\text{−+}}+N_{\text{−−}}& =p-2& \hfill \text{(1)}\\ \hfill N_{\text{++}}+N_{\text{−−}}-N_{\text{+−}}-N_{\text{−+}}& =-1& \hfill \text{(2)}\end{array}$$

and

$$\begin{array}{lll}\hfill N_{\text{++}}+N_{\text{+−}}& =\frac{1}{2}\left(p-2-{(-1)}^{\frac{p-1}{2}}\right)& \hfill \text{(3)}\\ \hfill N_{\text{++}}+N_{\text{−+}}& =\frac{p-1}{2}-1& \hfill \text{(4)}\end{array}$$

The sum of (1) and (2) gives

$$\begin{array}{lll}\hfill N_{\text{++}}+N_{\text{−−}}=\frac{p-3}{2}.& & \hfill \text{(5)}\end{array}$$

The sum of (3), (4), (5) gives, using (1),

$$2N_{\text{++}}+p-2=\frac{p-2}{2}+\frac{p-1}{2}+\frac{p-3}{2}-1-\frac{{(-1)}^{\frac{p-1}{2}}}{2},$$

thus

$$\begin{array}{llll}\hfill 2N_{\text{++}}& =\frac{p-1}{2}+\frac{p-3}{2}-\frac{p-2}{2}-1-\frac{{(-1)}^{\frac{p-1}{2}}}{2}& \hfill & \\ \hfill & =\frac{p}{2}-2-\frac{{(-1)}^{\frac{p-1}{2}}}{2}.& \hfill & \end{array}$$

So

$$\begin{array}{lll}\hfill N_{\text{++}}& =\frac{1}{4}\left(p-\left(\frac{-1}{p}\right)-4\right).& \hfill \text{(6)}\end{array}$$

(d)

Then, by equations (5) and (6), $$\begin{array}{llll}\hfill N_{\text{−−}}& =\frac{p-3}{2}-\frac{1}{4}\left(p-\left(\frac{-1}{p}\right)-4\right)& \hfill & \\ \hfill & =\frac{1}{4}\left(p+\left(\frac{-1}{p}\right)-2\right).& \hfill & \end{array}$$

By equations (3) and (6),

$$\begin{array}{llll}\hfill N_{\text{+−}}& =\frac{1}{2}\left(p-2-\left(\frac{-1}{p}\right)\right)-\frac{1}{4}\left(p-\left(\frac{-1}{p}\right)-4\right)& \hfill & \\ \hfill & =\frac{1}{4}\left(p-\left(\frac{-1}{p}\right)\right).& \hfill & \end{array}$$

Finally, by equations (4) and (6),

$$\begin{array}{llll}\hfill N_{\text{−+}}& =\frac{p-3}{2}-\frac{1}{4}\left(p-\left(\frac{-1}{p}\right)-4\right)& \hfill & \\ \hfill & =\frac{1}{4}\left(p+\left(\frac{-1}{p}\right)-2\right).& \hfill & \end{array}$$

In summary,

$$\begin{array}{llll}\hfill N_{\text{++}}& =\frac{1}{4}\left(p-\left(\frac{-1}{p}\right)-4\right),& \hfill & \\ \hfill N_{\text{−−}}& =\frac{1}{4}\left(p+\left(\frac{-1}{p}\right)-2\right),& \hfill & \\ \hfill N_{\text{+−}}& =\frac{1}{4}\left(p-\left(\frac{-1}{p}\right)\right),& \hfill & \\ \hfill N_{\text{−+}}& =\frac{1}{4}\left(p+\left(\frac{-1}{p}\right)-2\right).& \hfill & \end{array}$$