Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
4  
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. –  Siksek May 16 '11 at 22:05
    
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$. –  GH from MO May 17 '11 at 3:46
    
@GH Some of the solutions will have $a=b$, which I do not want to count. May be I was not clear about this. –  Julián Aguirre May 17 '11 at 21:09
add comment

4 Answers 4

up vote 13 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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). –  Kevin O'Bryant May 16 '11 at 22:07
3  
For primes, this has been known since at least Gauss. –  Felipe Voloch May 17 '11 at 0:57
3  
@Kevin: quoting a quasirandomness theorem to show edge density is 1/2 is overkill. –  Omar Antolín-Camarena May 17 '11 at 2:22
add comment

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

share|improve this answer
add comment

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*}

share|improve this answer
    
To fix your LaTeX, I suggest putting backticks around your expressions (see the "How to write math" in the sidebar) –  Yemon Choi May 17 '11 at 1:24
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.