Existence of Consecutive Quadratic residues

For any prime $p\gt 5$,prove that there are consecutive quadratic residues of $p$ and consecutive non-residues as well(excluding $0$).I know that there are equal number of quadratic residues and non-residues(if we exclude $0$), so if there are two consecutive quadratic residues, then certainly there are two consecutive non-residues,therefore, effectively i am seeking proof only for existence of consecutive quadratic residues. Thanks in advance.

Solution 1:

Since 1 and 4 are both residues (for any $p\ge 5$), then to avoid having consecutive residues (with 1 and 4), we would have to have both 2 and 3 as non-residues, and then we have 2 consecutive non-residues.

Thus, we must have either 2 consecutive residues or 2 consecutive nonresidues.

i.e.: 1 and 4 are both residues, so we have R * * R for the quadratic character of 1, 2, 3 and 4. However we fill in the two blanks with Rs or Ns, we will get either 2 consecutive Rs or 2 consecutive Ns.

Edited:

To show that we must actually get both RR and NN for $p\gt 5$, we consider 2 cases:

$p\equiv -1 \pmod 4$: then the second half of the list of $p-1$ Ns and Rs is the inverse of the first half (Ns become Rs and the order is reversed), so that if we have NN or RR in the first half (using the argument above) then we get the other pattern in the second half.

$p\equiv 1 \pmod 4$: then the second half of the list is the reverse of the first half. Then if there is no RR amongst the first 4, then there must be an appearance of NN, i.e. sequence begins RNNR..., and if we fill in the dots (this is where we need $p>5$ - to ensure there ARE some dots!) with Ns and Rs trying to avoid an appearance of RR, then we have to alternate ...NRNR...NR. However the sequence then ends with R, and the second half begins with R, so we eventually get RR.

(The comments about the second half of the list in the 2 cases are easy consequences of -1 being a residue or a nonresidue of p).

Solution 2:

The number of $k\in[0,p-1]$ such that $k$ and $k+1$ are both quadratic residues is equal to: $$ \frac{1}{4}\sum_{k=0}^{p-1}\left(1+\left(\frac{k}{p}\right)\right)\left(1+\left(\frac{k+1}{p}\right)\right)+\frac{3+\left(\frac{-1}{p}\right)}{4}, $$ where the extra term is relative to the only $k=-1$ and $k=0$, in order to compensate the fact that the Legendre symbol $\left(\frac{0}{p}\right)$ is $0$, although $0$ is a quadratic residue. Since: $$ \sum_{k=0}^{p-1}\left(\frac{k}{p}\right)=\sum_{k=0}^{p-1}\left(\frac{k+1}{p}\right)=0, $$ the number of consecutive quadratic residues is equal to $$ \frac{p+3+\left(\frac{-1}{p}\right)}{4}+\frac{1}{4}\sum_{k=0}^{p-1}\left(\frac{k(k+1)}{p}\right). $$ By the multiplicativity of the Legendre symbol, for $k\neq 0$ we have $\left(\frac{k}{p}\right)=\left(\frac{k^{-1}}{p}\right)$, so: $$ \sum_{k=1}^{p-1}\left(\frac{k(k+1)}{p}\right) = \sum_{k=1}^{p-1}\left(\frac{1+k^{-1}}{p}\right)=\sum_{k=2}^{p}\left(\frac{k}{p}\right)=-1,$$ and we have $\frac{p+3}{4}$ consecutive quadratic residues if $p\equiv 1\pmod{4}$ and $\frac{p+1}{4}$ consecutive quadratic residues if $p\equiv -1\pmod{4}$.

Solution 3:

An elementary proof, too: if $p>5$, at least one residue class among $\{2,5,10\}$ must be a quadratic residue, since the product of two quadratic non-residues is a quadratic residue. But every element of the set $\{2,5,10\}$ is a square-plus-one, giving at least a couple of consecutive quadratic residues among $(1,2),(4,5),(9,10)$.