How does Reduce solve Bivariate Diophantine quadratic equations?

Questions
, ,
1

Hi,

I’m a number theory hobbyist and currently playing with prime numbers. While working with Mersenne’s Primes, I came across Diophantine bivariate quadratic equations of the form:
x + y + 2 * n * x * y = (2^(n-1) - 1) / n
where n is an odd prime.

I found that the Reduce command works a bit faster than my own C++ algorithm that runs on my laptop.

I went thro’ the relevant reference page on your website and found that this equation falls in the catagory of “Hyperbolic-Type Equations with Square Determinants”. In this case, the equation is reduced to “D*f(x,y) - g”. I did the computation and found that this value comes out to be “2n(2nx + 1)(2ny + 1)”. The resulting linear functions only produce the trivial solutions: (0, c) and (c, 0) where c = (2^(n-1) - 1)/n.

So, my questions are as follows:

  1. Does your algorithm do the simple exhaustive brute force to find the solutions. Or some other advanced algorithm is used.
    I’m asking because my algorithm is plain brute force and yours is a bit faster than mine. So, is it just because of your high-end server grade hardware infrastructure or the algo as well.

  2. Is there any way to tell whether a particular equation of this form has a solution or not (other than the trivial ones) without going through the brute force. I’ve looked around a bit and at this point, it seems negative.

Thanks for your time.

manoj

2
3

Hi Frank,

Thanks for the link; it’s very informative.

I found that in this particular scenario (i.e., when determinant is perfect square), Reduce factorizes the RHS which, in this case, is the prime number itself (2^n - 1). Since I’m using this equation to factorize the prime number, I can’t use this algorithm.

I was hoping something similar to the solution to Pell’s equation which indeed is used by Reduce in other cases (when determinant is not a perfect square).

If you are aware of any other algo to solve this equation, please do let me know.

Accept my gratitude in advance.

manoj