Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there any relatively efficient way to calculate integer solutions $x$ and $y$ to the equation $x^2 - y^2 = z$ for a fixed integer $z$?

May or may not be useful: $z$ is an odd composite number

Thanks

share|cite|improve this question

migrated from mathoverflow.net Jul 2 '13 at 1:49

This question came from our site for professional mathematicians.

    
Why not just ask if there's an efficient way to factor integers? – Steven Landsburg Jul 2 '13 at 1:23

Write $z$ as $z=ab$. Hence, one solution for $x^2-y^2 = ab$ is $(x+y) = a \text{ and } x-y =b$.

I am sure you can take it from here.

share|cite|improve this answer
    
We do not have uniqueness in the case of two primes, since the trivial factorization gives a solution. – André Nicolas Jul 2 '13 at 1:55

HINT:

If $z$ is odd, $z\pm 1$ i s even $\implies \frac{z\pm1}2$ is integer

$$z\cdot1=\left(\frac{z+1}2\right)^2-\left(\frac{z-1}2\right)^2$$

If $z$ composite odd $=m\cdot n$(say), $m\pm n$ is even

$$m\cdot n=\left(\frac{m+n}2\right)^2-\left(\frac{m-n}2\right)^2$$

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.