Solving the diophantine equation ax2+bxy+cy2=n, where b2-4ac > 0 and is not a perfect square, n non-zero, gcd(a,b,c)=1

This uses a continued fraction approach to find representatives of the equivalence classes of solutions (x,y) with gcd(x,y)=1. The method goes back to Lagrange 1770 and was rediscovered in 2001 by Keith Matthews.
If gcd(a,n)=1, the algorithm finds representatives with least positive y.
(See paper.) The standard method is due to Gauss (See G.B. Mathews Number Theory, page 97 or note.)

E = 1 is verbose.

Enter a:
Enter b:
Enter c: (gcd(a,b,c)=1)
Enter n (non-zero):
Enter E (0 or 1):

Last modified 1st October 2006
Return to main page