Given a positive definite binary quadratic form ax2+bxy+cy2, we use an algorithm of Gauss to determine if a given positive integer m is expressible as
m = ax2+bxy+cy2, x and y integers, gcd(x,y) = 1.Note: Here d = b2 - 4ac < 0, a > 0, c > 0.
The algorithm (See L.E. Dickson, Introduction to the theory of numbers, pages 74-75.)
- Find the reduced form (a1,b1,c1) of (a,b,c).
- Solve n2 ≡ d (mod 4m), 0 ≤ n < 2m.
If there is no solution, exit.
- For each solution n, calculate l, where n2 - 4ml = d.
- Find the reduced form (a2,b2,c2) of (m,n,l).
- Test for equality of (a1,b1,c1) and (a2,b2,c2). If equal (to (A,B,C) say), find the unimodular transformation
x = αX + βY, y = γX + δY which converts (a,b,c) into (m,n,l).
(if x = rX + sY, y = tX + uY converts (m,n,l) to (A,B,C)
and x = r'X + s'Y, y = t'X + u'Y converts (a,b,c) to (A,B,C)
then α = r'u - s't, β = -r's + s'r, γ = t'u - u't, δ = -t's + u'r.)
- Then (x,y) = (α,γ) is a proper solution of m = ax2 + bxy + cy2.
- Finally, compute the equivalent solutions (x',y') from
2ax' + (b + √d)y' = (2ax + (b + √d)y)(t + u√d)/2,or more explicitly
x' = x(t - ub)/2 - cuy, y' =aux + y(t + ub)/2,where t and u are integers satisfying t2 - du2 = 4. (Also see Loo-Keng Hua, Number Theory, page 279.)
E=0 prints only the solutions, grouped by automorphs, whereas E=1 prints n, the reduction of (a,b,c) and (m,n,l) and the transformation coefficients α, β, γ and δ.
Last modified 16th November 2006
Return to main page