Representing an integer by a positive definite binary quadratic form

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.)

  1. Find the reduced form (a1,b1,c1) of (a,b,c).
  2. Solve n2 ≡ d (mod 4m), 0 ≤ n < 2m.
    If there is no solution, exit.
  3. For each solution n, calculate l, where n2 - 4ml = d.
  4. Find the reduced form (a2,b2,c2) of (m,n,l).
  5. 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.)
  6. Then (x,y) = (α,γ) is a proper solution of m = ax2 + bxy + cy2.
  7. 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 δ.

Enter a:
Enter b:
Enter c:
Enter m (> 0):
Enter E (0 or 1):

Last modified 16th November 2006
Return to main page