13
$\begingroup$

Let $p$ be an odd prime. I am interested in how many quadratic residues $a$ sre there such that $a+1$ is also a quadratic residue modulo $p$. I am sure that this number is $$ \frac{p-6+\text{mod}(p,4)}{4}, $$ but I have neither proof nor reference. It is a particular case of the question in the title: if $a$ and $b$ are quadratic residues modulo $p$, when is $a+b$ also a quadratic residue modulo $p$?

I came into this question when counting the number of diophantine $2$-tuples modulo $p$, that is, the number of pairs $\{ a,b\}\subset \mathbb{Z}^*_p$ such that $ab+1$ is a quadratic residue modulo $p$.

$\endgroup$
3
  • 4
    $\begingroup$ This is an easy consequence of the fact that $x^2+y^2=z^2$ is a curve of genus $0$ and so have exactly $p$ projective solutions. $\endgroup$
    – Siksek
    May 16, 2011 at 22:05
  • 1
    $\begingroup$ Note that your motivating problem can be solved directly. Let $q$ be any of the $(p+1)/2$ quadratic residues, and let's count the solutions of $ab+1=q$. For $q=1$ the equation is equivalent to $a=0$ or $b=0$, so there are $2p-1$ solutions. For $q\neq 1$ we have $a\neq 0$ and $b\neq 0$ which determine each other uniquely, so there are $p-1$ solutions. Altogether the number of (ordered) diophantine pairs equals $2p-1+(p-1)^2/2=(p^2+2p-1)/2$. $\endgroup$
    – GH from MO
    May 17, 2011 at 3:46
  • 1
    $\begingroup$ @GH Some of the solutions will have $a=b$, which I do not want to count. May be I was not clear about this. $\endgroup$ May 17, 2011 at 21:09

4 Answers 4

16
$\begingroup$

Here's a copy-paste of something I wrote up a while ago:

Lemma: Let $q$ be odd, and let $Q$ be the set of quadratic residues (including $0$) in $\mathbb F_q$. Then the number of elements $s_q(c)$ in $\{x^2+c|x \in \mathbb{F}_q\} \cap Q$ is given by \begin{array}{|c|c|c|} \hline & c \in Q & c \notin Q \\ \hline -1 \in Q & \frac{q+3}{4} & \frac{q-1}{4} \\ \hline -1 \notin Q & \frac{q+1}{4} & \frac{q+1}{4} \\ \hline \end{array}

Proof: If, for $x,y,c\in \mathbb{F}_q,\ c \neq 0$ we have $x^2+c=y^2$, then $c=y^2-x^2=(y-x)(y+x)$. Now for all the $q-1$ elements $d\in \mathbb{F}_q^{\ast}$, we can let $y-x=d$ and $y+x=\frac{c}{d}$. But the pairs $(d,\frac{c}{d}),(-d,\frac{c}{-d}),(\frac{c}{d},d),(\frac{c}{-d},-d)$ all give the same value of $y^2=\frac{1}{4}(d+c/d)^2$. Also, as $q$ is odd, $d\neq -d\ \forall d$. But if $c\in Q$, for $2$ values of $d$ we have $d=\frac{c}{d}$ and if $-c\in Q$, for 2 values of $d$ we have $d=\frac{c}{-d}$. So we have $$ s_q(c) = \left\{ \begin{array}{rcll} \frac{\frac{q-1}{2}-2}{2}+2 & = & \frac{q+3}{4} & if\ c\in Q,\ -c\in Q \\ \frac{\frac{q-1}{2}-1}{2}+1 & = & \frac{q+1}{4} & if\ c\in Q,\ -c\notin Q \\ \frac{\frac{q-1}{2}-1}{2}+1 & = & \frac{q+1}{4} & if\ c\notin Q,\ -c\in Q \\ & & \frac{q-1}{4} & if\ c\notin Q,\ -c\notin Q \end{array} \right. $$ and hence the result.

$\endgroup$
5
$\begingroup$

It is easy to write this number (of $a$ such that $a,a+1$ are squares) in terms of the number of solutions of $x^2-y^2=1$. This is a conic which has $p+1$ projective points over the field of $p$ elements (since it is isomorphic to $\mathbb{P}^1$). It has two points at infinity, two points with $y=0$ and two or zero points with $x=0$, depending on $p \mod 4$. So you get your formula.

There is no way of telling the quadratic character of $a+b$ from that of $a,b$, but it is a square half the time.

$\endgroup$
3
  • $\begingroup$ The ``half the time'' comment is known to be true because the quadratic residue graph is quasirandom (this is in the seminal paper of Graham & Chung on quasirandom subsets of $Z/(n)$ from around 1990). $\endgroup$ May 16, 2011 at 22:07
  • 3
    $\begingroup$ For primes, this has been known since at least Gauss. $\endgroup$ May 17, 2011 at 0:57
  • 3
    $\begingroup$ @Kevin: quoting a quasirandomness theorem to show edge density is 1/2 is overkill. $\endgroup$ May 17, 2011 at 2:22
3
$\begingroup$

To complement the answers so far let me show using Gauss sums that the number of solutions of $ ax^2+by^2=c $ in $\mathbb{F}_p$ equals $p-\left(\frac{-ab}{p}\right)$ for any $a,b,c\in\mathbb{F}_p^\times$. Indeed, this number equals $$ \frac{1}{p}\sum_n \sum_{x,y}e\left(n\frac{ax^2+by^2-c}{p}\right) = \frac{1}{p}\sum_n e\left(\frac{-nc}{p}\right) \sum_xe\left(\frac{nax^2}{p}\right)\sum_ye\left(\frac{nby^2}{p}\right),$$ where all sums are over $\mathbb{F}_p$ and $e(t)$ abbreviates $e^{2\pi i t}$. For $n\neq 0$ we have $$ \sum_xe\left(\frac{nax^2}{p}\right)\sum_ye\left(\frac{nby^2}{p}\right) = \left(\frac{na}{p}\right)\left(\frac{nb}{p}\right)\left(\sum_re\left(\frac{r^2}{p}\right)\right)^2 = \left(\frac{-ab}{p}\right)p,$$ so that the count in question equals $$ p+\left(\frac{-ab}{p}\right)\sum_{n\neq 0}e\left(\frac{-nc}{p}\right)=p-\left(\frac{-ab}{p}\right). $$

$\endgroup$
2
$\begingroup$

There is an elementary argument regarding the last problem. Denote by $N(p)$ the number of pairs of $(a,b)$ such that $a,b,a+b$ are all quadratic residues mod $p$. Hence we have $$N(p)=\frac{1}{8}\mathop{\sum\sum}_{\substack{a,b\bmod p\\(ab(a+b),p)=1}}\left(1+\left(\frac{a}{p}\right)\right)\left(1+\left(\frac{b}{p}\right)\right)\left(1+\left(\frac{a+b}{p}\right)\right)$$

$$=\frac{1}{8}\mathop{\sum\sum}_{\substack{a,b\bmod p\\(ab,p)=1}}\left(1+\left(\frac{a}{p}\right)\right)\left(1+\left(\frac{b}{p}\right)\right)\left(1+\left(\frac{a+b}{p}\right)\right)$$

$$-\frac{1}{8}\mathop{\sum\sum}_{\substack{a,b\bmod p\\(ab,p)=1,p|a+b}}\left(1+\left(\frac{a}{p}\right)\right)\left(1+\left(\frac{b}{p}\right)\right).$$

Clearly, the second term is just \begin{align*}&-\frac{1}{8}\sum_{\substack{a\bmod p\\(a,p)=1}}\left(1+\left(\frac{a}{p}\right)\right)\left(1+\left(\frac{-a}{p}\right)\right)=\frac{1}{8}-\frac{p}{8}\left(1+\left(\frac{-1}{p}\right)\right).\end{align*} And for the first term, we are required to investigate the quantity \begin{align*}L:=\mathop{\sum\sum}_{\substack{a,b\bmod p\\(ab,p)=1}}\left(\frac{ab(a+b)}{p}\right).\end{align*} In fact we have

$$L:=\mathop{\sum\sum}_{\substack{a,b\bmod p\\(ab,p)=1}}\left(\frac{ba^2+b^2a}{p}\right) =\mathop{\sum\sum}_{\substack{a,b\bmod p\\(ab,p)=1}}\left(\frac{b(a+\overline{2}b)^2-\overline{4}b^3}{p}\right)$$

$$=\mathop{\sum\sum}_{a,b\bmod p}\left(\frac{ba^2-\overline{4}b^3}{p}\right)$$

$$=\sum_{b\bmod p}\left(\frac{b}{p}\right)\sum_{a\bmod p}\left(\frac{a^2-\overline{4}b^2}{p}\right)$$

$$=\sum_{b\bmod p}\left(\frac{b}{p}\right)\sum_{a\bmod p}\left(\frac{a^2-1}{p}\right)=0.$$

The other terms could be computed in a similar way. Hence we can deduce that \begin{align*}N(p)=\frac{1}{8}(p-1)^2-\frac{p}{8}\left(1+\left(\frac{-1}{p}\right)\right)+\frac{1}{8}.\end{align*}

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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