5
$\begingroup$

Assume $p$ is a prime number and $\gcd(ab, p)=1$. Show that the number of integer solutions $(x, y)$ of $ax^2+by^2 \equiv 1 \pmod p$ is $$p - \left(\dfrac{-ab}{p}\right)$$ where $\left(\dfrac{x}{y}\right)$ is the Legendre symbol.

Ok, so here's my partial solution to the above question.

Suppose that $-ab$ is a quadratic residue of $p$, then $-ab\equiv c^2 \pmod p$ for some $c$.

Then $(ax)^2+aby^2\equiv(ax)^2-(cy)^2\equiv a \pmod p$ by multiplying both sides by $a$.

Then $(ax+cy)(ax-cy)\equiv a \pmod p$. Considering every possibility, it is not hard to see that there are $p-1$ solutions $(x, y)$ for the equation.

The problem is that I couldn't figure out how to prove this when $-ab$ is a quadratic nonresidue.

And even the solution I had shown to you is not truly mine; I got some help from my peers.

So I was wondering if there is a simpler solution to this question that includes the case when $-ab$ is a quadratic nonresidue. Nevertheless, I would also be really glad if someone could show me how to treat the nonresidue case separately.

Thanks!

$\endgroup$
  • 1
    $\begingroup$ Welcome to Math.SE! I've made significant edits to your original question to improve its readability and to add LaTeX syntax to your equations/mathematical expressions. Please take a look to make sure I didn't change the meaning of your question. Also, please read through the source code (click the "edit" link) to see how you can write math on Math.SE using LaTeX commands. $\endgroup$ – Dan Nov 1 '13 at 22:41
  • $\begingroup$ Thank you so much! I couldn't figure it out since this is my first time using Math.SE. I really appreciate your kindness. $\endgroup$ – Taxxi Nov 2 '13 at 0:20
  • $\begingroup$ Happy to help! :) $\endgroup$ – Dan Nov 2 '13 at 2:05
  • $\begingroup$ Possible duplicate of The number of solutions of $ax^2+by^2\equiv 1\pmod{p}$ is $ p-(\frac{-ab}{p})$ $\endgroup$ – Watson Feb 4 '18 at 13:13
8
$\begingroup$

Note: A caveat: It is to be noted that the analysis below only works for $p>2$ an odd prime. In any case, the result to be proved does not hold for $p=2$, and we shall only concern ourselves with $p>2$.

We have $(ax)^2 \equiv -aby^2+a \pmod{p}$, so we get $2$ solutions for $x$ when $(\frac{-aby^2+a}{p})=1$, $1$ solution when $(\frac{-aby^2+a}{p})=0$, and $0$ solutions when $(\frac{-aby^2+a}{p})=-1$. Thus the number of solutions is $$\sum_{y=0}^{p-1}{\left(1+\left(\frac{-aby^2+a}{p}\right)\right)}=p+\sum_{y=0}^{p-1}{\left(\frac{-aby^2+a}{p}\right)}=p+\left(\frac{-ab}{p}\right)\sum_{y=0}^{p-1}{\left(\frac{y^2-b^{-1}}{p}\right)}$$

It is fairly well known that $\sum_{y=0}^{p-1}{\left(\frac{y^2-b^{-1}}{p}\right)}=-1$, so this will give the number of solutions as $p-(\frac{-ab}{p})$ indeed. I shall prove that $\sum_{y=0}^{p-1}{\left(\frac{y^2-b^{-1}}{p}\right)}=-1$ below:

Proof of $\sum_{y=0}^{p-1}{\left(\frac{y^2-b^{-1}}{p}\right)}=-1$: By Euler's criterion, $$\sum_{y=0}^{p-1}{\left(\frac{y^2-b^{-1}}{p}\right)} \equiv \sum_{y=0}^{p-1}{(y^2-b^{-1})^{\frac{p-1}{2}}} \equiv \sum_{y=0}^{p-1}{(y^{p-1}+Q(y))} \pmod{p}$$

where $Q(y)$ is a polynomial in $y$ with degree $\leq p-2$, over $\mathbb{Z}_p$.

It is easy to prove that $\sum_{y=0}^{p-1}{y^n} \equiv \begin{cases} 0 \pmod{p} & n=0 \, \text{or} \, p-1 \nmid n \\ -1 \pmod{p} & n>0, p-1 \mid n \end{cases}$.

Indeed, we have $\sum_{y=0}^{p-1}{y^0}=\sum_{y=0}^{p-1}{1} \equiv 0 \pmod{p}$, and for $n>0$, consider a primitive root $g \pmod{p}$, then $$\sum_{y=0}^{p-1}{y^n}=\sum_{y=1}^{p-1}{y^n}\equiv \sum_{i=0}^{p-2}{(g^i)^n} \equiv \begin{cases} \frac{1-(g^n)^{p-1}}{1-g^n} \equiv 0 \pmod{p}& p-1 \nmid n \\ \sum_{y=1}^{p-1}{1} \equiv -1 \pmod{p} & p-1 \mid n \end{cases}$$

Thus we now have

$$\sum_{y=0}^{p-1}{\left(\frac{y^2-b^{-1}}{p}\right)} \equiv \sum_{y=0}^{p-1}{(y^{p-1}+Q(y))} \equiv -1\pmod{p}$$

Note that $$\left|\sum_{y=0}^{p-1}{\left(\frac{y^2-b^{-1}}{p}\right)}\right| \leq \sum_{y=0}^{p-1}{\left|\left(\frac{y^2-b^{-1}}{p}\right)\right|} \leq \sum_{y=0}^{p-1}{1}=p$$

Therefore we must have $\sum_{y=0}^{p-1}{\left(\frac{y^2-b^{-1}}{p}\right)}=-1 \, \text{or} \, p-1$. If $\sum_{y=0}^{p-1}{\left(\frac{y^2-b^{-1}}{p}\right)}=p-1$, then we must have $p-1$ terms equal to $1$ and exactly $1$ term $\left(\frac{c^2-b^{-1}}{p}\right)$ which is $0$. However $\left(\frac{(-c)^2-b^{-1}}{p}\right)=0$ as well, which is only possible if $c \equiv -c \pmod{p}$, i.e. $c=0$. This gives $\left(\frac{-b^{-1}}{p}\right)=0$, a contradiction. Therefore $\sum_{y=0}^{p-1}{\left(\frac{y^2-b^{-1}}{p}\right)}=-1$, as desired.

Note: The above method can be modified to help evaluate $\sum_{y=0}^{p-1}{\left(\frac{f(y)}{p}\right)}$ for any polynomial $f(y)$.

$\endgroup$
  • $\begingroup$ It was a really clear proof. A bit hard to understand for me though (I'm merely a biginner for number theory) but the logic itself was self-evident. But I still wonder if there would be another way to solve this at my 'elementary' level. I don't think my professor required this generalized solution. Still it is an awesome proof. Thanks! $\endgroup$ – Taxxi Nov 2 '13 at 1:00
1
$\begingroup$

For the first part: If $-ab =c^2 \pmod{p}$ then

$$(ax)^2+aby^2 = a \pmod {p} \Leftrightarrow (ax)^2-(cy)^2 = a \pmod {p} $$

Now, $ax-cy=\alpha \neq 0 \pmod{p}$ and $ax+cy = \alpha^{-1}a$. You get exactly one solution for each $0 \neq \alpha \pmod{p}$.

$\endgroup$

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.