SOLVING INTEGRAL QUADRATICS INTEGRALLY AND RATIONALLY. [Based on supplemental handout for a class in Elliptic Curves Dave Rusin, rusin@math.niu.edu Last revised 2/3/95 ] Sect I. INTRODUCTION Suppose given an integral quadratic equation a x^2 + b xy + c y^2 + dx + ey + f = 0 Our goals are: (1) To prove the Hasse-Minkowski Theorem (local-to-global principle): that this equation has rational solutions iff it is solvable in R and in each of the p-adic fields Q_p. (In one direction this is trivial.) (2) To determine when the equation has integral solutions and to find a procedure to determine all integer solutions quickly. We do this by reducing the equation (in most cases) to a Pellian equation x^2 + D y^2 = N. (3) To provide comments and extensions relating this to other topics. (4) To provide source code for solving these problems (not yet done) Sect II. REDUCTION TO THE PARTICULAR (PELLIAN) FORM The equation b xy + dx + ey + f = 0 is linear (and so, well-understood) if b=0; if b<>0, we can get an equivalent equation my multiplying by b then rearranging to get ( b x + e ) ( b y + d ) = ( de - bf) This is easy to deal with if de=bf. Otherwise, bx+d has to be a factor of de-bf, of which there are only finitely many. So we choose a factor g (positive or negative) and then solve for x and y in b x + d = g b y + e = g' = (de-bf)/g In particular, it is easy to spot which solutions (x,y) are integral. (The equation over a field is essentially XY=1, that is, it clearly has solutions in R and every Q_p, and it has solutions in Q). Having dispensed with this case, we may assume that one of the squares, say x^2, has a non-zero coefficient. Assuming a<>0 we multiply our original equation by 4a and get an equivalent equation involving x1 = 2a x + b y + d and y, namely x1^2 + (4ac-b^2) y^2 + (4ae-2bd) y + (4af-d^2) = 0 If (x,y) is an integral solution to the original equation, (x1,y) will be an integral solution to this one; the converse is only true for those integral solutions (x1,y) in which x1 -by = d mod (2a). Over any field, the solutions (x,y) and (x1,y) are in bijection. We write the last equation in the form x1^2 + D y^2 + E y + F = 0. If D = 0, there can only be an integral solution if -F is a square mod E; then all integral solutions are found by taking u to be each of the (finitely many) possible square roots of -F mod E, taking x1 = u + E x2 (for any integer x2), and then taking y = -E x2^2 - (2u) x2 - [(u^2+F)/E] (an integer). (Over a field, this equation is essentially X^2+Y=0, which has solutions over every R and Q_p, and solutions over Q). (If both D and E are zero, it is easy to analyze the solutions to x1^2+F=0 over the integers, rationals, R, or Q_p). Excluding this case, we may now assume D is nonzero. We don't change the solution set if we multiply by 4D; this gives an equation in y1 = 2D y + E and x1 which may be written y1^2 + (4D) x1^2 = (E^2- 4DF). As before, if we had integer solutions (x1,y) to the previous equation, we get integer solutions (x1,y1) to this one; integer solutions to this one only give integer solutions to the previous one if y1 = E mod 2D. Solutions over a field to the two equations are again in bijection. The equation to be solved now has the form y1^2 + D0 x1^2 = N0 for integers D0 and N0. We will look for rational solutions first, then return to look for integral solutions. Observe that in what follows we may assume x1 and y1 are non-negative; arbitrary changes in sign provide more solutions. Sect III. PROOF OF THE HASSE-MINKOWSKI THEOREM We wish to determine whether the quadratic equation has rational solutions. In this case we yield to the encumbrances of invertibility. Observe that a rational solution exists iff there is a solution in integers to y2^2 + D0 x2^2 = N z2^2 and that if any integer solution exists, a solution exists with x2, y2, and z2 relatively prime. Write D0=S^2 D1 and N0=T^2 N1 with D1 and N1 squarefree. Let G = gcd(D1, N1) and D1= G D2 and N1 = G N2. Note that D2 and N2 are relatively prime to each other and to G. Now, multiply the equation to be solved by G to get and equation involving x3=S G x2 y3=G y2 z3=T G z2 namely G y3^2 + D2 x3^2 + (-N2) z3^2 = 0 which we will rewrite with more symmetric notation as (*) a1 x1^2 + a2 x2^2 + a3 x3^2 = 0 where the ai are pairwise relatively prime nonzero integers. Our task is to show that if this equation has a solution in Z_p for all primes p, it has a rational solution. Note that we can assume at least one xi is not divisible by p by dividing by gcd(x1, x2, x3) (which is a power of p). Actually, we don't care about solvability in Q_p for odd p not dividing any ai. We also don't need to know it's solvable in both R and Q_2. Cassel's book gives a proof assuming solvability in Q_2. Here is a proof (from Borevich and Shafarevich, Number Theory) which assume solvability in R. First let's see what we learn from assuming (*) is solvable in Q_p for a prime p. Suppose p is a prime dividing a1. Choose a solution to this last equation in Z_p. I claim p does not divide x2. For if p|x2, then we'd have p| a3 x3^2, whence p | x3^2, so p|x3, so p^2 would divide a2 x2^2 + a3 x3^2 and thus a1 x1^2, so (as p divides a1 only to the first power) p|x1^2 and then p|x1. But this would make p divide all of x1, x2, and x3, contrary to our hypothesis. So we have p not dividing x2 (nor, by symmetry, x3). Then division mod p is defined so that we may write -(a2/a3) = (x3/x2)^2 mod p. Now, the right side is the square of a integer in Z_p (mod p), but the congruence classes mod p are just the congruence classes of integers mod p. It follows that there is an integer S=S1(p) such that -a2/a3 = S^2 mod p, i.e. a2 + S^2 a3 = 0. Then (*) reduces, mod p, to the congruence a3[(S(p) x2)^2 - x3^2]=0 In particular, we may factor the left side of (*) mod p as [S(p) x2 - x3][a3 S(p) x2 + a3 x3]. (The factorization is unique up to arrangement of the factors and up to scalar multiplication). Using the Chinese Remainder Theorem, we may find an integer S1 congruent to S(p) mod p for each p | a1. (S1 is unique mod a1 once the S(p) are fixed, but that means there are 2^n choices for S1 mod a1 if a1 has n odd prime factors.) Then it must be true that a1 x1^2 + a2 x2^2 + a3 x3^2 = [S1 x2 - x3][a3 S1 x2 + a3 x3] mod a1 since the congruence holds modulo each p| a1 and a1 is square-free. Likewise we find integers S2 and S3 so that the left side of (*) factors as [S2 x3 - x1][a3 S2 x3 + a1 x1] mod a2 and as [S3 x1 - x2][a1 S3 x1 + a2 x2] mod a3. With another application of the Chinese Remainder Theorem, we can write down two integral linear forms L and M so that a1 x1^2 + a2 x2^2 + a3 x3^2 = L(x1, x2, x3).M(x1, x2, x3) mod A, where in what follows we will write A for a1 a2 a3. In particular, if (x1, x2, x3) is any triple of integers where L(x1, x2, x3) = 0, then the left side of (*) is a multiple of A. The set of such solutions is an integer lattice, and an application of Minkowski's theorem would show that we can find one which will make the left side of (*) actually be zero. But we can do this more directly as follows. Consider the box defined by the inequalities |ai| xi^2 < |A| and xi >= 0 for i=1, 2, 3. The number of possible solutions xi is ceiling(sqrt(|A|/|ai|)), which is strictly greater than sqrt(|A|/|ai|) So the number of triples we are considering is strictly greater than the product of these, which is |A|. (OK, I lied a little: the number is only _strictly_ greater if the |A|/|ai| are not all squares. Since the ai are relatively prime, this is sure to hold unless |ai|=1 for all i. But this case is easily handled.) In particular, by the pigeonhole principle, there must be a pair of triples giving values to L(x, y, z) which are congruent mod A, and thus (by substracting) we find an integral triple (x,y,z) making L a multiple of A. Then, as in an earlier paragraph, the left side of (*) is also a multiple of A there. Note that (x,y,z) need not be in the box, but it's easy to see (|x|, |y|, |z|) must be, so this is now a point in the box where (*) is a multiple of A . Now, we have not yet used the fact that the equation (*) is assumed solvable in R. This assumption is equivalent to the statment that the ai don't all have the same sign. Multiplying through by -1 and relabelling the variables, as needed, we can assume a1, a2 > 0 > a3. Then it's easy to see that for any (x,y,z) in the box, the left side of (*) is strictly between -|A| and 2|A|. In particular, if it's an integer multiple of A, it's either 0 or |A|. In the latter case, we use this trick: if a1 x1^2 + a2 x2^2 + a3 x3^2 = A = -a1 a2 a3, then a1 z1^2 + a2 z2^2 + a3 z3^2 =0 where z1= x1 x3 + a2 x2 z2= x2 x3 - a1 x1 z3= x3 x3 + a1 a2 (This is another point in the lattice.) So, one way or another, we have found an integer triple making (*) hold. Sect IV. COMMENTS ON PROOF AND APPLICATION OF THE H-M THEOREM It is worth contemplating the effectiveness of this proof. If we can factor some integer coefficients, we can transform the arbitary quadratic into Sum ai xi^2 = 0. We only used the existence of a solution in Q_p to show that each -(ai/aj) is a square modulo the primes dividing the other ai. This is easily checked anyway, and in fact fast algorithms for computing square roots mod p exist. Thus the form L above is easily computed, and we may consider the solution set L=0 (a lattice) to be known. Indeed it will have very few points within the box (since the volume comes so close to the index); it is not hard to seek the lattice points closest to the origin. (If all else fails, we have given explicit upper bounds on the |xi|.) These points will solve the original equation. There may be more solutions, and indeed, we have quite a bit of freedom in constructing the lattice (any choice of which will lead to a solution): for, modulo each odd prime in question we have two choices of S(p). Interestingly, if the coefficients of the problem are very large it may be impossible to factor the necessary terms, and indeed difficult even to find the square-free ai. (Relatively primality is easier.) Moreover, if the ai cannot be factored, it is not so easy to compute square roots modulo ai. In this case, it seems reasonable to find an integer solution only when solutions in each Z_p are given. I'm not sure just how effective this approach is. It is also worth noting that we can get all the rational solutions once we have one. Indeed, suppose y1^2 + D0 x1^2 = N0 for some rational numbers (x1,y1). Any other rational pair may be written ( x1 + t, y1 + m t ) for some m and t (except for (x1, -y1), the only other solution with the same x coordinate as (x1, y1).) Substituting into the desired equation, we see the condition that this be a solution with t <> 0 is that t =-2 ( y1 m + D0 x1 ) / (m^2 + D0 ) [The case in which the denominator may be zero is trivial.] Thus, all remaining rational solutions are obtained from the one by selecting arbitary rational m and obtaining the point x = x1 -2 ( y1 m + D0 x1 ) / (m^2 + D0 ) y = y1 -2m ( y1 m + D0 x1 ) / (m^2 + D0 ) Of course, the search for _rational_ solutions to a quadratic need not take longer than the search for _integer_ solutions. We will show now that this is reasonably fast in some cases. Sect V. FINDING INTEGRAL SOLUTIONS TO PELL'S EQUATIONS We seek to solve y1^2 + D0 x1^2 = N0 in integers. This will, in non-trivial cases, require the use of algebraic number theory. If D0 is positive and N0 is negative, there are no solutions in R, hence none in Z or Q. If D0 is positive and N0 is >=0, there is at most a finite number of integer solutions to this problem, easily found (for N0 small) by examining each possible x1 = 0 thru sqrt(N0/D0). Alternately, one may proceed using algebraic number theory as below. If D0 is negative, we have the classic Pell's equation. We must show how to compute integral solutions (when they exist). We will let D2 = -D0 to focus on signs a little better: D2 > 0. We will assume as before that D2 is square-free (replacing D2 by D2/S^2 and x1 by S x1 as necessary.) The critical observation here is that a solution to y1^2 - D2 x1^2 = N0 in integers is equivalent to the discovery of an element u=y1 + d x1 in the ring of integers Z[d] of the algebraic number field Q[d] (where d = Sqrt(D2) ) which has a norm equal to N0. Here the Norm map is just N(u) = u . ubar for any such u, where 'bar' is the function sending d to -d (so ubar = y1 - d x1). Thus, for general N0, this becomes a problem in algebraic number theory. The _existence_ of integral solutions may be analyzed as follows. It is necessary and sufficient to find elements u and ubar in the ring with u.ubar= N0. I claim this is equivalent to finding a principal ideal I in the ring such that I.Ibar = (N0) (the principal ideal generated by N0.) Indeed, if u exists, let I = (u). Conversely, if such an I = (u) exists, then (u.ubar) = (N0), so u.ubar = N0.v for some unit v in the ring. But it is clear that v=Norm(u)/N0 lies in the ground field Q, and the only rational integral units are +- 1. If u.ubar = N0, we are done. If u.ubar=-N0, then either there is a unit e with e.ebar=-1 (in which case (ue).(ue)bar = N0 ) or not (in which case the equation u.ubar=N0 has no solution [I think]). Observe also that we can recover _all_ the solutions u for which (u) = I if we can find one, by taking u'=uv for all units v. [*NOTE* I thought wrong. See correction below from John Robertson --djr] Now, the ideal (N0) may be uniquely factored into prime ideals; indeed, if N0 = Prod pi^ei, then (N0) = Prod (pi)^ei. These ideals (pi) will behave in one of three ways: (pi) = Pi (a prime ideal in the ring); (pi)=Pi.Pi-bar (the prime splits) or (pi)=Pi^2 (the prime ramifies). It is easy to check the behaviour of any individual pi by checking to see whether or not D2 is a square mod pi. Thus (N0) may be written as a product of conjugate ideals iff ei is even for each pi which stays prime in the ring. In that case, the set of all possible ideals I such that I.Ibar = (N0) is found by computing all products I = I1 I2 I3 where I1 = Prod (pi)^(ei/2) (the product running over all i with (pi) prime) I3 = Prod (Pi)^ei (the product over all ramified primes) and I2 = Prod (Pi)^ei (the product over all split primes, where either Pi or Pi-bar chosen for each i; that is, there is more than one possible I2). Given this information, the only impediment to the preceding paragraph is that the created ideal I is supposed to be principal. This requires a calculation in the class group of the ring. A solution exists iff some choice of I2 leads to the identity element in the class group. The _computation_ of a solution seems to require factoring N0, analyzing the decomposition of the pi, and studying the class group of the ring. However, if N0 is less than 2Sqrt(D2), then a solution exists iff it is discovered via the continued fraction method described below; this does not require factoring N0 (or D2). The computation of the set of _all_ solutions involves the computation of a basic set as above, together with the computation of units. It is known that the units of this ring are all of the form (+-) e^n where n is any integer and e is a _fundamental unit_ (the smallest unit > 1). Since the norm of a unit is a unit in Z (i.e., +1 or -1), we are led to consider the equations y1^2 - D2 x1^2 = +-1. If we have a solution to this, then | (y1/x1) - Sqrt(D2) | = 1/[x1^2.|(y1/x1) + Sqrt(D2)|] (in fact, this is equivalent to the previous problem up to a loss of sign). For positive x1 and y1, this implies |(y1/x1) - Sqrt(D2)| is bounded by 1/2x1^2. It is known that this implies (y1/x1) is one of the recurrent terms in the continued fraction algorithm computing Sqrt(D2). It can be shown that the first solution which occurs in this way is a fundamental unit. (In particular, it will be clear whether or not there are units with norm -1. ) Thus an effective solution exists to find the units of the ring. (Along the way we discover solutions to the equation y1^2- D2 x1^2 = N0 for all N0 less than Sqrt(D2) for which a solution does exist.) I am not familiar with the methods used for the computation of the class group of real quadratic fields, nor the computation of which element of the group each ideal pertains to. Thus I can't give an effective solution to the general Pellian equation. Surely, however, this is known. One can show that if any solution exists (with x1>0, y1>0, say) then one exists with x1+y1Sqrt(D2) < Sqrt(N0.e) where e is the fundamental unit. See Borevich + Shafarevich p 123. I believe there is also some sort of reduction which reduces the question for general N0 to those N0 < 2sqrt(D), which is then addressed with continued fractions, but I can't remember what it is. You may wish to verify a few examples of various aspects of this theory: (1) x^2-3y^2 = 11 has no solutions though x^2-3y^2=-11 does (failure of existence of unit with norm -1) (2) the pairs (8,1) and (164,25) are solutions to x^2-43 y^2 = 21 which are not associates (one = other x a unit). (Two choices of ideal I with I.Ibar = (N0): I=P1.P2 or P1.P2-bar). (3) 7^2-10.1^2=39 but x^2-10y^2 =N has no solutions for N=+-3, +-13 (failure of being principal ideals) (4) In Z[Sqrt(79)] the primes dividing (3) and (5) are non-principal ideals. Here (3)=P.Pbar where P = (3, 1+sqrt(79)) and 5=Q.Qbar where Q = (5, 2+sqrt(79)). Therefore, (15)=I.Ibar in two essentially distinct ways, as in example (2). As in example (3), one of these is principal, so x^2-79 y^2 = +-N is solvable for N= 15 but not for N=3, 5. Unlike that example, though, we must choose I carefully: P.Q = ( 8-sqrt(79) ), but P.Qbar is not principal. (The class number is listed as 3, so [P] is of order 3, so [P][Q]=1 => [P][Qbar]=[P][Q]^(-1) is not 1.) References:Wagon, Amer Math Monthly 97 (1990) 125- Hardy, Muskat, Williams, Kath Comp 55 (1990) 327-343 D.A. Cox, 'Primes of the Form x^2+ny^2", Wiley 1989 Sect VI. COMMENTS AND EXTENSIONS (1) We assumed solutions in Q_p at the outset; however, once we have reduced to the form Sum(ai xi^2) = 0 with relatively prime squarefree nonzero ai, this is equivalent to having a solution in Z/pZ. (2) Yes, this can all be done over other algebraic number fields. The theorem then is that a solution in the field exists iff solutions exist in all completions of the field (Q_P for P a prime ideal, and all embeddings into C ). The initial reduction still works to show that integral solutions are related to those of x^2 - D y^2 = N, and those solutions may be found by considering ideals in an extension ring; however, the structure of the group of units becomes more complex and, as far as I know, there is no analogue of the continued fraction approach. (3) I have commented that solving quadratic equations by this method requires being able to factor integers (something which is implicit in the presentation of solutions in each Z_p, I suppose). A subsidiary question is of independent interest: given an integer a can we at least compute the squarefree part a/s^2? As far as I know this is no easier than the full factorization problem. On the other hand, solutions to quadratic polynomial equations by non-factoring methods (such as the continued fractions algorithm) leads to methods of factoring. Clearly, a solution of xy=D or x^2-y^2=D leads to a factorization of D; but also a solution of x^2-D y^2 = 1 has (x+1)(x-1) = D y^2 so gcd(x+1,D) gives a proper factor of D unless x = +-1 mod D. (Computation of a fundamental unit in Z[Sqrt(D)] thus provides such a factorization. Unfortunately, this can take roughly as many steps as a brute-force factorization of D.) (4) The H-M theorem also holds for quadratics of more than 2 variables. (5) The H-M theorem does NOT hold for polynomials of higher degree than 2. Classic counterexamples include products such as (x^2 + 3 y^2 - 17 z^2) (x^2 + 5 y^2 - 7 z^2) and Selmer's example 3 x^3 + 4 y^3 + 5 z^3 Loosely, the invariant Sha of an elliptic curve measures the extent of the failure of the local-to-global principle. Birch has shown the following: given an odd number d there is an n so that every homogeneous equation of degree d in n variables has a nontrivial rational solution. Sect VII. SOURCE CODE In an attempt to stay elementary I will write in BASIC the routines necessary to carry out these calculations. [not yet done] ============================================================================== Date: Mon, 29 Dec 1997 10:31:43 -0300 From: Dario Alejandro Alpern To: rusin@math.niu.edu Subject: Solving integer quadratic equations in two variables I'm making a calculator to solve this problem, and I'm using the information found in your page: [This page -- djr] One mistake I found was the following: > Sect II. REDUCTION TO THE PARTICULAR (PELLIAN) FORM > > The equation > b xy + dx + ey + f = 0 > is linear (and so, well-understood) if b=0; if b<>0, we can get an equivalent > equation my multiplying by b then rearranging to get > ( b x + d ) ( b y + e ) = ( de - bf) > This is easy to deal with if de=bf. Otherwise, bx+d has to be a factor of > de-bf, of which there are only finitely many. So we choose a factor g > (positive or negative) and then solve for x and y in > b x + d = g > b y + e = g' = (de-bf)/g > In particular, it is easy to spot which solutions (x,y) are integral. > ... "bx + d" must be replaced by "bx + e", and "by + e" must be replaced by "by + d". I almost finished the calculator except for the following. Is there an easier way to solve y1^2 - D2 x1^2 = N0 for N0 > 2sqrt(D2) than the method you wrote? Now I'm doing the calculator in UBASIC. When I finish I will migrate the code to JavaScript, so I the calculator can be used online. Thanks in advance. -- Dario Alejandro Alpern Buenos Aires - Argentina http://members.tripod.com/~alpertron (en castellano) http://members.tripod.com/~alpertron/ENGLISH.HTM (English) Si su navegador no soporta JavaScript: http://members.tripod.com/~alpertron/INDEX2.HTM If your browser does not support JavaScript: http://members.tripod.com/~alpertron/ENGLISH2.HTM Antes era fanfarron... Ahora soy perfecto!! ============================================================================== Date: Sun, 4 Jan 1998 02:25:51 -0600 (CST) From: Dave Rusin To: alpertron@hotmail.com Subject: Re: Solving integer quadratic equations in two variables Thanks for catching the misprints. I believe there are also some sign errors later (or else I may have confused D0 and D2). Yes, there are other ways to solve the Pell equation. I'm pretty sure that Henri Cohen's book has a detailed discussion of this, but it occupies a major portion of Gauss's Disquisitiones Arithmeticae too! I don't recall the specifics, but the procedure runs recursively; I believe the idea is to solve x^2-Dy^2=N by first solving mod N to get x^2-Dy^2=kN for some k < N; then it suffices (I think) to solve x^2-Dy^2=k, because there's some way to combine the two solutions to get a solution to x^2-Dy^2=N. I'm a little hesitant because I think this idea might require Z[sqrt(D)] to be a unique factorization domain, but there's some way to get around that problem too I suppose. If the ring is even a little more special (a Euclidean domain), you can make this procedure go very quickly; see 97/2squares.comp You don't have to confront the algebraic number theory to solve the problem, but you do have to realize that it's hiding there, preventing some equations from having solutions at all; so you might as well accept its presence! (Note: In order to solve mod N you'll need to be able to factor N, and then k as well. This is the major bottleneck with the algorithm I described, and it's unavoidable unless everybody has been blind to a simple algorithm for factoring integers!) You can actually find code for this if you have access to maple, since you can print the isolve procedure, which is capable of finding all solutions to an integral quadratic in two variables. Besides Cohen's excellent book and the article by Wagon which is in the file you have already read, you might want to read a few related notes at my site and the papers and books they cite. Try scanning index/11DXX.html for "Pell" or "quadratic". dave ============================================================================== From: Jpr2718@aol.com Date: Mon, 24 Mar 2003 21:37:23 EST Subject: Pell equations To: rusin@math.niu.edu Dear Dave, At <95/quadratics>, in about the middle, you say, ``If u.ubar = N0, we are done. If u.ubar=-N0, then either there is a unit e with e.ebar=-1 (in which case (ue).(ue)bar = N0) or not (in which case the equation u.ubar=N0 has no solution [I think]).'' Actually, there are counterexamples to this statement. For instance, x^2 - 34y^2 = -1 does not have integer solutions, but both x^2 - 34y^2 = 33 and x^2 - 34y^2 = -33 have solutions ((13, 2) for the first, and (1, 1) for the second). For some methods for solving the generalized Pell equation x^2 - Dy^2 = N see http://hometown.aol.com/jpr2718/. John Robertson jpr2718@aol.com