#### Solving the diophantine equation ax^{2}+by^{2}=m, gcd(x,y) = 1, by Cornacchia's method

Here a > 0, b > 0,m ≥ a+b, gcd(a,m)=1=gcd(a,b).

The algorithm is from A. Nitaj, *L'algorithme de Cornacchia*, Expositiones Mathematicae 13 (1995), 358-365.

We find the positive solutions (x,y) with gcd(x,y)=1.

If a=b=1, we find the solutions with x ≥ y.

This works for m with up to say 20 digits, due to the limitations of the program used to factor m.

*Last modified 28th August 2015*

Return to main page