From: Robin Chapman Subject: Re: x^2 - dy^2 = +/-4 query Date: Fri, 17 Dec 1999 09:27:05 GMT Newsgroups: sci.math Keywords: when do solutions exist? In article <83cadh$upo$1@nnrp1.deja.com>, jpr2718@aol.com wrote: > > For d==0 (mod 4), the method presented for solving x^2 - dy^2 = +/-4 > similarly follows easily from the method for solving x^2 - dy^2 = +/- > 1. In the +/-4 equation x must be even, so if r, s is a solution to > the equation r^2 - (d/4)s^2 = +/-1, then x=2r, y=s is a solution to > x^2 - dy^2 = +/-4. All solutions x, y must arise this way. One item > of interest in this case is that it is possible for there to be > solutions to x^2 - dy^2 = -4 without there being solutions to x^2 - > dy^2 = -1. For example, this happens for d = 8, 20, 40, 52, 68, 104, > and so on (I think this only happens for certain d that are either 4 > times or 8 times an integer that is 1 modulo 4, but I'm not sure). There can't be a solution if d is divisible by 16 by congruence conditions. If d = 4r or 8r where r is odd and not = 1 (mod 4), then r has a prime factor p = 3 (mod 4) and we can't have an x with x^2 = -4 (mod p). > For d==1 (mod 4), I do not see how to reduce solving x^2 - dy^2 = +/-4 > to solving x^2 - dy^2 = +/-1, even for some other d. I do understand > that the ring of integers in Q(sqrt(d)) is generated by 1 and (1+sqrt > (d))/2 when d==1 (mod 4) and d is not a square. Suppose that (x_1, y_1) is the "minimal" solution of x^2 - d y^2 = +-1 and that (x_2, y_2) is the "minimal" solution of x^2 - d y^2 = +-4. There are two possibilities. (i) x_2 and y_2 are both even. Then x_2 = 2x_1 and y_2 = 2y_1. (ii) x_2 and y_2 are both odd. Then x_1 + y_1 sqrt(d) = [(x_2 + y_2sqrt(d))/2]^3. > So it seems sensible > that the continued fraction expansion for (1+sqrt(d))/2 is involved in > solving x^2 - dy^2 = +/-4. But, I don't see how this relates to the > stopping point being the index where c_I = 2c_0 - 1, or why p_-2 = -1 > and p_-1 = 2. I am hoping someone has a reference or an explanation. > For d==1 (mod 4), solving x^2 - dy^2 = +/-4 seems to be more > fundamental than solving x^2 - dy^2 = +/-1. Agreed. -- Robin Chapman http://www.maths.ex.ac.uk/~rjc/rjc.html "`Well, I'd already done a PhD in X-Files Theory at UCLA, ...'" Greg Egan, _Teranesia_ Sent via Deja.com http://www.deja.com/ Before you buy. ============================================================================== From: Jpr2718@aol.com (John Robertson) Subject: Re: Equivalence of quadratic forms Date: 12 Jan 00 03:45:57 GMT Newsgroups: sci.math.numberthy Perhaps the best way known to determine whether the equation x^2-dy^2=-4 has a solution is to use the algorithm given below. While this algorithm is analogous to the continued fraction method for solving the equation x^2-dy^2=+/-1, it is more direct than solving x^2-dy^2=+/-1 and searching among the convergents for solutions to x^2-dy^2=-4. When d==1 (mod 4), which is the most interesting case for this method, x^2-dy^2=-4 has a solution if and only if L((1+sqrt (d))/2) is odd. Here, L(a) is the length of the continued fraction expansion of a. If d==0 (mod 4) then there is a solution iff L(sqrt (d)) is odd (as any such solution must be just twice a solution to x^2-dy^2=-1). And, if d==0 (mod 4), then there is a solution iff L(sqrt (d/4)) is odd (for any solution to x^2-dy^2=-4 we have that x is even and (x/2)^2 - (d/4)y^2=-1). The cf expansion of (1+sqrt(221))/2 has period 2, while, as noted in another post, the cf expansion of sqrt(221) has period 6. The method below thus shows that there is really only one fundamental solution to x^2-221y^2=4 (and not three as might be thought from the fact that 4 occurs twice in the fundamental period of the cf expansion of sqrt(221), as does 1). One reason x^2-221y^2=-4 does not have a solution is that x^2-221y^2=-1 does not have a solution (if d is not 4 or 8 times a product of primes congruent to 1 modulo 4, then x^2-dy^2=-4 has a solution iff x^2-dy^2=-1 has a solution). As with the equation x^2-dy^2=-1, there are no known universal criteria, other than those listed above, for determining whether x^2-dy^2=-4 has a solution. It is also an open question as to when x^2-dy^2=-4 has a solution but x^2-dy^2=-1 does not (d must be 4 or 8 times a product of primes congruent to 1 modulo 4, but this is not sufficient). A recent sci.math discussion under the thread "x^2 - dy^2 = +/-4 query" covers some of these points. I have not seen a proof in the literature of the method given below to solve x^2-dy^2=-4 for the case d==1 (mod 4), and would appreciate any references anyone might have. John Robertson THE ALGORITHM - Solving Pell equations x^2 - dy^2 = m for m = +/-1, or +/-4, with d>0, d not a perfect square. Begin by setting a_0 = 0, b_0 = 1, p_-2 = 0, p_-1 = 2, q_-2 = 1, q_-1 = 0, but substitute as follows, depending on the case: If m=+/-1 then p_-1 = 1. If m=+/-4 and d==1 (mod 4) then a_0 = 1, b_0 = 2, p_-2 = -1. If m=+/-4 and d==0 (mod 4) then b_0 = 2. If m=+/-4 and d==2 or 3 (mod 4) then q_-2 = 2. Recursively define c_i = int((a_i + sqrt(d))/b_i) for i>=0, a_i = b_{i-1}*c_{i-1} - a_{i-1} for i>=1, b_i = (d - (a_i)^2)/b_{i-1} for i>=1, p_i = c_i * p_{i-1} + p_{i-2} for i>=0, and q_i = c_i * q_{i-1} + q_{i-2} for i>=0. (Where the formula for c_i has sqrt(d), one can use int(sqrt(d)).) If d is congruent to 1 modulo 4 and m = +/-4, let k be the minimal index such that c_k = 2c_0 - 1 (but if d=5, take k=1). If either d is not congruent to 1 modulo 4, or m = +/-1, then let k be the minimal index such that c_k = 2c_0. The minimal positive solution to the Pell equation is given by taking x_1 = p_{k-1} and y_1 = q_{k-1}. If k is odd, this is a solution to the "negative" equation, i.e. the equation with m = -1 or m = -4. If k is even, this is a solution to the "positive" equation, m = +1 or m = +4. If k is even, then the negative equation does not have solutions. Note that the sequence c_i is the continued fraction expansion of (a_0 + sqrt(d))/b_0, and at each stage (a_i + sqrt(d))/b_i is the inverse of the fractional part of (a_{i-1} + sqrt(d))/b_{i-1}. If m=+/-1, then the following three ways to generate all of the positive solutions are equivalent: x_n + y_n*sqrt(d)=(x_1 + y_1*sqrt(d))^n x_n = x_1*x_{n-1} + y_1*y_{n-1}*d; y_n = y_1*x_{n-1} + x_1*y_{n-1} x_n = 2*x_1*x_{n-1} +/- x_{n-2}, y_n = 2*x_1*y_{n-1} +/- y_{n-2} where the + signs are to be used if there is a solution to the -1 equation, and the - signs are to be used if there are only solutions to the +1 equation. If m=+/-4, then the following three ways to generate all of the positive solutions are equivalent: x_n + y_n*sqrt(d)=((x_1 + y_1*sqrt(d))^n)/(2^(n-1)) x_n = (x_1*x_{n-1} + y_1*y_{n-1}*d)/2; y_n = (y_1*x_{n-1} + x_1*y_{n- 1})/2 x_n = x_1*x_{n-1} +/- x_{n-2}, y_n = x_1*y_{n-1} +/- y_{n-2} where the + signs are to be used if there is a solution to the -4 equation, and the - signs are to be used if there are only solutions to the +4 equation. If the -1 or -4 equation has a solution, then the above formulas generate all of the +/-1 or +/-4 solutions, alternately -1 and +1, or - 4 and +4. If you only want the solutions to one of the +1, -1, +4, or - 4 equations, there are analogous formulas.