Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $p$ be given prime $q$ or power of prime $q^r$. How many pairs $x \pmod p,y \pmod p$ can one expect for the equation $x^{2} - y^{2} \equiv k \pmod p$ where $k \pmod p \neq 0$ is given?

share|improve this question
    
If $k\ne 0$ we can expect $n-1$ pairs per $k\pmod{p}$. I believe there's a proof using quadratic residues. –  Foo Barrigno Jul 31 '13 at 11:36
    
what is $n$ in your comment? –  Turbo Jul 31 '13 at 11:36
    
Sorru, $n = p$. I was mixing up my terminology. I think you can use the fact that if $x$ is a residue $\pmod{p}$ then $-x$ is not a residue. –  Foo Barrigno Jul 31 '13 at 11:39
1  
If $k=0$ and $p>2$, there are $p(p-1)$ coming from $x=y$ and $x=-y$. –  Lior B-S Jul 31 '13 at 11:45
    
@Arul - no proof, however it holds at least for $p\le 17$ –  Foo Barrigno Jul 31 '13 at 11:50

1 Answer 1

up vote 6 down vote accepted

We deal with the original problem that asked only about primes.

The case $p=2$ is special, but easy to take care of. So let $p$ be an odd prime.

The case $k\equiv 0\pmod{p}$ is special, so for now assume $k\not\equiv 0\pmod{p}$.

We are looking at the congruence $(x-y)(x+y)\equiv k\pmod{p}$. Given any solution $(x,y)$, the pair $(x-y,x+y)$ is an ordered pair with product congruent to $k$. Conversely, let $(a,b)$ be an ordered pair such that $ab\equiv k\pmod{p}$. Then by solving the linear system $x-y\equiv a\pmod{p}$, $x+y\equiv b\pmod{p}$ we obtain a pair $(x,y)$ such that $x^2-y^2\equiv k\pmod{p}$. The system has a unique solution, obtained in the usual way.

There are $p-1$ possibilities for $a$, and hence $p-1$ solutions to the original congruence.

Finally, we deal with $p$ odd, $k$ a multiple of $p$. For any $x\not\equiv 0\pmod{p}$, there are $2$ possible values of $y$. Along with $(0,0)$ this gives $2p-1$ solutions.

Remark: The same analysis works for $x^2-y^2\equiv k\pmod{n}$, where $n$ is odd and $k$ and $n$ are relatively prime. For even $n$, a small change is needed.

Dealing with general $n$ and $k$ not relatively prime to $n$ may be messy.

share|improve this answer
    
Same holds if $p = q^r$? with case $q=2$ also included? –  Turbo Jul 31 '13 at 12:08
    
For powers $q^r$ of an odd prime $q$, and $k$ not divisible by $q$, same argument gives $\varphi(q^r)$, so $(p-1)p^{r-1}$. For $k$ divisible by various powers of $q$ it gets a little messy, with odd powers and even powers behaving a bit differently. Powers of $2$ are also special. –  André Nicolas Jul 31 '13 at 12:29

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.