Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
That there are consecutive residues (excluding 0) requires $p \gt 5$. The observation about equal numbers of residues and non-residues should probably be supplemented with an argument about whether $-1$ is a residue or not. E.g. why cannot we have 2,3 consecutive non-residues, but then alternating residues and non-residues to fill out the remaining classes? –  hardmath Jun 30 '12 at 9:55
add comment

3 Answers

up vote 9 down vote accepted

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).

share|improve this answer
    
The problem asks about two consecutive residues and two consecutive non-residues. The answer seems to deal with or. –  André Nicolas Jun 30 '12 at 14:55
    
In that case the result is surely wrong, as in the case $p=5$, there are two consecutive non-residues, but there are not two consecutive residues. –  Old John Jun 30 '12 at 14:59
    
But if $p\gt 5$ it is true. My proof (from a Number Theory set of notes I wrote) takes some time, uses as Lemma fact that sum of Legendre symbols $(a(a+1)/p)$, $a=1$ to $p-2$, is $-1$. –  André Nicolas Jun 30 '12 at 15:13
    
See my comment under the question. –  hardmath Jun 30 '12 at 15:14
    
@Andre - Agreed about $p>5$, and I suspect there might be a more elementary proof (I am working on it). –  Old John Jun 30 '12 at 15:19
show 1 more comment

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)$.

share|improve this answer
add comment

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}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.