The purpose of this article is to show how to solve the Diophantine Equation Ax^{2} + Bxy + Cy^{2} + Dx + Ey + F = 0. The term Diophantine Equation means that the solutions (x, y) should be integer numbers. For example, the equation 4y^{2} - 20y + 25 = 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.
If F is multiple of g we can divide all three coefficients by g thus obtaining:
dx + ey = -f (where d=D/g, e=E/g and f=F/g).
We will use now the Extended Euclid's Algorithm that can be used to find integers u' and v' such that uu'+vv' = ±gcd(u, v) (where the sign depends on the sign of d and e and the exact implementation of the algorithm).
We can let u = d, v = e. Once the values of u' and v' are found so that du'+ev' = ±1 (since gcd(d, e)=1) we can multiply the equation by -f to obtain:
du'+ev' = ±1 => d(±fu')+e(±fv') = -f => d(±fu')+det+e(±fv')-det = -f => d(et±fu')+e(-dt±fv') = f
So the general solution set is:
x = et ± fu'
y = -dt ± fv'
t = any integer
gcd(D, E) = gcd(10, 84) = 2. Since the constant term is also multiple of 2, we will divide the equation by this gcd.
The equation is now: 5x + 42y + 8 = 0.
Now we must apply the Generalized Euclidean algorithm:
Multiplying the last equation by -F = -8 we obtain:
(-136) * 5 + 16 * 42 = -8
Adding and subtracting de t = 5 * 42 t we obtain:
(-136 + 42 t) * 5 + (16 - 5 t) * 42 = -8
So, the solution is given by the set:
x = -136 + 42 t
y = 16 - 5 t
where t is any integer number.
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_{1}, d_{2}, ..., d_{n} be the set of divisors of DE - BF. Then,
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:
The only 8 solutions to the requested equations are marked above in red.
Since the ellipse is a closed figure, the number of solutions will be finite.
Operating with the original quadratic equation:
Ax^{2} + Bxy + Cy^{2} + Dx + Ey + F = 0
Cy^{2} + (Bx + E)y + (Ax^{2} + Dx + F) = 0
y = -(Bx + E) ± (Bx + E)2 - 4C(Ax2 + Dx + F) 2C (*)
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)^{2} - 4C(Ax^{2} + Dx + F) = 0
(B^{2} - 4AC)x^{2} + 2(BE - 2CD)x + (E^{2} - 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^{2} + 8xy + 15y^{2} + 23x + 17y - 4915 = 0.
Since B^{2} - 4AC = 8^{2} - 4*42*15 = -2456 < 0 the equation is elliptical.
The values of x should be between the roots of (B^{2} - 4AC)x^{2} + 2(BE - 2CD)x + (E^{2} - 4CF) = -2456x^{2} - 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^{2} = 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^{2} - 4ac = 0 implies that b^{2}/4 = ac. Since gcd(a,c) = 1, both a and c are perfect squares.
Multiplying the original equation by :
g(ax^{2} + bxy + cy^{2}) + Dx + Ey + F = 0
g(x + y)^{2} + Dx + Ey + F = 0
where for the sign of B/A is taken.
Adding and subtracting Dy:
g(x + y)^{2} + D(x + y) - Dy + Ey + F = 0
Let u = x + y: (i)
gu^{2} + Du + (E - D)y + F = 0
(D - E)y = gu^{2} + 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^{2} + 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_{1} and u_{2} be the roots of the above equation.
From (i) we have: x + y - u_{1} = 0 and x + y - u_{2} = 0 which can be solved with the methods for the linear equation.
In the second case, gu^{2} + Du + F should be multiple of D - E.
Let u_{0}, u_{1},... 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]^{2} + D[u_{i} + (D - E)t] + F
y = g(D - E)t^{2} + (D + 2gu_{i})t + gu_{i}^{2} + Du_{i} + F D - E
From (i) and (iii):
u = x + y = u_{i} + (D - E)t
x = g(E - D)t^{2} + (D - E - 2gu_{i} - D)t + u_{i} - gu_{i}^{2} + Du_{i} + F D - E
x = g(E - D)t^{2} + (- E - 2gu_{i})t + u_{i}(D - E) - gu_{i}^{2} - Du_{i} - F D - E
x = g(E - D)t^{2} + (- E - 2gu_{i})t - gu_{i}^{2} + Eu_{i} + F D - E
Example 4: Find the solutions for 8 x^{2} - 24 xy + 18 y^{2} + 5x + 7y + 16 = 0
We have to calculate the values g, a, c, , , D - E and gu^{2} + 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^{2} + Du + F = 4u^{2} + 5u + 32
We have to determine the values of u in the range 0 ≤ u < 29 for which 4u^{2} + 5u + 32 is multiple of 29.
The values of u are: u_{0} = 2 and u_{1} = 4.
For u_{0} = 2:
x = -174 t^{2} - 17 t - 2
y = -116 t^{2} - 21 t - 2
For u_{0} = 4:
x = -174 t^{2} - 41 t - 4
y = -116 t^{2} - 37 t - 4
Ax^{2} + Bxy + Cy^{2} = -F
Multiplying by 4A:
4A^{2}x^{2} + 4ABxy + 4ACy^{2} = -4AF
4A^{2}x^{2} + 4ABxy + B^{2}y^{2} - B^{2}y^{2} + 4ACy^{2} = -4AF
(2Ax + By)^{2} - (B^{2} - 4AC)y^{2} = -4AF
This can be interpreted as a difference of squares:
(2Ax + By + B2 - 4AC y) (2Ax + By - B2 - 4AC y) = -4AF
(2Ax + (B + B2 - 4AC )y) (2Ax + (B - B2 - 4AC )y) = -4AF
Since -4AF = 0, the condition to have more solutions is that B^{2} - 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^{2} - 4AC = k^{2} for some integer k, the parentheses in the equation above should be factors of -4AF.
Let u_{1}, u_{2},... 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 2A
We should discard the values of u_{i} that makes x or y non-integer.
Let's consider now the case F ≠ 0 and B^{2} - 4AC not a perfect square.
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^{2} < B^{2} - 4AC, the solutions of the equation will be amongst the convergents of the continued fraction of the roots of the equation At^{2} + Bt + C = 0.
The continued fraction expansion of a quadratic irrationality is periodic. Since B^{2} - 4AC is not a perfect square the number of solutions will be infinite or none.
In the other hand, if 4 F^{2} ≥ B^{2} - 4AC solutions can be obtained as follows:
Let G = gcd(x,y), x = Gu and y = Gv.
The original equation is then: AG^{2}u^{2} + BG^{2}uv + CG^{2}v^{2} + F = 0, so F will be multiple of G^{2}.
Dividing the equation by G^{2}:
Au^{2} + Buv + Cv^{2} + F/G^{2} = 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)^{2} + B(sy - Fz)y + Cy^{2} + F = 0
As^{2}y^{2} - 2AFsyz + AF^{2}z^{2} + Bsy^{2} - BFyz + Cy^{2} = -F
(As^{2} + Bs + C) y^{2} + (-2As - B)Fyz + AF^{2}z^{2} = - F
Dividing by -F:
-(As^{2} + Bs + C) y^{2} / F + (2As + B)yz - AFz^{2} = 1 (3)
Now we must determine the values of s between 0 and F - 1 such that As^{2} + Bs + C ≡ 0 (mod F). Once the values of y and z are found using continued fraction expansions of the roots of -(As^{2} + Bs + C) t^{2} / 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^{2} + Bx(sx - Fz) + C(sx - Fz)^{2} + F = 0
Ax^{2} + Bsx^{2} - BFxz + Cs^{2}x^{2} - 2CFsxz + CF^{2}z^{2} = -F
(Cs^{2} + Bs + A) x^{2} + (-2Cs - B)Fxz + CF^{2}z^{2} = - F
Dividing by -F:
-(Cs^{2} + Bs + A) x^{2} / F + (2Cs + B)xz - CFz^{2} = 1 (5).
Now we must determine the values of s between 0 and F - 1 such that Cs^{2} + Bs + A ≡ 0 (mod F). Once the values of x and z are found using continued fraction expansions of the roots of -(Cs^{2} + Bs + A) t^{2} / 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^{2} + Bxy + Cy^{2} =
= A(iX+jY)^{2} + B(iX+jY)(mX+nY) + C(mX+nY)^{2} =
= aX^{2} + bXY + cY^{2}
where:
a = Ai^{2} + Bim + Cm^{2} (9)
b = 2Aij + Bin + Bjm + 2Cmn (10)
c = Aj^{2} + Bjn + Cn^{2} (11)
So we have to find the values of i and m such that a = Ai^{2} + Bim + Cm^{2} is relatively prime to F.
Since gcd(C, F) > 1 we have gcd(Ai^{2} + Bim + Cm^{2}, C) = 1, so gcd(i, C) = 1 and gcd(Ai+Bm, C) = 1.
Since gcd(A, F) > 1 we have gcd(Ai^{2} + Bim + Cm^{2}, 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
k = Ai^{2} + Bim + Cm^{2}
if gcd(k, F) = 1, end.
end if
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).
This method was e-mailed to me by Iain Davidson.
Example 5: Find some solutions for 18 x^{2} + 41 xy + 19 y^{2} - 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^{2} + 41 xy + 19 y^{2} - 24 = 0
Let x = sy - fz, so [-(as^{2} + bs + c)/f]y^{2} + (2sa + b)yz - afz^{2} = 1.
So 18 s^{2} + 41 s + 19 should be multiple of 24.
This holds for s = 19.
We have to find the continued fraction expansion of the roots of 304 t^{2} + 725 t + 432 = 0, that is, t = √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_{0} and Z_{0} are found (the third column are the values for P(y, z) = 304 y^{2} + 725 yz + 432 z^{2}):
c_{n} | y_{n} | z_{n} | P(y_{n}, z_{n}) |
---|---|---|---|
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_{0} = -7987 322433 784501 16
Z_{0} = 6865 878383 744439 16
Since X_{0} = 19 Y_{0} + 24 Z_{0}:
Since the equation Ax^{2} + Bxy + Cy^{2} + F = 0 does not change when x is replaced by -x and y is replaced by -y simultaneously we have another solution:
Now we must consider the continued fraction of the other root: t = - √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_{0} and Z_{0} are found (the third column are the values for P(y, z) = 304 y^{2} + 725 yz + 432 z^{2}):
c_{n} | y_{n} | z_{n} | P(y_{n}, z_{n}) |
---|---|---|---|
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_{0} = 11
Z_{0} = -9
Since X_{0} = 19 Y_{0} + 24 Z_{0}:
We have to find the continued fraction expansion of the roots of 18 t^{2} + 41 t + 19 = 0, that is, t = √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_{0} and V_{0} are found (the third column are the values for P(u, v) = 18 u^{2} + 41 uv + 19 v^{2}):
c_{n} | u_{n} | v_{n} | P(u_{n}, v_{n}) |
---|---|---|---|
1 | 0 | ||
-1 | -1 | 1 | -4 |
2 | -1 | 2 | 12 |
1 | -2 | 3 | -3 |
5 | -11 | 17 | 2 |
8 | -90 | 139 | -11 |
1 | -101 | 156 | 6 |
2 | -292 | 451 | -1 |
17 | -5065 | 7823 | 6 |
2 | -10422 | 16097 | -11 |
1 | -15487 | 23920 | 2 |
8 | -134318 | 207457 | -3 |
5 | -687077 | 1 061205 | 12 |
1 | -821395 | 1 268662 | -4 |
3 | -3 151262 | 4 867191 | 9 |
1 | -3 972657 | 6 135853 | -8 |
1 | -7 123919 | 11 003044 | 6 |
2 | -18 220495 | 28 141941 | -6 |
2 | -43 564909 | 67 286926 | 8 |
1 | -61 785404 | 95 428867 | -9 |
1 | -105 350313 | 162 715793 | 4 |
3 | -377 836343 | 583 576246 | -12 |
1 | -483 186656 | 746 292039 | 3 |
5 | -2793 769623 | 4315 036441 | -2 |
8 | -22833 343640 | 35266 583567 | 11 |
1 | -25627 113263 | 39581 620008 | -6 |
2 | -74087 570166 | 114429 823583 | 1 |
17 | -1 285115 806085 | 1 984888 620919 | -6 |
2 | -2 644319 182336 | 4 084207 065421 | 11 |
1 | -3 929434 988421 | 6 069095 686340 | -2 |
8 | -34 079799 089704 | 52 636972 556141 | 3 |
5 | -174 328430 436941 | 269 253958 467045 | -12 |
1 | -208 408229 526645 | 321 890931 023186 | 4 |
3 | -799 553119 016876 | 1234 926751 536603 | -9 |
1 | -1007 961348 543521 | 1556 817682 559789 | 8 |
1 | -1807 514467 560397 | 2791 744434 096392 | -6 |
2 | -4622 990283 664315 | 7140 306550 752573 | 6 |
2 | -11053 495034 889027 | 17072 357535 601538 | -8 |
1 | -15676 485318 553342 | 24212 664086 354111 | 9 |
1 | -26729 980353 442369 | 41285 021621 955649 | -4 |
3 | -95866 426378 880449 | 148067 728952 221058 | 12 |
As explained above, x = 2u and y = 2v, so:
The other root of the equation 18 t^{2} + 41 t + 19 = 0 is t = - √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_{0} and V_{0} are found (the third column are the values for P(u, v) = 18 u^{2} + 41 uv + 19 v^{2}):
c_{n} | u_{n} | v_{n} | P(u_{n}, v_{n}) |
---|---|---|---|
1 | 0 | ||
-2 | -2 | 1 | 9 |
2 | -3 | 2 | -8 |
1 | -5 | 3 | 6 |
2 | -13 | 8 | -6 |
2 | -31 | 19 | 8 |
1 | -44 | 27 | -9 |
1 | -75 | 46 | 4 |
3 | -269 | 165 | -12 |
1 | -344 | 211 | 3 |
5 | -1989 | 1220 | -2 |
8 | -16256 | 9971 | 11 |
1 | -18245 | 11191 | -6 |
2 | -52746 | 32353 | 1 |
17 | -914927 | 561192 | -6 |
2 | -1 882600 | 1 154737 | 11 |
1 | -2 797527 | 1 715929 | -2 |
8 | -24 262816 | 14 882169 | 3 |
5 | -124 111607 | 76 126774 | -12 |
1 | -148 374423 | 91 008943 | 4 |
3 | -569 234876 | 349 153603 | -9 |
1 | -717 609299 | 440 162546 | 8 |
1 | -1286 844175 | 789 316149 | -6 |
2 | -3291 297649 | 2018 794844 | 6 |
2 | -7869 439473 | 4826 905837 | -8 |
1 | -11160 737122 | 6845 700681 | 9 |
1 | -19030 176595 | 11672 606518 | -4 |
3 | -68251 266907 | 41863 520235 | 12 |
1 | -87281 443502 | 53536 126753 | -3 |
5 | -504658 484417 | 309544 154000 | 2 |
8 | -4 124549 318838 | 2 529889 358753 | -11 |
1 | -4 629207 803255 | 2 839433 512753 | 6 |
2 | -13 382964 925348 | 8 208756 384259 | -1 |
17 | -232 139611 534171 | 142 388292 045156 | 6 |
2 | -477 662187 993690 | 292 985340 474571 | -11 |
1 | -709 801799 527861 | 435 373632 519727 | 2 |
8 | -6156 076584 216578 | 3775 974400 632387 | -3 |
5 | -31490 184720 610751 | 19315 245635 681662 | 12 |
1 | -37646 261304 827329 | 23091 220036 314049 | -4 |
3 | -144428 968635 092738 | 88588 905744 623809 | 9 |
1 | -182075 229939 920067 | 111680 125780 937858 | -8 |
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^{2} + Bxy + Cy^{2} = M and N(u, v) = u^{2} + Buv + ACv^{2} = N.
M(p, q) = Ap^{2} + Bpq + Cq^{2}
M(p, q)/A = p^{2} + (B/A)pq + (C/A)q^{2}
M(p, q)/A = p^{2} + Dpq + Eq^{2}
M(p/q, 1)/A = (p/q)^{2} + D(p/q) + E (12)
The roots of M(p/q, 1)/A = (p/q - J) (p/q - J') = 0 (13) are:
J = -B + B2 - 4AC 2A and J' = -B - B2 - 4AC 2A
It can be easily shown by equating (12) and (13) that:
J^{2} = -DJ - E (14)
J'^{2} = -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:
K = -B + B2 - 4AC 2A and K' = -B - B2 - 4AC 2A
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^{2}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'^{2}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^{2} - (J + J')XY + JJ'Y^{2}
Multiplying equations (16) and (17) we obtain: (M(p, q)/A) N(r, s) = X^{2} + DY + EY^{2}
Multiplying by A we get (from (19) and (20)):
AX^{2} + BXY + CY^{2} = 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^{2} + Brs + ACs^{2} = 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:
X_{n+1} = P X_{n} + Q Y_{n}
Y_{n+1} = R X_{n} + S Y_{n}
P = r (24)
Q = -Cs (25)
R = As (26)
S = r + Bs (27)
where
r^{2} + Brs + ACs^{2} = 1 (28)
Credits: This method was e-mailed to me by Iain Davidson. I've made some modifications.
Multiplying the equation by 4A:
4A^{2}x^{2} + 4ABxy + 4ACy^{2} + 4ADx + 4AEy + 4AF = 0
(2Ax + By + D)^{2} - (By + D)^{2} + 4ACy^{2} + 4AEy + 4AF = 0
(2Ax + By + D)^{2} + (4AC - B^{2})y^{2} + (4AE - 2BD)y + (4AF - D^{2}) = 0
Let x_{1} = 2Ax + By + D
and g = gcd(4AC - B^{2}, 2AE - BD).
Multiplying by 4AC - B^{2} g :
4AC - B^{2} g x_{1}^{2} + (4AC - B^{2})^{2} g y^{2} + 2(4AC - B^{2}) (2AE - BD) g y + (4AC - B^{2}) (4AF - D^{2}) g = 0
4AC - B^{2} g x_{1}^{2} + g y_{1}^{2} + (4AC - B^{2}) (4AF - D^{2}) - (2AE - BD)^{2} g = 0
4AC - B^{2} g x_{1}^{2} + g y_{1}^{2} + 4A(4ACF - AE^{2} - B^{2}F + BDE - CD^{2}) g = 0
where:
y_{1} = 4AC - B^{2} g y + 2AE - BD g
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)^{2} + B(Px + Qy + K) (Rx + Sy + L) + C(Rx + Sy + L)^{2} + D(Px + Qy + K) + E(Rx + Sy + L) + F = 0
(AP^{2} + BPR + CR^{2})x^{2} + (2APQ + B(PS+QR) + 2CRS)xy + (AQ^{2} + BQS + CS^{2})y^{2} + (2AKP + B(KR+LP) + 2CLR + DP + ER)x + (2AKQ + B(KS+LQ) + 2CLS + DQ + ES)y + (AK^{2} + BKL + CL^{2} + DK + EL + F) = 0 (29)
Now we will investigate the values inside the parentheses.
AP^{2} + BPR + CR^{2} = Ar^{2} + BrAs + CA^{2}s^{2} = A(r^{2} + Brs + ACs^{2})
From equation (28) we obtain:
AP^{2} + BPR + CR^{2} = A (30)
2APQ + B(PS+QR) + 2CRS = 2Ar(-Cs) + B[r(r+Bs)+(-Cs)As] + 2CAs(r+Bs) = -2ACrs + B(r^{2}+Bs-ACs^{2}) + 2ACrs + 2ABCs^{2} = B(r^{2}+Bs+ACs^{2})
From equation (28) we obtain:
2APQ + B(PS+QR) + 2CRS = B (31)
AQ^{2} + BQS + CS^{2} = AC^{2}s^{2} + B(-Cs)(r+Bs) + C(r+Bs)^{2} = AC^{2}s^{2} - BCrs - B^{2}Cs^{2} + Cr^{2} + 2BCrs + B^{2}Cs^{2} = AC^{2} + BCrs + Cr^{2} = C(r^{2} + Brs + ACs^{2})
From equation (28) we obtain:
AQ^{2} + BQS + CS^{2} = C (32)
This means that 2AKP + B(KR+LP) + 2CLR + DP + ER = D and 2AKQ + B(KS+LQ) + 2CLS + DQ + ES = E.
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:
K = D[BQ - 2C(PS-QR-S)] + E[B(PS-RQ-P) - 2CR] 4AC (PS - QR) + B^{2} (QR - PS)
L = D[B(PS-RQ-S) - 2AQ] + E[BR - 2A(PS-RQ-P)] 4AC (PS - QR) + B^{2} (QR - PS)
Since PS - QR = r(r+Bs) - (-Cs)As = r^{2} + Brs + ACs^{2} = 1, these equations can be simplified to:
K =
D[BQ - 2C(1-S)] + E[B(1-P) - 2CR]
4AC - B^{2}
L =
D[B(1-S) - 2AQ] + E[BR - 2A(1-P)]
4AC - B^{2}
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^{2} + BKL + CL^{2} + DK + EL = 0 (33).
The expansion is very complicated and will not be reproduced here, but fortunately it is a multiple of 4AC-B^{2}, so it cancels the square in the denominator, since it is (4AC-B^{2})^{2}.
This means that Z(4AC-B^{2}) is an integer number and it is equal to:
AD^{2}Q^{2} - 2ADEPQ + AE^{2}P^{2} - AE^{2} + BD^{2}QS - BDEPS - BDEQR + BDE + BE^{2}PR + CD^{2}S^{2} - CD^{2} - 2CDERS + CE^{2}R^{2}
Reordering terms:
AD^{2}Q^{2} + BD^{2}QS + CD^{2}S^{2} - CD^{2} - 2ADEPQ - BDEPS - BDEQR - 2CDERS + BDE + AE^{2}P^{2} + BE^{2}PR + CE^{2}R^{2} - AE^{2}
D^{2}(AQ^{2} + BQS + CS^{2}) - CD^{2} - DE(2APQ + BPS + BQR + 2CRS) + BDE + E^{2}(AP^{2} + BPR + CR^{2}) - AE^{2}
From (30), (31) and (32):
Z(4AC-B^{2}) = CD^{2} - CD^{2} - BDE + BDE + AE^{2} - AE^{2} = 0
This means that Z = 0, so (33) holds, then (29) holds too.
Let K = K_{D}D + K_{E}E 4AC - B^{2} and L = L_{D}D + L_{E}E 4AC - B^{2} (34)
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^{2}s + 2ACs
L_{D} - K_{E} = (4AC - B^{2})s (37)
So:
K =
CD(P+S-2) + E(B-Br-2ACs)
4AC - B^{2}
L =
D(B-Br-2ACs) + AE(P+S-2)
4AC - B^{2}
+ Ds
Generally the numerators will not be multiple of 4AC - B^{2}, 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_{D}L_{E} - K_{E}L_{D} = 4ACr^{2} + 4ABCrs + 4A^{2}C^{2}s^{2} - B^{2}r^{2} - B^{3}rs - AB^{2}Cs^{2} - 4ABCs - B^{3}s + 4AC - B^{2} - 8ACr + 2B^{2}r =
= (4AC - B^{2}) (r^{2} + Brs + ACs^{2}) - (4AC - B^{2})Bs + (4AC - B^{2}) - (4AC - B^{2})2r =
= (4AC - B^{2}) (2 - 2r - Bs)
The equal signs shown below mean congruence mod 4AC - B^{2}.
K_{D}L_{E} - K_{E}L_{D} = 0 => K_{D}/K_{E} = L_{D}/L_{E} (38)
Since K and L must be integers they should be (from (34)):
K_{D}D + K_{E}E = 0 => E = (-K_{D}/K_{E})D (39)
L_{D}D + L_{E}E = 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)^{2} + B(-r)(-s) + AC(-s)^{2} = r^{2} + Brs + ACs^{2} = 1.
If no solutions were found (as in example 7), we should use the next pair of solutions (r_{1}, s_{1}) of r^{2} + Brs + ACs^{2} = 1 because there will always be solutions as shown below.
First we should find r_{1} and s_{1} from r and s. To do that we use the formulas (24) - (28).
r_{1} = r r + (-ACs)s = r^{2} - ACs^{2}
s_{1} = s r + (r + Bs)s = 2rs + Bs^{2}
Now the values of r and s should be replaced by r_{1} and s_{1}.
From (24): P_{1} = r_{1} = r^{2} - ACs^{2}
From (25): Q_{1} = -Cs_{1} = -C(2rs + Bs^{2})
From (26): R_{1} = As_{1} = A(2rs + Bs^{2})
From (27): S_{1} = r_{1} + Bs_{1} = r^{2} + 2Brs + (B^{2} - AC)s^{2}
From (35):
K_{1D} = C(-2 + 2r_{1} + Bs_{1})
K_{1D} = C[-2 + 2(r^{2} - ACs^{2}) + B(2rs + Bs^{2})]
K_{1D} = C[-2 + 2(r^{2} + Brs + ACs^{2}) - 4ACs^{2} + B^{2}s^{2}]
K_{1D} = C[-2 + 2 + (B^{2} - 4AC)s^{2}]
K_{1D} = (B^{2} - 4AC)Cs^{2}
From (36):
K_{1E} = B - Br_{1} - 2ACs_{1}
K_{1E} = B - Br^{2} + ABCr^{2} - 4ACrs - 2ABCr^{2}
K_{1E} = B - B(r^{2} + ACs^{2}) - 4ACrs
K_{1E} = B - B(r^{2} + ACs^{2} + Brs - Brs) - 4ACrs
K_{1E} = B - B(1 - Brs) - 4ACrs
K_{1E} = (B^{2} - 4AC)rs
From (37):
L_{1D} - K_{1E} = (4AC - B^{2})s_{1}
L_{1D} = (B^{2} - 4AC) (rs - 2rs - Bs^{2})
L_{1D} = (B^{2} - 4AC) (-rs - Bs^{2})
Therefore:
K_{1} = K_{1D}D + K_{1E}E 4AC - B^{2} = -CDs^{2} - Ers
L_{1} = L_{1D}D + L_{1E}E 4AC - B^{2} = Ds(r + Bs) - AEs^{2}
So, finally:
X_{n+1} = (r^{2} - ACs^{2})X_{n} - Cs(2r+Bs)Y_{n} - CDs^{2} - Ers (40)
Y_{n+1} = As(2r+Bs)X_{n} + [r^{2} + 2Brs + (B^{2}-AC)s^{2}]Y_{n} + Ds(r+Bs) - AEs^{2} (41)
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^{2} + 13xy + 5y^{2} + Dx + Ey + F = 0
The first solution of r^{2} + Brs + ACs^{2} = r^{2} + 13 rs + 15 s^{2} = 1 using the continued fraction method is r = -8351 and s = 6525.
P = r = -8351
Q = -Cs = -32625
R = As = 19575
S = r + Bs = 76474
K = CD(P+S-2) + E(B-Br-2ACs) 4AC-B^{2} = -340605 109 D + 87174 109 E
L = D(B-Br-2ACs) + AE(P+S-2) 4AC-B^{2} + Ds = 798399 109 D - 204363 109 E
The numerator of K (or L) is not a multiple of the denominator (4AC - B^{2} = -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
K = CD(P+S-2) + E(B-Br-2ACs) 4AC-B^{2} = 3125 D - 800 E
L = D(B-Br-2ACs) + AE(P+S-2) 4AC-B^{2} + Ds = -7325 D + 1875 E
So, the recursive relation between solutions is:
X_{n+1} = 8351 X_{n} - 32625 Y_{n} + (3125 D - 800 E)
Y_{n+1} = -19575 X_{n} - 76474 Y_{n} + (-7325 D + 1875 E)
Check: Knowing that x = 2, y = 3 is a solution of 3x^{2} + 13xy + 5y^{2} - 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_{0} = 2 and Y_{0} = 3, we find X_{1} = 85802 and Y_{1} = -201122.
and replacing X_{1} = 85802 and Y_{1} = -201122, we find X_{2} = -5845 101523 and Y_{2} = 13701 097128.
Replacing these values in the original equation we can check that these values are correct.
Example 7: 3x^{2} + 14xy + 6y^{2} + Dx + Ey + F = 0
The first solution of r^{2} + Brs + ACs^{2} = r^{2} + 14 rs + 18 s^{2} = 1 using the continued fraction method is r = -391 and s = 273.
P = r = -391
Q = -Cs = -1638
R = As = 819
S = r + Bs = 3431
K = CD(P+S-2) + E(B-Br-2ACs) 4AC-B^{2} = -147 D + 35 E
L = D(B-Br-2ACs) + AE(P+S-2) 4AC-B^{2} + Ds = 308 D - 147 2 E
The numerator of L is not a multiple of the denominator (4AC - B^{2} = -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
K = CD(P+S-2) + E(B-Br-2ACs) 4AC-B^{2} = -4563 31 D - 1092 31 E
L = D(B-Br-2ACs) + AE(P+S-2) 4AC-B^{2} + Ds = 4563 62 D - 9555 31 E
The numerator of K (or L) is not a multiple of the denominator (4AC - B^{2} = -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_{1} = r^{2} - ACs^{2} = -1188641
Q_{1} = -Cs(2r+Bs) = -4979520
R_{1} = As(2r+Bs) = 2489760
S_{1} = r^{2} + 2Brs + (B^{2}-AC)s^{2} = 10430239
K_{1} = -CDs^{2} - Ers = -106743 D + 447174 E
L_{1} = Ds(r+Bs) - AEs^{2} = 936663 D - 223587 E
So, the recursive relation between solutions is:
X_{n+1} = -1188641 X_{n} - 4979520 Y_{n} + (106743 D - 447174 E)
Y_{n+1} = 2489760 X_{n} + 10430239 Y_{n} + (936663 D - 223587 E)
Check: Knowing that x = 4, y = 7 is a solution of 3x^{2} + 14xy + 6y^{2} - 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_{0} = 4 and Y_{0} = 7, we find X_{1} = -34 464335 and Y_{1} = 72 189943.
and replacing X_{1} = -34 464335 and Y_{1} = 72 189943, we find X_{2} = -318 505538 201756 and Y_{2} = 667 150425 396007.
Replacing these values in the original equation we can check that these values are correct.
I've written a program that use these methods:
Follow the link to run a Java program compatible with Internet Explorer and Firefox.
The program runs in two modes: solution only and step-by-step. In the last mode, the program explains how the results are found.
Form to send me your comments.
Last modification: May 2nd, 2016.