Proportion of non-quadratic residues when added by 1 are still non-quadratic residues

Question

Let $p$ be a prime. I am interested in the set of elements $x\in\mathbb{Z}/p\mathbb{Z}$ such that $x$ and $x+1$ are both quadratic non-residues. Let $N_p$ be the number of such elements. I want to calculate $\lim_{p\rightarrow\infty}N_p/p$. Where to begin? More generally, what kind of tools are available to study questions like this, where I am interested in proportions of elements in $\mathbb{Z}/p\mathbb{Z}$ satisfying certain properties, as $p\rightarrow \infty$?

Answer 1

Let $c$ be a quadratic non-residue. Then $x$ and $x+1$ are both quadratic non-residues iff $cx$ and $c(x+1)$ are both quadratic residues (nonzero squares modulo $c$). If so then $xc\equiv a^2$ and $x(c+1)\equiv b^2\pmod p$, so that $$b^2-a^2\equiv c\pmod p.\tag{1}$$ Let $M_p$ be the number of solutions of $(1)$ in the integers modulo $p$.

A solution of $(1)$ with $a$, $b\not\equiv0\pmod p$ will give rise to an $x$ with $x$ and $x+1$ both quadratic non-residues, and if we multiply $a$ or $b$ by $-1$ we get the same $x$. So the number of nonzero solutions of $(1)$ is $4N_p$. But $(1)$ has no solutions with $a\equiv0$ as $c$ is a non-residue but it may have solutions with $b=0$, precisely when $-1$ is a non-residue, that is when $p\equiv3\pmod 4$. So $M_p=4N_p$ or $M_p=4N_p+2$ according to whether $p\equiv1$ or $p\equiv3\pmod 4$.

But $M_p=p-1$ in all cases, since we can rewrite $(1)$ as $$(b-a)(b+a)\equiv c\pmod p.\tag2$$ Thus $b-a$ can be any number nonzero modulo $p$ and that determines $b+a$ and so both $a$ and $b$. Therefore $M_p=\frac14(p-1)$ or $\frac14(p-3)$ (whichever happens to be an integer) or simply the integer part of $p/4$.

Answer 2

To resolve this particular question (and some questions like it), here's one method.

Let $\left(\frac{x}{p}\right)$ be a Legendre symbol, so it's $0$ if $x\equiv 0\bmod p$, $1$ if $x$ is a (nonzero) quadratic residue modulo $p$, and $-1$ if it's a nonresidue. As a result, we have that $$\left(\left(\frac{x}{p}\right)-1\right)\left(\left(\frac{x+1}{p}\right)-1\right)$$ is $4$ if $x$ and $x+1$ are both nonresidues, $0$ if one of them is a positive residue, and $2$ if $(-1/p)=-1$ and $x=-1$. So, $$\sum_{x\in\mathbb F_p}\left(\left(\frac{x}{p}\right)-1\right)\left(\left(\frac{x+1}{p}\right)-1\right)$$ is $4$ times the number of $x$ so that $x$ and $x+1$ are both nonresidues, possibly plus $2$ if $-1$ is a nonresidue modulo $p$. Let $N$ be the answer that we seek.

The other tool we use is that $$\left(\frac{x}{p}\right)\equiv x^{\frac{p-1}{2}}\bmod p.$$ As a result, $$4N+1-\left(\frac{-1}{p}\right)\equiv \sum_{x\in\mathbb F_p}\left(x^{\frac{p-1}{2}}-1\right)\left((x+1)^{\frac{p-1}{2}}-1\right)\bmod p.$$ Let's evaluate the sum on the right. For $p-1\nmid k$, we have $$\sum_{x\in\mathbb F_p} x^k\equiv\sum_{j=0}^{p-2}g^{kj}\equiv\frac{g^{(p-1)k}-1}{g^k-1}\equiv 0\bmod p,$$ where $g$ is a primitive root modulo $p$, and the same result is true when $k=0$. When $k$ is a positive multiple of $p$, the result is $-1$. As a result, when we expand out the polynomial on the right side of the above congruence, every term that is of degree $<p-1$ is unimportant, and so the sum on the right is simply $-1$. As a result, $$4N+1-\left(\frac{-1}{p}\right)\equiv -1\bmod p\implies N\equiv \frac{p-2+\left(\frac{-1}{p}\right)}{4}\bmod p.$$ However, $N$ is clearly between $0$ and $p-1$ (inclusive), and the right side is an integer between these two values. There are no other integers congruent to the right side modulo $p$ that are between $0$ and $p-1$, and so $$N=\frac{p-2+\left(\frac{-1}{p}\right)}{4}=\left\lfloor\frac{p}{4}\right\rfloor.$$

---

Similar techniques can work for cubes, if you note that $$x^{\frac{2(p-1)}{3}}+x^{\frac{p-1}{3}}+1$$ is $3$ if $x$ is a cubic residue and $0$ otherwise (and of course $1$ at $0$), as well as other powers if you like, but the sums become messier and more complicated.