Solving the diophantine equation ax2+by2=m 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 20th January 2005
Return to main page