Reducing an indefinite binary quadratic form using an algorithm of Don Zagier

Given an indefinite binary quadratic form ax2+bxy+cy2, we follow pages 120-132 of Zetafunktionen und quadratische Körper, Eine Einführung in die höhere Zahlentheorie, Don Zagier, Springer 1981 and define (a,b,c) to be reduced if a > 0, c > 0 and b > a+c, or equivalently, 0 < (√d - b)/2a < 1 < (√d + b)/2a.
The transformation x=nx'+y', y=-x', where n > (b + √d)/2a > n - 1, converts ax2+bxy+cy2 to (an2-bn+c)x'2+(2an-b)x'y'+ay'2 and on repeated application, will eventually reach a reduced form, and this gives a cycle of reduced forms.
Note: d=b2-4ac > 0, d is not a perfect square and we assume d < 106.

See the corresponding BC program.

Enter a:
Enter b:
Enter c:

Last modified 31st December 2011
Return to main page