Alternative method to solve quadratic Diophantine equations

1.2k Views Asked by At

For most types of quadratic Diophantine equations there exists an algorithm which makes it possible to find a solution (or solutions) over integers (good reference is here: https://www.alpertron.com.ar/METHODS.HTM).

However, those methods require at some stage finding integer divisors of some expression made of equation's coefficients (i.e. A,B,...F). When these are small, then this task is not an issue. However, for coefficients with many digits this becomes an arduous exercise.

Does anyone see a possibility of finding integer solutions of QDE without the need of factorization (i.e. finding integer divisors) along the process?

1

There are 1 best solutions below

8
On BEST ANSWER

Probably there is no method easier than the method Dario Alpern presents.

Note that in general it is UNDECIDABLE, whether a given polynomial with integer coefficients has integer roots.

The case with $2$ variables and degree $2$ is completely solveable, but you already need some effort to do this.

You can write a program, for example, in PARI/GP. It can easily handle large numbers, and it can factor numbers upto about $60$ digits very fast. PARI/GP supports ECM and quadratic sieve methods. Of course, for $500-600$ digits, some luck is needed to get a factorization in a reasonable time. But checking whether a number is prime is routine even for $500-600$ digit numbers.

As fas as I know, you have to program the methods yourself, PARI/GP does not have a command solving quadratic equations.