# The number of solutions of $ax^2+by^2\equiv 1\pmod{p}$ is $p-\left(\frac{-ab}{p}\right)$

What I need to show is that

For $$\gcd(ab,p)=1$$ and p is a prime, the number of solutions of the equation $$ax^2+by^2\equiv 1\pmod{p}$$ is exactly $$p-\left(\frac{-ab}{p}\right)\,.$$

I got a hint that I have to use Legendre symbol from the answer.

I think that I may count a solution one by one.

What I did :

$$(ax)^2 \equiv a-aby^2 \pmod{p}$$ It suffices to count $$y$$ such that $$(\frac{a-aby^2}{p})=1$$.

I tried to use the complete residue system or a primitive root but it didn't work.

The factorization also didn't work.

I think that the pigeonhole principle may not work because it just says the existence.

• I think you should add the restriction that $p\not=2$, else the formula is not true. Regards. May 21, 2013 at 14:49
• For the benefit of search engine users: This is problem 22 from section 3.2 of Niven, Zuckermann and Montgomery (NZM 3.2.22). Jun 29, 2013 at 23:58

Using Legendre symbol, the number of solutions can be written as $$\sum_{y=0}^{p-1} \left(1+\left(\frac{a-aby^2}{p}\right)\right),$$ since if $a-aby^2$ is nonzero square, you have to count two solutions in $x$, and if $a-aby^2$ is zero, then you have to count one solution in $x$ (namely 0), and if $a-aby^2$ is non-square, then no solutions.

Then rewrite the summation of second term as $$\sum_{y=0}^{p-1} \left(\frac{a-aby^2}{p}\right)=\left(\frac{-ab}{p}\right)\sum_{y=0}^{p-1}\left(\frac{y^2+d}{p}\right),$$ where $d=-b^*$ ($b^*$ is the inverse of $b$ modulo $p$)

The summation on the right, can be rewritten as $$\sum_{y=0}^{p-1} \left(1+\left(\frac{y}{p}\right)\right)\left(\frac{y+d}{p}\right)$$

Then the sum over single Legendre symbol is zero, but it remains to compute $$\sum_{y=0}^{p-1}\left(\frac{y}{p}\right)\left(\frac{y+d}{p}\right)$$

This one involves a trick: using $\left(\frac{y^*}{p}\right)$ instead of $\left(\frac{y}{p}\right)$

Then you will find that $$\sum_{y=0}^{p-1}\left(\frac{y}{p}\right)\left(\frac{y+d}{p}\right)=-1$$

Now, putting all together, you get the desired answer.

• Excuse me, do you mind explaning in a little more details how to evaluate the final sum? Thanks in advance for any explanations. May 21, 2013 at 14:57
• Oh, I see. We can rewrite it as the sum of all $(\dfrac{1+yd}{p})$ and this is the sum of all Legendre symbols, except for $(\dfrac{1}{p})$, and hence equals $-1$. Thanks thus for this beautiful answer. :D May 21, 2013 at 15:04
• @i707107 How did you get $\sum_{y=0}^{p-1}(\frac{y^2+d}{p})=\sum_{y=0}^{p-1}(1+(\frac{y}{p}))(\frac{y+d}{p})$? May 21, 2013 at 15:17
• If $y$ is a nonzero square(i.e. $\left(\frac{y}{p}\right)=1$, then the symbol $\left(\frac{y+d}{p}\right)$ gets summed twice, and if $y$ is zero, then $\left(\frac{d}{p}\right)$, and if $y$ is non-square, then the symbol $\left(\frac{y+d}{p}\right)$does not get summed. May 21, 2013 at 15:56

Let $k = -b/a$ and $c = 1/a$ (both are nonzero), so that you can rewrite the equation as $x^2-ky^2 = c$.

Call $N(k,c)$ the number of solutions $(x,y)$ to $x^2-ky^2 = c$. It is easy to check that this number only depends on $c$ and wether $k$ is a square, a nonsquare, or $0$, and that $N(0,c) = p(1 + \binom c p)$

Call $M(y,c)$ the number of solutions $(x,k)$ to $x^2-ky^2 = c$. If $y=0$ then again, $M(0,c) = N(0,c)$. And if $y \neq 0$, we clearly have $k = (x^2-c)/y^2$, hence $M(y,c) = p$ (one value of $k$ for each value of $x$)

The total number $T(c)$ of triplets $(x,y,k)$ satisfying the equation is $T(c) = \sum N(k,c) = \sum M(y,c) = M(0,c) + (p-1)p$, hence $\sum_{k \neq 0} N(k,c) = p^2-p$.

Now, if $k$ is a square $u^2$ you can factor the left-hand side to get $(x-uy)(x+uy) = c$. Since $p>2$, the change of variable $(x,y) \to (x-uy,x+uy) = (s,t)$ is invertible, and you get $st = c$, of which there are $p-1$ solutions for $c \neq 0$, (and $2p-1$ for $c=0$).

This leaves you, when $c \neq 0$, with $(p^2-p)-(p-1)^2/2 = (p-1)(p+1)/2$ triplets with $k$ nonsquare, hence $p+1$ solutions for each nonsquare $k$.
And when $c = 0$, with $(p^2-p)-(p-1)(2p-1)/2 = (p-1)/2$ triplets, hence $1$ solution (the trivial $x=y=0$ one) for each nonsquare $k$.

Let $$N(x^2=a)$$ be the number of $$x\in\mathbb{Z}/p\mathbb{Z}$$ such that $$x^2=a$$. Clearly, $$N(x^2=a)=1+\left(\frac{a}{p}\right).$$ Now, the number $$S$$ of solutions to our original equation $$\alpha x^2+\beta y^2=1$$ can be written as \begin{align} S&=\sum_{\substack{ a,b\in\mathbb{Z}/p\mathbb{Z}\\ \alpha a+\beta b=1}}N(x^2=a)N(y^2=b)\\ &=\sum_{\substack{ a,b\in\mathbb{Z}/p\mathbb{Z}\\ \alpha a+\beta b=1}}1+\sum_{\substack{ a,b\in\mathbb{Z}/p\mathbb{Z}\\ \alpha a+\beta b=1}}\left(\frac{a}{p}\right)+\sum_{\substack{ a,b\in\mathbb{Z}/p\mathbb{Z}\\ \alpha a+\beta b=1}}\left(\frac{b}{p}\right)+\sum_{\substack{ a,b\in\mathbb{Z}/p\mathbb{Z}\\ \alpha a+\beta b=1}}\left(\frac{ab}{p}\right). \end{align} Observe that each sum has $$p$$ terms and that $$b=(1-\alpha a)/\beta$$ as $$a$$ runs through the elements of $$\mathbb{Z}/p\mathbb{Z}$$. In other words, the first sum is $$p$$. Since there are as many residues as nonresidues in $$\mathbb{Z}/p\mathbb{Z}$$, both middle sums are zero. Finally, we get that $$S=p+\sum_{\substack{ a,b\in\mathbb{Z}/p\mathbb{Z}\\ \alpha a+\beta b=1}}\left(\frac{ab}{p}\right)=p+\left(\frac{\beta^{-1}}{p}\right)\sum_{a\in\mathbb{Z}/p\mathbb{Z}}\left(\frac{a(1-\alpha a)}{p}\right)=p+\left(\frac{\beta}{p}\right)\sum_{a\in\mathbb{Z}/p\mathbb{Z}}\left(\frac{a(1-\alpha a)}{p}\right).$$ For the last sum, observe that $$\left(\frac{a(1-\alpha a)}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{1-\alpha a}{p}\right)=\left(\frac{a}{p}\right)^{-1}\left(\frac{1-\alpha a}{p}\right)=\left(\frac{a^{-1}-\alpha}{p}\right)$$ and that $$a\mapsto a^{-1}-\alpha$$ is a bijection from $$(\mathbb{Z}/p\mathbb{Z})^\times$$ onto $$\mathbb{Z}/p\mathbb{Z}\setminus\{-\alpha\}$$ so that $$S=p-\left(\frac{\beta}{p}\right)\left(\frac{-\alpha}{p}\right)=p-\left(\frac{-\alpha\beta}{p}\right).$$