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.
Number Theory – Existence of Consecutive Quadratic Residues
number theory
Best Answer
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).