Solving the diophantine equation ax2+by2=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.

Enter a: (> 0)
Enter b: (> 0, gcd(a,b)=1)
Enter m: (≥ a+b),gcd(a,m)=1

Last modified 28th August 2015
Return to main page