Proving consecutive quadratic residue modulo p [duplicate]

This question already has an answer here:

Let p be a prime with p > 7. Prove that there are at least two consecutive quadratic residues modulo p. [Hint: Think about what integers will always be quadratic residues modulo p when p ≥ 7.]

marked as duplicate by user26486, user147263, Zev Chonoles, Chappers, graydadMay 5 '15 at 3:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer

Look at $0^2\pmod{p}$ and $1^2\pmod{p}$.

EDIT

If you exclude $0$, from the list of quadratic residues as some people do, the proof is as follows.

Assume that there are no consecutive quadratic residues. Note that $1$ and $4$ are quadratic residues for all $p \geq 7$. If $2$ or $3$ or $5$ are quadratic residues we are done. Hence, we can assume that $2$, $3$ and $5$ are not quadratic residues. This means that $p$ has to be greater than $7$, since $2$ is a quadratic residue $\pmod7$.

Now recall that there are $(p-1)/2$ non-zero quadratic residues of which we have accounted for $1$ and $4$. This means there are $(p-1)/2-2$ quadratic residues still left. This means the $3^{rd}$ quadratic residue must be at-least $4+2$, and in general the $k^{th}$ quadratic residue must be at-least $2k$. Hence, a simple pigeon-hole principle based argument shows that the set of quadratic residues must be $\{1,4,6,8,10,\ldots,p-1\}$. However, for $p \geq 11$, $9$ is a quadratic residue. Hence, our assumption that there are no consecutive quadratic residues is incorrect.