The purpose of this article is to show how to solve the Diophantine Equation Ax² + Bxy + Cy² + Dx + Ey + F = 0. The term Diophantine Equation means that the solutions (x, y) should be integer numbers. For example, the equation 4y² - 25y + 10 = 0 has solutions given by the horizontal line y = 2.5, but since 2.5 is not an integer number, we will say that the equation has no solutions.

There are several cases that depend on the values of A, B and C. The names are taken from the figures represented by the equation in the plane xy: a line, an ellipse, a parabola or a hyperbola (or two lines). These figures are the set of real solutions. In our situation, the set of solutions are represented by isolated point/s in the plane xy.

• Linear case: A = B = C = 0.
• Simple hyperbolic case: A = C = 0; B 0.
• Elliptical case: B² - 4AC < 0.
• Parabolic case: B² - 4AC = 0.
• Hyperbolic case: B² - 4AC > 0.
• Programs that use these methods

There are two cases: DE - BF = 0 (two lines parallel to x and y axes respectively) and DE - BF 0 (a hyperbola whose asymptotes are parallel to x and y axes).

In the first case a necessary condition to have solutions occurs when one of the parentheses equal zero, i.e., Bx + E = 0 or By + D = 0. Since B 0, we have solutions for:

In the second case the values of x and y are found by finding all divisors of DE - BF. Let d₁, d₂, ..., d_n be the set of divisors of DE - BF.So,

Example 2: Solve 2xy + 5x + 56y + 7 = 0.

In this case the divisors of DE - BF = 5*56 - 2*7 = 266 are: ±1, ±2, ±7, ±14, ±19, ±38, ±133, ±266.

Since (2x + 56) (2y + 5) = 266 we obtain:

• d₁ = 1: x = (1-56)/2 = -55/2, y = (266/1-5)/2 = 261/2
• d₂ = -1: x = (-1-56)/2 = -57/2, y=[266/(-1)-5]/2 = 271/2
• d₃ = 2: x = (2-56)/2 = -27, y = (266/2-5)/2 = 64
• d₄ = -2: x = (-2-56)/2 = -29, y = [266/(-2)-5]/2 = -69
• d₅ = 7: x = (7-56)/2 = -49/2, y = (266/7-5)/2 = 33/2
• d₆ = -7: x = (-7-56)/2 = -63/2, y = [266/(-7)-5]/2 = -43/2
• d₇ = 14: x = (14-56)/2 = -21, y = (266/14-5)/2 = 7
• d₈ = -14: x = (-14-56)/2 = -35, y = [266/(-14)-5]/2 = -12
• d₉ = 19: x = (19-56)/2 = -37/2, y = (266/19-5)/2 = 9/2
• d₁₀ = -19: x = (-19-56)/2 = -75/2, y = [266/(-19)-5]/2 = -19/2
• d₁₁ = 38: x = (38-56)/2 = -9, y = (266/38-5)/2 = 1
• d₁₂ = -38: x = (-38-56)/2 = -47, y = [266/(-38)-5]/2 = -6
• d₁₃ = 133: x = (133-56)/2 = 77/2, y = (266/133-5)/2 = -3/2
• d₁₄ = -133: x = (-133-56)/2 = -189/2, y = [266/(-133)-5]/2 = -7/2
• d₁₅ = 266: x = (266-56)/2 = 105, y = (266/266-5)/2 = -2
• d₁₆ = -266: x = (-266-56)/2 = -161, y = [266/(-266)-5]/2 = -3

The only 8 solutions to the requested equations are marked above in red.

Operating with the original quadratic equation:

Ax² + Bxy + Cy² + Dx + Ey + F = 0

Cy² + (Bx + E)y + (Ax² + Dx + F) = 0

For any value of x there will be two values of y except at the left and right extremes of the ellipse. In this case there will be only one value of y. To determine the location of the left and right extremes we should equal the square root to zero, so the previous expression returns only one value of y.

(Bx + E)² - 4C(Ax² + Dx + F) = 0

(B² - 4AC)x² + 2(BE - 2CD)x + (E² - 4CF) = 0

So the values of x should be between the roots of this equation. If the roots are not real, there will be no solutions to the original equation, else, all integer values of x should be replaced in equation (*) in order to find an integer value of y.

Example 3: Solve 42x² + 8xy + 15y² + 23x + 17y - 4915 = 0.

Since B² - 4AC = 8² - 4*42*15 = -2456 < 0 the equation is elliptical.

The values of x should be between the roots of (B² - 4AC)x² + 2(BE - 2CD)x + (E² - 4CF) = -2456x² - 1108x + 295189 = 0. The roots equal -11.19... and 10.74..., so we have to check the values of x from -11 to 10.

The only value of x that replaced in (*) makes y integer occurs for x = -11, where y = -1, therefore this is the only solution to this problem.

Since b² = 4ac is positive, we can choose g with the same sign of A. In this way a and c will be positive (or one of them zero).

The expression b² - 4ac = 0 implies that b²/4 = ac. Since gcd(a,c) = 1, both a and c are perfect squares.

Multiplying the original equation by :

g(ax² + bxy + cy²) + Dx + Ey + F = 0

g(x + y)² + Dx + Ey + F = 0

where for the sign of B/A is taken.

Adding and subtracting Dy:

g(x + y)² + D(x + y) - Dy + Ey + F = 0

Let u = x + y:    (i)

gu² + Du + (E - D)y + F = 0

(D - E)y = gu² + Du + F (ii)

There are two cases: D - E = 0 (two parallel lines) or D - E 0 (a parabola).

In the first case, D - E = 0.

From (ii): gu² + Du + F = 0

Since x and y should be integer numbers, the equation (i) implies that the number u (the root of the above equation) should be also integer. Let u₁ and u₂ be the roots of the above equation.

From (i) we have: x + y - u₁ = 0 and x + y - u₂ = 0 which can be solved with the methods for the linear equation.

In the second case, gu² + Du + F should be multiple of D - E.

Let u₀, u₁,... the values of u in the range 0 <= u < |D - E| for which the above condition holds.

So u = u_i + (D - E)t, where t is any integer number.   (iii)

Replacing (iii) in (ii):

(D - E)y = g[u_i + (D - E)t]² + D[u_i + (D - E)t] + F

y = g(D - E)t2 + (D + 2gui)t +

gui2 + Dui + F D - E

From (i) and (iii):

u = x + y = u_i + (D - E)t

x	=	g(E - D)t2 + (D - E - 2gui - D)t +
	+	ui - gui2 + Dui + F D - E

x	=	g(E - D)t2 + (- E - 2gui)t +
	+	ui(D - E) - gui2 + Dui + F D - E

x	=	g(E - D)t2 + (- E - 2gui)t -
	-	gui2 + Eui + F D - E

x = g(E - D)t2 - (E + 2gui)t - gui2 + Eui + F D - E y = g(D - E)t2 + (D + 2gui)t + gui2 + Dui + F D - E

Example 4: Find the solutions for 8 x² - 24 xy + 18 y² + 5x + 7y + 16 = 0

We have to calculate the values g, a, c, , , D - E and gu² + Du + F.

g = gcd(8, 18) = 2
a = 8/2 = 4
c = 18/2 = 9
= 2
= -3 (since B/A = -24/8 < 0)
D - E = -3 * 5 - 2 * 7 = -29 (second case)
gu² + Du + F = 4u² + 5u + 32

We have to determine the values of u in the range 0 <= u < 29 for which 4u² + 5u + 32 is multiple of 29.

The values of u are: u₀ = 2 and u₁ = 4.

For u₀ = 2:

For u₀ = 4:

• Find solutions of the homogeneous equation Ax² + Bxy + Cy² + F = 0
• Find recurrences among the solutions of the homogeneous equation
• Find solutions of the general quadratic equation
• Find recurrences among the solutions of the general quadratic equation

Ax² + Bxy + Cy² = -F

Multiplying by 4A:
4A²x² + 4ABxy + 4ACy² = -4AF
4A²x² + 4ABxy + B²y² - B²y² + 4ACy² = -4AF
(2Ax + By)² - (B² - 4AC)y² = -4AF

This can be interpreted as a difference of squares:

(2Ax + By + sqrt(B² - 4AC) y) (2Ax + By - sqrt(B² - 4AC) y) = -4AF
(2Ax + (B + sqrt(B² - 4AC))y) (2Ax + (B - sqrt(B² - 4AC))y) = -4AF

Since -4AF = 0, the condition to have more solutions is that B² - 4AC should be a perfect square.

Now the same method used for the linear equation (since the equation are represented by two lines in the plane xy intersecting at the point (0, 0)) can be used in order to find the solutions.

If F 0 and B² - 4AC = k² for some integer k, the parentheses in the equation above should be factors of -4AF.

Let u₁, u₂,... be the positive and negative divisors of -4AF.

Then we have the following set of two linear equations in two unknowns:

2Ax + (B+k)y = u_i
2Ax + (B-k)y = -4AF/u_i

So we have:

y = (u_i + 4AF/u_i) / (2k)
x = (u_i - (B+k)y)

We should discard the values of u_i that makes x or y non-integer.

F 0

If F is not a multiple of gcd(A, B, C), the equation has no solutions, otherwise we can divide all coefficients of the equation by this gcd.

If 4 F² < B² - 4AC, the solutions of the equation will be amongst the convergents of the continued fraction of the roots of the equation At² + Bt + C = 0.

The continued fraction expansion of a quadratic irrationality is periodic. Since B² - 4AC is not a perfect square the number of solutions will be infinite or none.

In the other hand, if 4 F² >= B² - 4AC solutions can be obtained as follows:

Let G = gcd(x,y), x = Gu and y = Gv.

The original equation is then: AG²u² + BG²uv + CG²v² + F = 0, so F will be multiple of G².

Dividing the equation by G²:

Au² + Buv + Cv² + F/G² = 0    (1).

Once the values of u and v are found, we can easily determine x = Gu and y = Gv.

So we can assume that gcd(x,y) = 1.

Let x = sy - Fz    (2).

Replacing in the original equation:

A(sy - Fz)² + B(sy - Fz)y + Cy² + F = 0

As²y² - 2AFsyz + AF²z² + Bsy² - BFyz + Cy² = -F

(As² + Bs + C) y² + (-2As - B)Fyz + AF²z² = - F

Dividing by -F:

-(As² + Bs + C) y² / F + (2As + B)yz - AFz² = 1    (3)

Now we must determine the values of s between 0 and F - 1 such that As² + Bs + C 0 (mod F). Once the values of y and z are found using continued fraction expansions of the roots of -(As² + Bs + C) t² / F + (2As + B)t - AF = 0, the value of x is found by (2). If no solutions are found amongst the convergents, there will be no solutions to (1).

If the original equation has solutions, there should be a solution to the previous congruence, except when gcd(A,B,F) > 1. In this case, if gcd(B,C,F) = 1 we should make the substitution y = sx - Fz    (4), so replacing in the original equation:

Ax² + Bx(sx - Fz) + C(sx - Fz)² + F = 0

Ax² + Bsx² - BFxz + Cs²x² - 2CFsxz + CF²z² = -F

(Cs² + Bs + A) x² + (-2Cs - B)Fxz + CF²z² = - F

Dividing by -F:

-(Cs² + Bs + A) x² / F + (2Cs + B)xz - CFz² = 1    (5).

Now we must determine the values of s between 0 and F - 1 such that Cs² + Bs + A 0 (mod F). Once the values of x and z are found using continued fraction expansions of the roots of -(Cs² + Bs + A) t² / F + (2Cs + B)t - CF = 0, the value of y is found by (4). If no solutions are found amongst the convergents, there will be no solutions to (1).

The equations (4) and (5) have no solutions when both gcd(A,B,F) and gcd(B,C,F) are greater than 1. In this case we will use the following approach:

Let i, j, m and n be four integers such that in - jm = 1    (6).

If x = iX + jY and y = mX + nY    (7) we obtain X = nx - jy and Y = -mx + iy    (8).

Since the transformation is reversible, we can convert any (x,y) to (X,Y) and vice versa. So we will work with (X,Y) and with these solutions will can compute the values of (x,y) that satisfies the original equation.

Ax² + Bxy + Cy² =
= A(iX+jY)² + B(iX+jY)(mX+nY) + C(mX+nY)² =
= aX² + bXY + cY²

a = Ai² + Bim + Cm²    (9)
b = 2Aij + Bin + Bjm + 2Cmn    (10)
c = Aj² + Bjn + Cn²    (11)

Since gcd(C, F) > 1 we have gcd(Ai² + Bim + Cm², C) = 1, so gcd(i, C) = 1 and gcd(Ai+Bm, C) = 1.

Since gcd(A, F) > 1 we have gcd(Ai² + Bim + Cm², A) = 1, so gcd(m, A) = 1 and gcd(Bi+Cm, A) = 1.

From (6), gcd(i, m) = 1.

If F 0 (mod p) (p prime):

A	B	C	i, m	Examples
A 0	B 0	C 0	Not applicable (gcd(A, B, C) = 1)
A 0	B 0	C 0	m 0	i 0, m 1
A 0	B 0	C 0	i 0, m 0	i 1, m 1
A 0	B 0	C 0	m 0, i -Cm/B	i 1-C, m B
A 0	B 0	C 0	i 0	i 1, m 0
A 0	B 0	C 0	i 0 or m 0	i 1, m 1
A 0	B 0	C 0	i 0, m -Ai/B	i B, m 1-A
A 0	B 0	C 0	i 0 or m 0	i 1, m 1

While it is possible to generate the values of i and m from their values modulo different primes, it is very tedious and it is not necessary, because from the table above, almost all values of i and m can be used. So it is better to use the following pseudocode in order to find both values:

    for i=0 to |F|-1
       for m=0 to i+1
          if gcd(i, m) = 1 and gcd(Ai2 + Bim + Cm2, F) = 1, end.
       next m
    next i

With the values of i and m just found, we can compute the values of j and n from (6) using the methods for the linear equation. Then we have to compute a, b and c using (9), (10) and (11), from which the set of solutions (X,Y) can be found. With the formula (7) we can find the set of solutions (x,y).

Credits: This method was e-mailed to me by Iain Davidson.

Example 5: Find some solutions for 18 x² + 41 xy + 19 y² - 24 = 0

First of all we must determine the gcd of all coefficients but the constant term, that is: gcd(18, 41, 19) = 1.

Dividing the equation by the greatest common divisor we obtain:
18 x² + 41 xy + 19 y² - 24 = 0

Let x = sy - fz, so [-(as² + bs + c)/f]y² + (2sa + b)yz - afz² = 1.

So 18 s² + 41 s + 19 should be multiple of 24.

This holds for s = 19.

• Let s = 19. Replacing in the above equation:
  304 y² + 725 yz + 432 z² = 1

  We have to find the continued fraction expansion of the roots of 304 t² + 725 t + 432 = 0, that is, (sqrt(313) - 725) /608

  The continued fraction expansion is:
  -2 + //1, 5, 8, 5, 1, 3, 1, 1, 2, 2, 1, 1, 3, 1, 5, 8, 1, 2, 17, 2, 1//

  where the periodic part is marked in bold (the period has 19 coefficients).

  The following table shows how the values of Y₀ and Z₀ are found (the third column are the values for 304 y² + 725 yz + 432 z²):

  cn	yn	zn
  	1	0
  -2	-2	1	198
  1	-1	1	11
  5	-7	6	-2
  8	-57	49	3
  5	-292	251	-12
  1	-349	300	4
  3	-1339	1151	-9
  1	-1688	1451	8
  1	-3027	2602	-6
  2	-7742	6655	6
  2	-18511	15912	-8
  1	-26253	22567	9
  1	-44764	38479	-4
  3	-160545	138004	12
  1	-205309	176483	-3
  5	-1 187090	1 020419	2
  8	-9 702029	8 339835	-11
  1	-10 889119	9 360254	6
  2	-31 480267	27 060343	-1
  17	-546 053658	469 386085	6
  2	-1123 587583	965 832513	-11
  1	-1669 641241	1435 218598	2
  8	-14480 717511	12447 581297	-3
  5	-74073 228796	63673 125083	12
  1	-88553 946307	76120 706380	-4
  3	-339735 067717	292035 244223	9
  1	-428289 014024	368155 950603	-8
  1	-768024 081741	660191 194826	6
  2	-1 964337 177506	1 688538 340255	-6
  2	-4 696698 436753	4 037267 875336	8
  1	-6 661035 614259	5 725806 215591	-9
  1	-11 357734 051012	9 763074 090927	4
  3	-40 734237 767295	35 015028 488372	-12
  1	-52 091971 818307	44 778102 579299	3
  5	-301 194096 858830	258 905541 384867	-2
  8	-2461 644746 688947	2116 022433 658235	11
  1	-2762 838843 547777	2374 927975 043102	-6
  2	-7987 322433 784501	6865 878383 744439	1
  17	-138547 320217 884294	119094 860498 698565	-6
  2	-285081 962869 553089	245055 599381 141569	11
  1	-423629 283087 437383	364150 459879 840134	-2

  Notice that y_n = c_n y_n-1 + y_n-2 and z_n = c_n z_n-1 + z_n-2.

  The signs in the third column are alternated, so the numbers will repeat after an even number of convergents. Therefore two entire periods should be considered if the period length is odd. If it is even, only one period should be considered. With these solutions and the recurrence relation to be developed in the next section we can find all solutions of the homogeneous equation.

  Y₀ = -7987 322433 784501 (16 digits)
  Z₀ = 6865 878383 744439 (16 digits)
  Since X₀ = 19 Y₀ + 24 Z₀:
  

  X0 = 13021 954967 961017 (17 digits) Y0 = -7987 322433 784501 (16 digits)

  Since the equation Ax² + Bxy + Cy² + F = 0 does not change when x is replaced by -x and y is replaced by -y simultaneously we have another solution:

  X0 = -13021 954967 961017 (17 digits) Y0 = 7987 322433 784501 (16 digits)

  Now we must consider the continued fraction of the other root: (-sqrt(313) - 725) /608

  The expansion is -2 + //1, 3, 1, 1, 17, 2, 1, 8, 5, 1, 3, 1, 1, 2, 2, 1, 1, 3, 1, 5, 8, 1, 2// (the period has 19 coefficients).

  The following table shows how the values of Y₀ and Z₀ are found (the third column are the values for 304 y² + 725 yz + 432 z²):

  cn	yn	zn
  	1	0
  -2	-2	1	198
  1	-1	1	11
  3	-5	4	12
  1	-6	5	-6
  1	-11	9	1
  17	-193	158	-6
  2	-397	325	11
  1	-590	483	-2
  8	-5117	4189	3
  5	-26175	21428	-12

  This table is not complete, but there are no solutions in the section not shown.

  Y₀ = 11
  Z₀ = -9
  Since X₀ = 19 Y₀ + 24 Z₀:

  X0 = -7 Y0 = 11

  X0 = 7 Y0 = -11

We have to find the continued fraction expansion of the roots of 18 t² + 41 t + 19 = 0, that is, (sqrt(313) - 41) / 38

The continued fraction expansion is:
-1 + //2, 1, 5, 8, 1, 2, 17, 2, 1, 8, 5, 1, 3, 1, 1, 2, 2, 1, 1, 3//

where the periodic part is marked in bold (the period has 19 coefficients).

The following table shows how the values of U₀ and V₀ are found (the third column are the values for 18 u² + 41 uv + 19 v²):

As explained above, x = 2u and y = 2v, so:

The other root of the equation 18 t² + 41 t + 19 = 0 is (-sqrt(313) - 41) / 38

Its continued fraction expansion is:
-2 + //2, 1, 2, 2, 1, 1, 3, 1, 5, 8, 1, 2, 17, 2, 1, 8, 5, 1, 3, 1//

where the periodic part is marked in bold (the period has 19 coefficients).

The following table shows how the values of U₀ and V₀ are found (the third column are the values for 18 u² + 41 uv + 19 v²):

As explained above, x = 2u and y = 2v, so:

X_n+1 = P X_n + Q Y_n
Y_n+1 = R X_n + S Y_n

where P, Q, R and S should be determined.

Let M(x, y) = Ax² + Bxy + Cy² = M and N(u, v) = u² + Buv + ACv² = N.

M(p, q) = Ap² + Bpq + Cq²

M(p, q)/A = p² + (B/A)pq + (C/A)q²

M(p, q)/A = p² + Dpq + Eq²

M(p/q, 1)/A = (p/q)² + D(p/q) + E    (12)

The roots of M(p/q, 1)/A = (p/q - J) (p/q - J') = 0  (13) are:

It can be easily shown by equating (12) and (13) that:

J² = -DJ - E    (14)
J'² = -DJ' - E    (15)
J + J' = -D    (16)
JJ' = E    (17)

The roots of N(p/q, 1) = (p/q - K) (p/q - K') = 0 are:

so K = AJ, K' = AJ'    (18)

M(p, q)/A = (p - Jq)(p - J'q) = M    (19)

N(r, s) = (r - Ks)(r - K's) = N    (20)

From (18) we obtain:

(p - Jq)(r - Ks) = (p - Jq)(r - AJs) = (pr - AJps - Jqr + AJ²qs)

From (14) we obtain:

[pr - AJps - Jqr + A(-DJ - E)qs] = (pr - AEqs) - (Aps + qr + AEqs)J = (pr - Cqs) - (Aps + qr + Bqs)J    (21)

From (18) we obtain:

(p - J'q)(r - K's) = (p - J'q)(r - AJ's) = (pr - AJ'ps - J'qr + AJ'²qs)

From (15) we obtain:

[pr - AJ'ps - J'qr + A(-DJ' - E)qs] = (pr - AEqs) - (Aps + qr + AEqs)J' = (pr - Cqs) - (Aps + qr + Bqs)J'    (22)

Let X = pr - Cqs and Y = Aps + qr + Bqs    (23).

Multiplying (21) by (22) we obtain:

(M(p, q)/A) N(r, s) = (X - YJ) (X - YJ') = X² - (J + J')XY + JJ'Y²

Multiplying equations (16) and (17) we obtain: (M(p, q)/A) N(r, s) = X² + DY + EY²

Multiplying by A we get (from (19) and (20)):

AX² + BXY + CY² = MN

Letting M = -F and N = 1 we can see that X and Y are also solutions of the original equation.

Let r and s be a solution to N(r, s) = r² + Brs + ACs² = 1,
X_n = p, Y_n = q, X_n+1 = X and Y_n+1 = Y (since the last two pairs of numbers are solutions to the original equation).

From (23) we obtain:

X_n+1 = rX_n - CsY_n+1
Y_n+1 = AsX_n + rY_n+1 + BsY_n+1

This means that:

Credits: This method was e-mailed to me by Iain Davidson. I've made some modifications.

Multiplying the equation by 4A:

4A²x² + 4ABxy + 4ACy² + 4ADx + 4AEy + 4AF = 0
(2Ax + By + D)² - (By + D)² + 4ACy² + 4AEy + 4AF = 0
(2Ax + By + D)² + (4AC - B²)y² + (4AE - 2BD)y + (4AF - D²) = 0

Let x₁ = 2Ax + By + D
and g = gcd(4AC - B², 2AE - BD).

Multiplying by (4AC - B²)/g:

where:

X_n+1 = P X_n + Q Y_n + K
Y_n+1 = R X_n + S Y_n + L

Replacing in the original equation x by Px + Qy + K and y by Rx + Sy + L:

A(Px + Qy + K)² + B(Px + Qy + K) (Rx + Sy + L) + C(Rx + Sy + L)² + D(Px + Qy + K) + E(Rx + Sy + L) + F = 0

(AP² + BPR + CR²)x² + (2APQ + B(PS+QR) + 2CRS)xy + (AQ² + BQS + CS²)y² + (2ABP + B(KR+LP) + 2CLR + DP + ER)x + (2AKQ + B(KS+LQ) + 2CLS + DQ + ES)y + (AK² + BKL + CL² + DK + EL + F) = 0    (29)

Now we will investigate the values inside the parentheses.

• From (24) and (26) we obtain:

  AP² + BPR + CR² = Ar² + BrAs + CA²s² = A(r² + Brs + ACs²)

  From equation (28) we obtain:

  AP² + BPR + CR² = A    (30)

• From (24) to (27) we obtain:

  2APQ + B(PS+QR) + 2CRS = 2Ar(-Cs) + B[r(r+Bs)+(-Cs)As] + 2CAs(r+Bs) = -2ACrs + B(r²+Bs-ACs²) + 2ACrs + 2ABCs² = B(r²+Bs+ACs²)

  From equation (28) we obtain:

  2APQ + B(PS+QR) + 2CRS = B    (31)

• From (25) and (27) we obtain:

  AQ² + BQS + CS² = AC²s² + B(-Cs)(r+Bs) + C(r+Bs)² = AC²s² - BCrs - B²Cs² + Cr² + 2BCrs + B²Cs² = AC² + BCrs + Cr² = C(r² + Brs + ACs²)

  From equation (28) we obtain:

  AQ² + BQS + CS² = C    (32)

These two equations are equivalent to:

(2AP+BR)K + (BP+2CR)L = -D(P-1) - ER
and (2AQ+BS)K + (BQ+2CS)L = -DQ - E(S-1)

Solving the equation system for K and L:

Since PS - QR = r(r+Bs) - (-Cs)As = r² + Brs + ACs² = 1, these equations can be simplified to:

Now we must show that the expression inside the right parentheses of (29) equals F. This means that we have to prove that the values of K and L just found verify the equation Z = AK² + BKL + CL² + DK + EL = 0    (33).

The expansion is very complicated and will not be reproduced here, but fortunately it is a multiple of 4AC-B², so it cancels the square in the denominator, since it is (4AC-B²)².

This means that Z(4AC-B²) is an integer number and it is equal to:

AD²Q² - 2ADEPQ + AE²P² - AE² + BD²QS - BDEPS - BDEQR + BDE + BE²PR + CD²S² - CD² - 2CDERS + CE²R²

Reordering terms:

AD²Q² + BD²QS + CD²S² - CD² - 2ADEPQ - BDEPS - BDEQR - 2CDERS + BDE + AE²P² + BE²PR + CE²R² - AE²

D²(AQ² + BQS + CS²) - CD² - DE(2APQ + BPS + BQR + 2CRS) + BDE + E²(AP² + BPR + CR²) - AE²

From (30), (31) and (32):

Z(4AC-B²) = CD² - CD² - BDE + BDE + AE² - AE² = 0

This means that Z = 0, so (33) holds, then (29) holds too.

To continue simplifying the expressions we should note the following:

K_D = BQ - 2C(1 - S)
K_D = B(-Cs) - 2C(1 - r - Bs)
K_D = -BCs - 2C + 2Cr + 2BCs
K_D = C(-2 + 2r + Bs)    (35)
K_D = C(P + S - 2)

L_E = BR - 2A(1 - P)
L_E = ABs - 2A + 2Ar
L_E = A(-2 + 2r + Bs)
L_E = A(P + S - 2)

K_E = B(1 - P) - 2CR
K_E = B(1 - r) - 2ACs
K_E = B - Br - 2ACs    (36)

L_D = B(1 - S) - 2AQ
L_D = B(1 - r - Bs) + 2ACs
L_D = B - Br - B²s + 2ACs

L_D - K_E = (4AC - B²)s    (37)

So:

Generally the numerators will not be multiple of 4AC - B², so using this formula we cannot find a recurrence for all values of D and E.

For some values of D and E there will be solutions, as shown below. Using equations (24) - (27):

K_DL_E - K_EL_D = 4ACr² + 4ABCrs + 4A²C²s² - B²r² - B³rs - AB²Cs² - 4ABCs - B³s + 4AC - B² - 8ACr + 2B²r =

= (4AC - B²) (r² + Brs + ACs²) - (4AC - B²)Bs + (4AC - B²) - (4AC - B²)2r =

= (4AC - B²) (2 - 2r - Bs)

The equal signs shown below mean congruence mod 4AC - B².

K_DL_E - K_EL_D = 0 => K_D/K_E = L_D/L_E    (38)

Since K and L must be integers they should be (from (34)):

K_DD + K_EE = 0 => E = (-K_D/K_E)D    (39)

L_DD + L_EE = 0 => E = (-L_D/L_E)D

These equations are consistent because of equation (38).

In some cases (see example 6) we can find a recurrence by using the solutions -r and -s since (-r)² + B(-r)(-s) + AC(-s)² = r² + Brs + ACs² = 1.

If no solutions were found (as in example 7), we should use the next pair of solutions (r₁, s₁) of r² + Brs + ACs² = 1 because there will always be solutions as shown below.

First we should find r₁ and s₁ from r and s. To do that we use the formulas (24) - (28).

r₁ = r r + (-ACs)s = r² - ACs²
s₁ = s r + (r + Bs)s = 2rs + Bs²

Now the values of r and s should be replaced by r₁ and s₁.

From (24): P₁ = r₁ = r² - ACs²
From (25): Q₁ = -Cs₁ = -C(2rs + Bs²)
From (26): R₁ = As₁ = A(2rs + Bs²)
From (27): S₁ = r₁ + Bs₁ = r² + 2Brs + (B² - AC)s²

From (35):

K_1D = C(-2 + 2r₁ + Bs₁)
K_1D = C[-2 + 2(r² - ACs²) + B(2rs + Bs²)]
K_1D = C[-2 + 2(r² + Brs + ACs²) - 4ACs² + B²s²]
K_1D = C[-2 + 2 + (B² - 4AC)s²]
K_1D = (B² - 4AC)Cs²

From (36):

K_1E = B - Br₁ - 2ACs₁
K_1E = B - Br² + ABCr² - 4ACrs - 2ABCr²
K_1E = B - B(r² + ACs²) - 4ACrs
K_1E = B - B(r² + ACs² + Brs - Brs) - 4ACrs
K_1E = B - B(1 - Brs) - 4ACrs
K_1E = (B² - 4AC)rs

From (37):

L_1D - K_1E = (4AC - B²)s₁
L_1D = (B² - 4AC) (rs - 2rs - Bs²)
L_1D = (B² - 4AC) (-rs - Bs²)

Therefore:

So, finally:

Notice that in this case, in order to find the solutions using the continued fraction method, we will need to compute two entire periods if the period length is even and four if it is odd.

Example 6: 3x² + 13xy + 5y² + Dx + Ey + F = 0

P = r = -8351
Q = -Cs = -32625
R = As = 19575
S = r + Bs = 76474

The numerator of K (or L) is not a multiple of the denominator (4AC - B² = -109), so there is no recurrence with the values of P, Q, R, S shown above, except for special cases (according to (39), when E 93 D (mod 109)).

Using the solution r = 8351, s = -6525 we get:

P = r = 8351
Q = -Cs = 32625
R = As = -19575
S = r + Bs = -76474

So, the recursive relation between solutions is:

Check: Knowing that x = 2, y = 3 is a solution of 3x² + 13xy + 5y² - 11x - 7y - 92 = 0, find other two solutions.

Replacing D = -11 and E = -7 in the previous equations:

X_n+1 = 8351 X_n - 32625 Y_n - 28775
Y_n+1 = -19575 X_n + 76474 Y_n + 67450

So, replacing here X₀ = 2 and Y₀ = 3, we find X₁ = 85802 and Y₁ = -201122.

and replacing X₁ = 85802 and Y₁ = -201122, we find X₂ = -5845 101523 and Y₂ = 13701 097128.

Replacing these values in the original equation we can check that these values are correct.

Example 7: 3x² + 14xy + 6y² + Dx + Ey + F = 0

P = r = -391
Q = -Cs = -1638
R = As = 819
S = r + Bs = 3431

The numerator of L is not a multiple of the denominator (4AC - B² = -124), so there is no recurrence with the values of P, Q, R, S shown above, except for special cases (when E is even).

Using the solution r = 391, s = -273 we get:

P = r = 391
Q = -Cs = 1638
R = As = -819
S = r + Bs = -3431

The numerator of K (or L) is not a multiple of the denominator (4AC - B² = -124), so there is no recurrence with the values of P, Q, R, S shown above, except for special cases.

Using (40) and (41):

P₁ = r² - ACs² = -1188641
Q₁ = -Cs(2r+Bs) = -4979520
R₁ = As(2r+Bs) = 2489760
S₁ = r² + 2Brs + (B²-AC)s² = 10430239
K₁ = -CDs² - Ers = -106743 D + 447174 E
L₁ = Ds(r+Bs) - AEs² = 936663 D - 223587 E

So, the recursive relation between solutions is:

Check: Knowing that x = 4, y = 7 is a solution of 3x² + 14xy + 6y² - 17x - 23y - 505 = 0, find other two solutions.

Replacing D = -17 and E = -23 in the previous equations:

X_n+1 = -1188641 X_n - 4979520 Y_n + 5146869

Y_n+1 = 2489760 X_n + 10430239 Y_n - 10780770

So, replacing here X₀ = 4 and Y₀ = 7, we find X₁ = -34 464335 and Y₁ = 72 189943.

and replacing X₁ = -34 464335 and Y₁ = 72 189943, we find X₂ = -318 505538 201756 and Y₂ = 667 150425 396007.

Replacing these values in the original equation we can check that these values are correct.

Press here to run a JavaScript program compatible with Internet Explorer 3.0 or Netscape Navigator 3.0 or later (not finished yet).

Press here to run a Java program compatible with Internet Explorer 4.0 or Netscape Navigator 4.0 or later. It is about 50 times faster than the previous program.

Both programs run in two modes: solution only and step-by-step. In the last mode, the program explains how the results are found.

Click here to send me your comments.

Last modification: December 17th, 2000.