###
Representing an integer by a positive definite binary quadratic form

Given a positive definite binary quadratic form ax^{2}+bxy+cy^{2}, we use an algorithm of Gauss to determine if a given positive integer m is expressible as

m = ax^{2}+bxy+cy^{2}, x and y integers, gcd(x,y) = 1.

Note: Here d = b^{2} - 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 (a
_{1},b_{1},c_{1}) of (a,b,c).
- Solve n
^{2} ≡ d (mod 4m), 0 ≤ n < 2m.

If there is no solution, exit.
- For each solution n, calculate l, where n
^{2} - 4ml = d.
- Find the reduced form (a
_{2},b_{2},c_{2}) of (m,n,l).
- Test for equality of (a
_{1},b_{1},c_{1}) and (a_{2},b_{2},c_{2}). 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 = ax
^{2} + bxy + cy^{2}.
- 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 t^{2} - du^{2} = 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