For any prime p>5 proving the existence of consecutive quadratic residues and consecutive quadratic non residues

Question

This question was asked in an assignment which I am solving and I couldn't solve it.

Prove that for any prime $p>5$ there exist integers $1\leq a,b \leq p-1$ for which $\binom{a}{p}=\binom{a+1}{p}=1$ and $\binom{b}{p}=\binom{b+1}{p} =-1$.

Quadratic residues and non-residues are equal in number , if I prove that any 2 residues are consecutive then non-residues will be automatically proved consecutive.

But I am unable to prove and 2 residues to be consecutive. For theory, I am studying David M Burton's book.

Can you please help?

Answer 1

Let $p>5$. We always have $\left(\frac{1}{p}\right)=1$ and $\left(\frac{4}{p}\right)=1$. Then there are 2 cases:

Case 1: $\left(\frac{2}{p}\right)=1$ or $\left(\frac{3}{p}\right)=1$. In this case there are at least 3 quadratic residues in $\{1,2,3,4\}$. Hence there are at least $\frac{p-1}{2}-1$ quadratic non-residues and at most $\frac{p-1}{2}-3$ quadratic residues in the set $\{5,\dots,p-1\}$ (because the number of quadratic residues is equal to the number of quadratic non-residues). Thus by the pigeon hole principle, there have to be consecutive quadratic non-residues.

Case 2: $\left(\frac{2}{p}\right)=\left(\frac{3}{p}\right)=-1$. We know that $p>7$ in this case, because $3^2\equiv 2\; (7)$, but $2$ is not a quadratic residue. Thus we may look at the residue classes of $\{4,5,6,7,8,9,10\}$. If it contains consecutive quadratic residues, we are done. Otherwise, because $4$ and $9$ are squares, $\{5,6,7,8,10\}$ contains at least $4$ quadratic non-residues. This means that the set $\{1,2,3,4,5,6,7,8,9,10\}$ contains at least $6$ quadratic non-residues and at most $4$ quadratic residues. We then conclude similarly to Case 1.

Answer 2

Here is a rather interesting solution involving a bit of combinatorical tricks:

---

We wil start with some basic theory:

Lemma $(1)$:

For any odd prime $p$, there are exactly $\frac{p-1}{2}$ quadratic residues (greater than $0$) and exactly $\frac{p-1}{2}$ non-quadratic residues.

Lemma $(2)$:

For any integer $n$, $n^2$ is a quadratic residue$\pmod{p}$. in other words, $\big(\frac{n^2}{p}\big)=1$ (I used Legendre's symbol here)

Lets now start the proof!

---

Consider the residues$\pmod{p}$: $(1,2,...,p-1)$. Assign $1$ to a residue $k$ if it is a quadratic residue, and $0$ if it is not a quadratic residue. We will now get a new sequence of $1$s and $0$s out of the originl sequence.

As an example, for $p=7$ we would get $(1,2,3,4,5,6)\mapsto(1,1,0,1,0,0)$.

Observe that to prove your question, we must show that for any prime $p\geq 5$, in this sequence, there are $2$ consecutive $1$s and $2$ consecutive $0$s (at least).

Because we have a sequence of $p-1$ $1$s and $0$s and there are exactly $\frac{p-1}{2}$ $1$s and $\frac{p-1}{2}$ $0$s $($this is an implication of lemma $(1)$, because there are $\frac{p-1}{2}$ quadratic residues and $\frac{p-1}{2}$ non-quadratic residues$)$ we can easily see that if there are 2 consecutive $0$s, then there must be $2$ consecutive $1$s too.

Suppose for this prime $p$ there are no $2$ consecutive $1$s or $0$s. Then, using lemma $(2)$, because $1$ is a quadratic residue, our sequence should look like this: $(1,0,1,0,......,0)$, in other words all odd numbers from $1$ to $p-1$ are quadratic residues and all even numbers from $1$ to $p-1$ are non-quadratid residues. But using lemma $(2)$ again, we know $4$ is a quadratic residue, thus leding in a contradiction for $p\geq 5$ $(p$ must be $\geq 5$ so $4\leq p-1$).

So for $p\geq 5$ we will always find $2$ consecutive $1$s and $2$ consecutive $0$s.

Answer 3

Too long to write in the comment section.

Alternative proofs for CPCH's Case #2 where both $2$ and $3$ are nonresidues and $n\geqslant 11$.

Method A: We already have two consecutive nonresidues. Suppose we don't have two consecutive quadratic residues, then from $5$ to $p-1$ there are equal numbers of residues/nonresidues; and $(4/p)=1 \implies (5/p)=-1$, they must alternate with $-1$ and $1$, therefore $(9/p)=-1$, a contradiction.

Method B: $(2/p)(5/p)=(10/p)$, so at least one of them is equal to $1$, therefore, either $(1,2)$, or $(3,4)$, or $(9,10)$ are consecutive residues.