New York J. Math. 11(2005)539–545.
Generalized Lagrange criteria for certain quadratic Diophantine equations
R.A. Mollin
Abstract. We consider the Diophantine equation of the formx2−Dy2=±4, whereDis a positive integer that is not a perfect square, and provide a gener- alization of results of Lagrange with elementary proofs using only basic prop- erties of simple continued fractions. As a consequence, we achieve a completely general, simple criterion for the central norm to be 4 associated with principal norm 8 in the simple continued fraction expansion of√
D.
Contents
1. Introduction 539
2. Notation and preliminaries 540
3. Central norms 4 associated with norm 8 542
References 544
1. Introduction
In [1], published in 1844, Eisenstein considered the problem of giving necessary and sufficient conditions for the solvability of the Diophantine equation
|x2−Dy2|= 4 whereD≡5 (mod 8), D∈N, and gcd(x, y) = 1. (1.1)
Indeed, considerable work has been done by various authors on this problem. For instance, see [2], [9]–[10].
We know that all solutions of Equation (1.1) can be given in terms of the simple continued fraction expansions of (1 +√
D)/2 (see [4, Theorem 5.3.4, p. 246] for instance). WhenD≡1 (mod 4),Dmust be even and work has been done in clas- sifying solutions of the equation in terms of the simple continued fraction expansion of√
D (see [2] for instance).
In this paper we assume the solvability of x2−Dy2 = 4 with gcd(x, y) = 1, whereD is a positive integer that is not a perfect square, and link an analogue of
Received January 31, 2005.
Mathematics Subject Classification. Primary: 11D09, 11R11, 11A55. Secondary: 11R29.
Key words and phrases. Quadratic Diophantine equations, Continued Fractions, Central Norms.
The author’s research is supported by NSERC Canada grant # A8484.
ISSN 1076-9803/05
539
a result of Lagrange obtained in [7] to the simple continued fraction of√
D. In [7], we looked at the fundamental solution (x, y) = (x0, y0) ofx2−Dy2= 1 and proved thatx0≡ ±1 (modD) if and only if the central norm is 2 in the simple continued fraction expansion of√
D (see below for definitions). This generalized a celebrated result of Lagrange. In this paper we link the fundamental solution ofx2−Dy2= 4, gcd(x, y) = 1, with central norms equal to 4, associated with a principal norm of 8, which is an exact analogue of the generalized Lagrange result.
2. Notation and preliminaries
We will be concerned with the simple continued fraction expansions of √ D, whereD is an integer that is not a perfect square. We denote this expansion by,
√D=q0;q1, q2, . . . , q−1,2q0, where=(√
D) is the period length,q0=√
D (thefloorof√
D), andq1, q2, . . . , q−1 is a palindrome. Thejthconvergentof√
D forj≥0 is given by, Aj
Bj
=q0;q1, q2, . . . , qj, where
Aj=qjAj−1+Aj−2, (2.1)
Bj=qjBj−1+Bj−2, (2.2)
withA−2= 0, A−1 = 1,B−2= 1,B−1 = 0. Thecomplete quotients are given by, (Pj+√
D)/Qj, whereP0= 0, Q0= 1, and for j≥1, Pj+1=qjQj−Pj, (2.3)
qj=
Pj+√ D Qj
, and
D=Pj+12 +QjQj+1.
We will also need the following facts (which can be found in most introductory texts in number theory, such as [4]. Also, see [3] for a more advanced exposition).
AjBj−1−Aj−1Bj = (−1)j−1. (2.4)
Also,
A2j−1−Bj−12 D= (−1)jQj. (2.5)
In particular,
A2−1−B2−1D= (−1). (2.6)
Whenis even,P/2=P/2+1, so by Equation (2.3), Q/22P/2,
whereQ/2 is called thecentral norm, (via Equation (2.5)), where Q/22D.
(2.7)
In general, the values Qj are called the principal norms, since they are the norms of the principal reduced ideals in the order Z[√
D], due to the association
between the simple continued fraction expansion of √
D and the infrastructure of the underlying real quadratic order (see [3] for instance).
We will be considering Diophantine equationsx2−Dy2= 1,4. Thefundamental solution of such an equation means the (unique) least positive integers (x, y) = (x0, y0) satisfying it.
In the following (which we need in the next section), and all subsequent results, the notation for theAj,Bj,Qjand so forth apply to the above-developed notation for the continued fraction expansion of√
D.
Theorem 1([6]). Let D be a positive integer that is not a perfect square. Then =(√
D) is even if and only if one of the following two conditions occurs:
(1) There exists a factorization D=ab with 1 < a < bsuch that the following equation has an integral solution(x, y):
|ax2−by2|= 1. (2.8)
Furthermore, in this case, each of the following holds, where (x, y) = (r, s) is the fundamental solution of Equation (2.8):
(a) Q/2=a.
(b) A/2−1=raandB/2−1=s. (c) A−1=r2a+s2b andB−1= 2rs. (d) r2a−s2b= (−1)/2.
(2) There exists a factorization D=ab with 1 ≤a < b such that the following equation has an integral solution(x, y)withxy odd:
|ax2−by2|= 2. (2.9)
Moreover, in this case each of the following holds, where(x, y) = (r, s)is the fundamental solution of Equation (2.9):
(a) Q/2= 2a.
(b) A/2−1=raandB/2−1=s. (c) 2A−1=r2a+s2b andB−1=rs. (d) r2a−s2b= 2(−1)/2.
We will require the following dual results, which are our original generalizations of the results of Lagrange that inspired the work herein. Both are proved in [7].
Theorem 2. If (x0, y0)is the fundamental solution of x2−Dy2= 1, (2.10)
whereD >2 is not a perfect square, then the following are equivalent:
(1) x0≡1 (modD).
(2) If=(√
D), then ≡0 (mod 4), andQ/2= 2.
(3) There is a solution to the Diophantine equation x2−Dy2= 2. (2.11)
Theorem 3. If (x0, y0)is the fundamental solution of x2−Dy2= 1, (2.12)
whereD >2 is not a perfect square, then the following are equivalent:
(1) x0≡ −1 (modD).
(2) If=(√
D), then ≡2 (mod 4), andQ/2= 2.
(3) There is a solution to the Diophantine equation x2−Dy2=−2. (2.13)
There is also the following result on central norms that we proved in [8]:
Theorem 4. Suppose thatD= 4dc, wherecis not a perfect square,cis odd,d≥1, =(√
D), and =(√
c). If is even, thenQ/2= 4d if and only if A/2−1
2d +B/2−1√
c=A−1+B−1√ c, (2.14)
in the simple continued fraction expansions of √
D, respectively √
c. Moreover, when this occurs, ≡/2 (mod 2).
Lastly, we will require the following in the next section.
Theorem 5. LetD >1be an integer that is not a perfect square and suppose that =(√
D) is even. Then each of the following holds:
Q/2A−1=A2/2−1+B2/2−1D, (2.15)
Q/2B−1= 2A/2−1B/2−1. (2.16)
Proof. This is a consequence of [5, Lemma 3.3, p. 323].
3. Central norms 4 associated with norm 8
The following is the analogue of Theorems2–3, and provides a criterion for the central norm to be 4, associated with norm 8, in the process.
Theorem 6. Let D > 16 be an integer that is not a perfect square, and let = (√
D). Also, assume that (x0, y0) is the fundamental solution of x2−Dy2= 4 with gcd(x, y) = 1. (3.1)
Then the following are equivalent:
(1) x0≡ ±2 (modD/2).
(2) ≡ 0 (mod 4), Q/2 = 4, and the there is a solution to the Diophantine equation
X2−DY2=±8 with gcd(X, Y) = 1, (3.2)
where the±signs correspond to those in part(1).
Proof. First we assume that part (1) holds. If x0/2 ≡ −1 (modD/4), then by Theorem 3, =(
D/4) ≡2 (mod 4), Q/2 = 2 and there is a solution to the equation
X2−DY2/4 =−2. (3.3)
Hence, D/4 is odd, since otherwise the solvability of Equation (3.1) would imply that D/4≡0 (mod 8), which contradicts the solvability of Equation (3.3). More- over, ifx0/2 is even, then 4(x0/4)2−y20D/4 = 1, so part (1) of Theorem1tells us thatQ/2= 4; orx0/2 is odd and 2(x0/2)2−y20D/2 = 2 and part (2) of Theorem1 tells us thatQ/2= 4. Therefore, we may invoke Theorem1to conclude that
≡2 ≡0 (mod 4).
SinceD≡4 (mod 8), Theorem4allows us to conclude that A/2−1
2 +B/2−1
D/4 =A−1+B−1
D/4, and Theorem5 also tells us that
A−1+B−1
D/4 =
A/2−1+B/2−1
D/4 2
2 ,
so we have,
A/2−1+B/2−1
√D=
A/2−1+B/2−1
D/4 2
. It follows that
A/2−1+B/2−1
D/4 3
=X+Y√ D is a primitive element with norm−8, where
X =A3/2−1+ 3A/2−1B2/2−1D/4, Y = 3A2/2−1B/2−1/2 +B3/2−1D/8,
which are both integers sinceA/2−1B/2−1is odd. This completes the case where x0 ≡ −2 (modD/4). If x0 ≡ 2 (modD/4), then we may invoke Theorem 2 to argue in a similar fashion to the above. Thus, we have shown that part (1) implies part (2).
Assume part (2) holds. Then the solvability of Equation (3.2) implies that D is even and implies the solvability of the (X/2)2−Y2D/4 = ±2. Then using the solvability of Equation (3.1), we may invoke Theorems 2 and 3 to get that x0/2≡ ±1 (modD/4), which secures the result.
Example 1. If D = 4·19 = 76, then = 12, Q/2 = 4, Q/4 = Q3 = 8, x0 = 340 =A/2−1≡ −2 (modD/2), and the fundamental solution ofX2−DY2=−8 is (A2, B2) = (26,3).
If D = 4· 127, then = 32, Q/2 = 4, Q6 = 8, A/2−1 = A15 = x0 = 9461248 ≡ 2 (modD/2), and the fundamental solution of X2 −DY2 = 8 is (A5, B5) = (4350,193).
Remark 1. Note that whenD > 256, the solution of Equation (3.2) means that Qj = 8 for some j in the simple continued fraction expansion of√
D, wherej is odd when there is a minus sign and j is even when there is a plus sign. This may be seen using results from [3], for instance, where the continued fraction algorithm may be employed — see [3, Theorem 2.1.2, p. 44]. The latter tells us that all norms of principal (reduced) ideals inZ[√
D] must appear as one of the Qj. The existence of the primitive element of norm −8 implies the existence of a primitive reduced ideal of norm 8. The “reduced” part merely means (in this case), that 8 <√
D/2, namelyD > 256. When D < 256 we still have the solvability of the equation but Qj does not necessarily equal 8 for any j. For instance, ifD = 28, then = 4, Q/4 = 4, butQj = 8 for any j. Moreover, (X, Y) = (90,17) is the solution of the equation. Also, the solvability of Equation (3.2) cannot be removed from condition (2) of Theorem6. For instance, if D = 320, Q/2 = Q2 = 4, but x0 = 18 ≡ ±2 (modD/2). This tells us that this is a criterion, not merely for
central norm 4, rather as asserted in the header for the section, a criterion for central norm 4 associated with norm 8.
Remark 2. It is not a difficult task to show that the solvability of Equation (3.1), means thatx0≡ ±2 (modD) is not possible for oddD, which must in the case of that solvability, be congruent to 5 modulo 8. In other words, there is no analogue of Theorem 6 in the order Z[(1 +√
D)/2] , nor in the order Z[√
D] for odd D. Theorems2–3 provide the desired generalization of Lagrange to orders whereinD may be odd. The result by Lagrange is that for a primeD =p >2, with (x0, y0) the fundamental solution of the Pell Equationx2−Dy2= 1, thenx0≡1 (modp) if and only ifp≡7 (mod 8). Theorems 2–3 deliver the palatable fact that when (√
D) is even, then x0 ≡ ±1 (modD) if and only ifQ/2 = 2. The following is the analogous fact derived from Theorem6.
Theorem 7. IfD is a positive nonsquare integer, and(x0, y0)is the fundamental solution of Equation (3.1), then x0 ≡ ±2 (modD/2) if and only if Q/2 = 4 and Qj= 8 for somej.
The following is the analogue of another result in [7].
Theorem 8. If D = 4c, c is odd, (√
D) = is even with Q/2= 4, and Qj = 8 for somej, then the following hold:
(1) c≡3,7 (mod 16), if and only if j is even.
(2) c≡11,15 (mod 16) if and only ifj is odd.
Proof. First, we observe that it is a consequence of the results in [7] and in this paper that the only odd primes that may divideD in Theorem6areonlythose of the formp≡ ±1 (mod 8) oronlythose of the formp≡1,3 (mod 8), andD/4≡1 (mod 4).
SinceA2j−1−DB2j−1= (−1)j8, the following Jacobi symbol identity holds where D/4 =c:
1 = A2j−1
c =
(−1)j8 c
=
(−1)j c
2 c
= (−1)(4j(c−1)+c2−1)/8,
from which one easily deduces the results.
References
[1] G. Eisenstein,Aufgaben, J. Reine Angew. Math.27(1844), 86–88,ERAM 027.0784cj.
[2] P. Kaplan and K.S. Williams,Pell’s equationsx2−my2=−1,−4, and continued fractions, J. Number Theory23(1986), 169–182,MR0845899(87g:11035),Zbl 0596.10013.
[3] R.A. Mollin,Quadratics, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, 1996,MR1383823(97e:11135),Zbl 0858.11001.
[4] R.A. Mollin, Fundamental number theory with applications, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, 1998,Zbl 0943.11001.
[5] R.A. Mollin,Polynomials of Pellian type and continued fractions, Serdica Math. J.27(2001), 317–342,MR1899042(2003c:11139).
[6] R.A. Mollin,A continued fraction approach to the Diophantine equationax2−by2=±1, JP Journal Algebra, Number Theory, and Appl.4(2004), 159–207,MR2049695(2005a:11031), Zbl 1056.11017.
[7] R.A. Mollin,Lagrange, central norms, and quadratic Diophantine equations, International J.
Math. and Math. Sci.7(2005), 1039–1047.
[8] R.A. Mollin,Necessary and sufficient conditions for the central norm to equal a power of2 in the simple continued fraction expansion of√
Dfor any nonsquareD >1, Canadian Math.
Bulletin48(2005), 121–132,MR2118769(2005i:11013).
[9] A.J. Stephens and H.C. Williams,Some computational results on a problem of Eisenstein, Th´eorie des nombres (Quebec, PQ, 1987) (J-M De Koninck and C. Levesque, eds.), Walter de Gruyter, Berlin, New York (1989), 869–886,MR1024611(91c:11066),Zbl 0689.10024.
[10] H.C. Williams,Eisenstein’s problem and continued fractions, Utilitas Math.37(1990), 145–
158,MR1068514(91h:11018),Zbl 0718.11010.
Department of Mathematics and Statistics, University of Calgary, Calgary, Alberta, T2N 1N4, Canada
[email protected] http://www.math.ucalgary.ca/˜ramollin/
This paper is available via http://nyjm.albany.edu:8000/j/2005/11-25.html.