Resource: Solving Diophantine Equation
Sources: https://www.alpertron.com.ar/METHODS.HTM
Solving General Bivariate Quadratic Diophantine Equation
The general bivariate quadratic Diophantine equation may be classified into several cases according to the values of A, B and C. These cases can be named accordingly to the figure represented by the equation in the coordinate plane xy, namely, a line, an ellipse, a parabola, and a hyperbola (or two lines). The set of solutions (x,y) can then be represented by isolated points in the coordinate plane xy.
Linear Case, A=B=C=0
If A=B=C=0. then the equation becomes Dx+Ey+F=0, a linear case.
- If D=E=0, then the equation can be simplified as F=0. In other words, there will be solutions only if F=0, and x and y can be any value.
- If D=0 and E≠0, then the equation can be simplified as Ey+F=0⇒y=-F/E. In other words, there will be solutions only if E divides F with y=-F/E, and x can be any value.
- If D≠0 and E=0, then the equation can be simplified as Dx+F=0⇒x=-F/D. In other words, there will be solutions only if D divides F with x=-F/D, and y can be any value.
- If D≠0, E≠0, and g=gcd(D, E)>1, then g divides both D and E, and (Dx+Ey)/g=-F/g. In other words, expression Dx+Ey will also be divided by g for any value of x and y, therefore there will has no solution if F is not a multiple of g.
- If D≠0, E≠0, and g=gcd(D, E)=1, then the equation can be rearragned as Dx+Ey=-F such that the Extended Euclid's Algorithm, uu'+vv'=±gcd(u, v) can be applied.
By letting u=D, v=E, then Du'+Ev'=±gcd(D,E)=±1⇒D(±Fu')+E(±Fv')=-F
Let t be any integer, the equation becomes D(±Fu')+DEt+E(±Fv')-DEt=-F⇒D(Et±Fu')D+E(-Dt±Fv')=-F.
Therefore, the general solution set of x,y is {x=Et±Fu', y=-Dt±Fv', where t=any integer}
For example, 30x+52y+8=0
Since gcd(D, E) = gcd(30, 52) = 2 and 2 divides 8, there will has solutions. Imply 15x+26y+4=0
By Extended Euclid's Algorithm,
- Step 0: 1 * 15 + 0 * 26 = 15
- Step 2: 0 * 15 + 1 * 26 = 26
- Step 3: 1 * 15 + 0 * 26 = 15
- Step 4: 2 * 15 + (-1) * 26 = 4
- Step 4: 8 * 15 + (-4) * 26 = 16
- Step 5: 7 * 15 + (-4) * 26 = 1
Multiplying the last equation by -F = -8, then (-56) * 15 + 32 * 26 = -8
Adding and subtracting DEt = 15 * 26 t, then (-56+26t) * 15 + (32-15t) * 26 = -8
The set of solution is {x=56+26t; y=32-15t; where t is any integer value}
Simple Hyperbolic Case, A=C=0 and B≠0
If A=C=0 and B≠0, then the equation becomes Bxy + Dx + Ey + F = 0, a simple hyperbolic case. Imply
Bxy + Dx + Ey + F = 0
⇒Bxy + Dx + Ey = -F
⇒B²xy + BDx + BEy = -BF
⇒B²xy + BDx + BEy + DE = DE - BF
⇒(Bx + E)(By + D) = DE - BF
There are two cases. If DE - BF = 0 then the figure is two lines parallel to x and y axes respectively and if DE - BF ≠ 0 then the figure is a hyperbola with asymptotes parallel to x and y axes.
- If DE - BF = 0, then either (Bx + E) = 0 or (By + D) = 0. Since B cannot equal to zero, B≠0, the equation can have solutions only if B divides D or E accordingly.
Only if B divides E, then the set of solution is {x=-E/B, y=any integer}
Only if B divides D, then the set of solution is {x=any integer, y=-D/B}
- If DE - BF ≠ 0, then DE - BF is the product of (Bx + E) and (By + D). Therefore, the values of x and y can be found by finding all divisors of DE - BF.
Let d₁, d₂, …, dᵢ, …, dₙ be the set of divisors of DE - BF
For each dᵢ, Bx + E= dᵢ ⇒ By + D=(DE - BF) / dᵢ
Therefore, Bx=dᵢ - E and By=(DE - BF) / dᵢ - D
The set of solution is {x=(dᵢ - E)/B, y=((DE - BF) / dᵢ - D )/B}
For example, xy+3x+2y+1=0
The equation can be transformed to x + 2)(y + 3) = 3*2 - 1*1
Since DE - BF = 3*2 - 1*1 = 5>0, the divisors of DE - BF are ±1, ±5.
Therefore, for each dᵢ
- d₁=1: x=1 - 2=-1, y=(3*2 - 1) / 1 - 3 =2⇒The set of solution is {-1,2}
- d₂=-1: x=-1 - 2=-3, y=(3*2 - 1) / (-1) - 3 =-8⇒The set of solution is {-3,-8}
- d₃=5: x=5 - 2=3, y=(3*2 - 1) / 5 - 3 =-2⇒The set of solution is {3,-2}
- d₄=-5: x=-5 - 2=-7, y=(3*2 - 1) / (-5) - 3 =-4⇒The set of solution is {-7,-4}
Elliptical Case, B² - 4AC < 0
If B2 - 4AC < 0, then the figure of the equation Ax² + Bxy + Cy² + Dx + Ey + F = 0 is an ellipse. An ellipse is a closed figure, the number of solutions is therefore finite. Imply
Ax² + Bxy + Cy² + Dx + Ey + F = 0
⇒Cy² + (Bx + E)y + (Ax² + Dx + F) = 0
⇒y=(-(Bx + E)±√((Bx + E)²-4C(Ax² + Dx + F)))/2C
For an ellipse, there are two extremes at the left and right sides of the ellipse. The values of two extremes can be determined by setting the square root of an equation to zero. Imply
(Bx + E)²-4C(Ax² + Dx + F)=0
⇒(B²- 4AC)x² + 2(BE - 2CD)x + (E² - 4CF) = 0
In other words, the values of x can only be between the roots of the equation, (B²- 4AC)x² + 2(BE - 2CD)x + (E² - 4CF) = 0. That is
x=(-2(BE - 2CD)±√((2(BE - 2CD))²-4(B²- 4AC)(E² - 4CF)))/2(B²- 4AC)
Therefore there will has no solution if the roots are not real. The integer x values of the solution can only be all interger values of x between the roots. The integer y values of the solution can be obtained by subsituting the corresponding integer x value accordingly.
For example, x² + xy + y² + x + y - 5 = 0
Since B² - 4AC = 1²-4(1)(1)=-3 < 0, the equation is elliptical. Imply x is between
x=(-2(BE - 2CD)±√((2(BE - 2CD))²-4(B²- 4AC)(E² - 4CF)))/2(B²- 4AC)=(-2(1 - 2)±√((2(1 - 2))²-4(1²- 4)(1² - 4(1)(-5)))/2(1²- 4)=(1±8)/-3
⇒-3≤x≤7/3
⇒x={-3,-2,-1,1,2}
Since y=(-(Bx + E)±√((Bx + E)²-4C(Ax² + Dx + F)))/2C=(-(x + 1)±√((x + 1)²-4(x² + x + 5)))/2
⇒x=-3; y=1
⇒x=1; y={-3,1}
Parabolic Case, B² - 4AC = 0
If B² - 4AC = 0, then the figure of the equation Ax² + Bxy + Cy² + Dx + Ey + F = 0 is a parabola.
Since B² - 4AC = 0, imply B² = 4AC⇒ (B/2)² = AC. Therefore the product of A and C is a perfect square.
Let g=gcd(A,C), b=B/g, and c=C/g, ⇒(bg/2)² = agcg⇒(b/2)² = ac. Therefore both a and c are perfect squares.
Subsitute into equation, imply
Ax² + Bxy + Cy² + Dx + Ey + F = 0
⇒g(ax² + bxy + cy²) + Dx + Ey + F = 0⇒g(ax² + 2√a√cxy + cy²) + Dx + Ey + F = 0 ⇒g(√ax +√cy )² + Dx + Ey + F = 0
for √c, the sign of B/A is taken.
Multiplying √a, and Adding and subtracting √cDy, imply
√ag(√ax +√cy )² + √aDx + √cDy - √cDy + √aEy + √aF = 0
⇒√ag(√ax +√cy )² + D(√ax + √cy) - (√cD - √aE)y + √aF = 0
Let u=√ax +√cy, imply
√agu² + Du - (√cD - √aE)y + √aF = 0
⇒√agu² + Du + √aF = (√cD - √aE)y
There are two cases. If √cD - √aE = 0 then the figure is two parallel lines and if √cD - √aE ≠ 0 then the figure is a parabola.
- If √cD - √aE = 0 then √agu² + Du + √aF = 0⇒u=(-D±√(D² -4√ag√aF))/2√ag
Since x and y are integer and u=√ax +√cy, u should also be integer.
Let u₁ and u₂ be the roots, from u=√ax +√cy, imply √ax +√cy - u₁ =0 and √ax +√cy-u₂=0.
With two equations and two unknowns, the solution set x,y can then be found by solving methods for the linear equation.
- if √cD - √aE ≠ 0 then √agu² + Du + √aF=(√cD - √aE)y. √cD - √aE divides √agu² + Du + √aF because y is an integer value. Imply
√agu² + Du + √aF ≡ 0 (mod √cD - √aE)
Let u₁, u₂, …, uᵢ, …, uₙ be the set of values in the range 0 ≤uᵢ<|√cD - √aE| for which u is an integer value while the equation holds.
In other words, the solution set for each uᵢ is u=uᵢ+ (√cD - √aE )t where t is any integer number.
Subsitute u
(√cD - √aE)y=√ag(uᵢ+ (√cD - √aE )t)² + D(uᵢ+ (√cD - √aE )t) + √aF
⇒(√cD - √aE)y=2√aguᵢ (√cD - √aE )t+√ag((√cD - √aE )t)²+ (√cD - √aE )Dt +√aguᵢ²+ Duᵢ+√aF
⇒y=√ag(√cD - √aE )t² +(D +2√aguᵢ) t + (√aguᵢ²+ Duᵢ+√aF)/(√cD - √aE)
Similarly
u=√ax +√cy = uᵢ+ (√cD - √aE )t ⇒ √ax = uᵢ+ (√cD - √aE )t -√cy
⇒ √ax = -√a√cg(√cD - √aE )t² -(√aE + 2√a√cguᵢ) t + uᵢ -√c (√aguᵢ²+ Duᵢ+√aF)/(√cD - √aE)
⇒ x = -√cg(√cD - √aE )t² -(E + 2√cguᵢ) t - ( √cguᵢ²+ Euᵢ +√cF)/(√cD - √aE)
For example, x² + 2xy + y² + 2x + y - 7 = 0
Since B² - 4AC = 2²-4(1)(1)= 0, the equation is parabolic.
Variables:
- g = gcd(A, C) = gcd(1, 1) =1
- a=A/g=1/1=1
- c=C/g=1/1=1
- √a=√1=1
- √c=√1=1 (B/A>0, sign=positive)
- √cD - √aE =1(2) -1(1)=1⇒ second case
- √agu² + Du + √aF=u² + 2u -7
- u: 0 ≤uᵢ<|√cD - √aE| ⇒ 0 ≤uᵢ< 1
- u:√agu² + Du + √aF ≡ 0 (mod √cD - √aE) ⇒ u² + 2u -7 ≡ 0 (mod 1)⇒u={0}
- For u₁=0,
x = -t² - t - 7
y = t² +2 t + 7
Hyperbolic Case, B² - 4AC > 0
If B² - 4AC > 0, then the figure of the equation Ax² + Bxy + Cy² + Dx + Ey + F = 0 is a hyperbola.
Homogeneous Equation
Ax² + Bxy + Cy² + F = 0
- If F=0, then Ax² + Bxy + Cy² = 0, and x=0 and y=0 is the trivial solution.
Ax² + Bxy + Cy² = -F
Multiplying by 4A, and Adding and subtracting g((2AE - BD)/g)²
⇒4A²x² + 4ABxy + B²y² - B²y² + 4ACy² = -4AF
⇒(2Ax + By)²- (B² - 4AC)y² = -4AF
⇒(2Ax + By+ √(B² - 4AC)y)(2Ax + By- √(B² - 4AC)y) = -4AF
⇒(2Ax + (B+ √(B² - 4AC))y)(2Ax + (B- √(B² - 4AC))y) = -4AF
Since -4AF=0, methods used in linear equation can be used to find all solutions, however the equation can have integer solutions only if B² - 4AC is a perfect square.
- If F≠ 0 and B² - 4AC=k² is a perfect square for some integer k, then right hand side of equation (2Ax + (B+ √(B² - 4AC))y)(2Ax + (B- √(B² - 4AC))y) = -4AF must be factors of -4AF.
Let u₁, u₂, …, uᵢ, …, uₙ be the set of positive and negative divisors of -4AF
⇒(2Ax + (B+ √(B² - 4AC))y) = 2Ax + (B+ k)y = uᵢ and (2Ax + (B- √(B² - 4AC))y) = 2Ax + (B- k)y = -4AF/uᵢ
⇒y=(uᵢ+4AF/uᵢ )/(2k); and x=(uᵢ- (B+ k)y) for x and y of integer values only
- If F≠ 0, B² - 4AC is not a perfect square, and gcd(A,B,C)=g, then there has integer solution only if g divides F.
- If 4F<B² - 4AC, then 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.
- If 4F≥B² - 4AC, then Ax² + Bxy + Cy² = -F can be rewritten.
Let G = gcd(x,y), x = Gu and y = Gv
⇒AG²u² + BG²uv + CG²v² = -F⇒Au² + Buv + Cv² = -F/G²
therefore there has integer solution only if G² divides F.
Assume gcd(x,y)=1, ⇒Ax² + Bxy + Cy² = F
Let x=sy-Fz
⇒A(sy-Fz)² + B(sy-Fz)y + Cy² = -F
⇒As²y² -2AFsyz +AF²z² + Bsy²-BFzy + Cy² = -F
⇒(As² + Bs+ C)y²+(-B -2As)Fyz +AF²z² = -F
⇒-(As² + Bs+ C)y²/F+(B + 2As)yz -AFz² = 1
Find 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 x=sy-Fz. If no solutions are found amongst the convergents, there will be no solutions to the equation.
If the equation has solutions, there should be a solution to the congruence, except when gcd(A,B,F) > 1. In this case, if gcd(B,C,F) = 1, then
Let y=sx-Fz
⇒Ax² + Bx(sx - Fz) + C(sx - Fz)² = -F
⇒Ax²+ Bsx² - BFxz + Cs²x² - 2CFsxz + CF²z² = -F
⇒(Cs² + Bs + A) x² + (-2Cs - B)Fxz + CF²z² = - F
⇒(Cs² + Bs + A) x²/F + (-2Cs - B)xz + CFz² = - 1
Find 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 y=sx-Fz. If no solutions are found amongst the convergents, there will be no solutions to the equation.
If the equation has solutions, there should be a solution to the congruence, except when both gcd(A,B,F) >1. In this case, if gcd(B,C,F) > 1, then
Let i, j, m and n be four integers such that in - jm = 1
Let x = iX + jY and y = mX + nY, imply X = nx - jy and Y = -mx + iy
⇒Ax² + Bxy + Cy² = -F
⇒A(iX+jY)² + B(iX+jY)(mX+nY) + C(mX+nY)² = -F
⇒aX² + bXY + cY² = -F ; where a = Ai² + Bim + Cm² , b = 2Aij + Bin + Bjm + 2Cmn , c = Aj² + Bjn + Cn²
Find the values of i and m such that a=Ai² + Bim + Cm² is relatively prime to F
Since gcd(C, F) > 1, imply gcd(Ai2 + Bim + Cm2, C) = 1, so gcd(i, C) = 1 and gcd(Ai+Bm, C) = 1.
Since gcd(A, F) > 1, imply gcd(Ai2 + Bim + Cm2, A) = 1, so gcd(m, A) = 1 and gcd(Bi+Cm, A) = 1.
Since in - jm = 1, gcd(i,m)=1
If F≡0 (mod p) where p is a prime, then i and m from a, b and c are as below
| 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 |
The values of i and m can be generated from their values modulo different primes, but the values of i and m can also be found by searching. That it
for i=0 to |F|-1: for m=0 to i+1: if gcd(i, m) = 1 : k = Ai2 + Bim + Cm2 : if gcd(k, F) = 1, end. : end if : next m : next i
With the values of i and m just found, the values of j and n can be determined from in - jm = 1 using the methods for the linear equation. Then the values of a, b and c can be determined from the corresponding equations accordingly. The set of solutions (X,Y) can then be found. And the set of solutions (x,y) can also be determined from the corresponding equations accordingly.
For example, Find some solutions for 18 x² + 41 xy + 19 y² - 24 = 0
First 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, imply
18 x² + 41 xy + 19 y² - 24 = 0
Let x = sy - fz, imply
[-(as² + bs + c)/f]y² + (2sa + b)yz - afz²
= 1.
So 18 s² + 41 s + 19 should be multiple of 24.
imply s = 19.
Let s=19, imply
304 y2 + 725 yz + 432 z2 = 1
Determine the continued fraction expansion of the roots of 304 t2 + 725 t + 432 = 0, that is,
-
considering the continued fraction of the root,
t =
(√313 - 725)/608, imply
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 Y0 and Z0 are found (the third column are the values for P(y, z) = 304 y2 + 725 yz + 432 z2):
Terms of the continued fraction and convergents
| cn |
yn |
zn |
P(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 yn = cn yn-1 + yn-2
and zn = cn zn-1 + zn-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 all solutions of the homogeneous equation can be found.
Y0 = -7987 322433 784501 16
Z0 = 6865 878383 744439 16
Since X0 = 19 Y0 + 24 Z0
X0 = 13021 954967 961017 17
Y0 = -7987 322433 784501 16
Since the equation Ax2 + Bxy + Cy2 + F = 0 does not change when x is replaced by
-x and y is replaced by -y simultaneously. Another solution is:
X0 = -13021 954967 961017 17
Y0 = 7987 322433 784501 16
-
Now considering the continued fraction of the other root: t = - (√313 + 725) /608, imply
The continued fraction 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 Y0 and Z0 are found (the third column are the values for P(y, z) = 304 y2 + 725 yz + 432 z2):
Terms of the continued fraction and convergents
| cn |
yn |
zn |
P(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.
Y0 = 11
Z0 = -9
Since X0 = 19 Y0 + 24 Z0:
X0 = -7
Y0 = 11
And similarly
X0 = 7
Y0 = -11
Since 2 * 2 is a divisor of the constant term (-24), the solutions should be 2 times the solutions of 18 u2 + 41 uv + 19 v2 - 6 = 0.
Determine the continued fraction expansion of the roots of 18 t2 + 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 U0 and V0 are found (the third column are the values for
P(u, v) = 18 u2 + 41 uv + 19 v2):
Terms of the continued fraction and convergents
| cn |
un |
vn |
P(un, vn) |
| |
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:
X0 = -202
Y0 = 312
X0 = 202
Y0 = -312
X0 = -10130
Y0 = 15646
X0 = 10130
Y0 = -15646
X0 = -14 247838 8
Y0 = 22 006088 8
X0 = 14 247838 8
Y0 = -22 006088 8
X0 = -9245 980567 328630 16
Y0 = 14280 613101 505146 17
X0 = 9245 980567 328630 16
Y0 = -14280 613101 505146 17
-
The other root of the equation 18 t2 + 41 t + 19 = 0 is t = -
(√313 + 41)/38
The 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 U0 and V0 are found (the third column are the values for
P(u, v) = 18 u2 + 41 uv + 19 v2):
Terms of the continued fraction and convergents
| cn |
un |
vn |
P(un, vn) |
| |
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:
X0 = 10
Y0 = -6
X0 = -10
Y0 = 6
X0 = 6582 595298 10
Y0 = -4037 589688 10
X0 = -6582 595298 10
Y0 = 4037 589688 10
X0 = 9 258415 606510 13
Y0 = -5 678867 025506 13
X0 = -9 258415 606510 13
Y0 = 5 678867 025506 13
X0 = 464 279223 068342 15
Y0 = -284 776584 090312 15
X0 = -464 279223 068342 15
Y0 = 284 776584 090312 15
Find recurrences among the solutions of the homogeneous equation
Once some solutions of the equation were found, other solutions of the family of infinite solutions of the homogeneous equation can also be determined.by Xₙ₊₁ = P Xₙ + Q Yₙ ; Yₙ₊₁ = R Xₙ + S Yₙ 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
⇒ M(p,q)/A=p² + (B/A)pq + (C/A)q² =M/A
Let D=B/A and E=C/A
⇒ M(p,q)/A=p² +Dpq + Eq² =M/A
⇒ M(p/q,1)/A=(p/q)² +D(p/q) + E =M/A
The roots of M(p/q,1)=A(p/q)² +B(p/q) + C = (p/q-J)(p/q-J')=0 are
J=(-B+√(B²-4AC))/2A ; J'=(-B-√(B²-4AC))/2A
⇒J²=-DJ-E
⇒J'²=-DJ'-E
⇒J+J'=-D
⇒JJ'=E
Similarly, the roots of N(p/q,1)=(p/q)² +B(p/q) + AC = (p/q-K)(p/q-K')=0 are
K=(-B+√(B²-4AC))/2 ; K'=(-B-√(B²-4AC))/2
⇒K=AJ and K'=AJ'
Therefore,
M(p, q)/A = (p - Jq)(p - J'q) = M ?
N(r, s) = (r - Ks)(r - K's) = N
Since K=AJ and K'=AJ'
⇒(p - Jq)(r - Ks) = (p - Jq)(r - AJs) = (pr - AJps - Jqr + AJ²qs)
Subsitute J²=-DJ-E
⇒(p - Jq)(r - Ks) = (pr - AJps - Jqr + A(DJ-E)qs) = (pr - AEqs) - (Aps + qr + AEqs)J = (pr - Cqs) - (Aps + qr + Bqs)J
Similarly, since K=AJ and K'=AJ'
(p - J'q)(r - K's) = (p - J'q)(r - AJ's) = (pr - AJ'ps - J'qr + AJ'²qs)
Subsitute J'²=-DJ'-E
⇒(p - J'q)(r - K's) = pr - AJ'ps - J'qr + A(-DJ' - E)qs = (pr - AEqs) - (Aps + qr + AEqs)J' = (pr - Cqs) - (Aps + qr + Bqs)J'
Let X = pr - Cqs and Y = Aps + qr + Bqs
Multiplying (M(p, q)/A) N(r, s)
⇒(M(p, q)/A) N(r, s) =(p - Jq)(r - Ks) (p - J'q)(r - K's) =(X - YJ) (X - YJ') = X² - (J + J')XY + JJ'Y²
Subsitute J+J'=-D and JJ'=E
⇒(M(p, q)/A) N(r, s) = X² + DXY + EY²
Multiplying product of M(p, q)/A and N(r, s) by A
⇒AX² + BXY + CY² = MN
Let M=-F and N=1 then X and Y are also solutions of the equation.
Let r and s be a solution to N(r,s) = r² + Brs + ACs² = 1.
Therefore Xₙ = p, Yₙ = q, Xₙ₊₁ = X and Yₙ₊₁ = Y since the last two pairs of numbers are solutions to the original equation.
From X = pr - Cqs and Y = Aps + qr + Bqs
Xₙ₊₁ = rXₙ - CsYₙ₊₁
Yₙ₊₁ = AsXₙ + rYₙ₊₁ + BsYₙ₊₁
Imply
Xₙ₊₁ = P Xₙ + Q Yₙ
Yₙ₊₁ = R Xₙ + S Yₙ
P=r, Q=-Cs, R=As, and S=r+Bs where r² + Brs + ACs² = 1
General Quadratic Equation
Ax² + Bxy + Cy² + Dx + Ey + F = 0
Multiplying by 4A
⇒ 4A²x² + 4ABxy + 4ACy² + 4ADx + 4AEy + 4AF = 0
⇒ (2Ax + By + D)² - B²y² - D² - 2BDy + 4ACy² + 4AEy + 4AF = 0
⇒ (2Ax + By + D)² + (4AC - B²)y² + 2(2AE - BD)y + (4AF - D²) = 0
Let x₁ = 2Ax + By + D and g=gcd(4AC - B²,2AE - BD)
Multiplying by (4AC - B²)/g and Adding and subtracting g((2AE - BD)/g)²
⇒ ((4AC - B²)/g)x₁² + ((4AC - B²)²/g)y² + (2 (4AC - B²)(2AE - BD)/g)y + g((2AE - BD)/g)² - g((2AE - BD)/g)² + (4AC - B²)(4AF - D²)/g = 0
⇒ ((4AC - B²)/g)x₁² + g((((4AC - B²)/g)y)² + (2 (4AC - B²)(2AE - BD)/g²)y + ((2AE - BD)/g)²) - g((2AE - BD)/g)² + (4AC - B²)(4AF - D²)/g = 0
⇒ ((4AC - B²)/g)x₁² + g(((4AC - B²)/g)y + (2AE - BD)/g)² + (4AC - B²)(4AF - D²) - (2AE - BD)² )/g = 0
⇒ ((4AC - B²)/g)x₁² + g(((4AC - B²)/g)y + (2AE - BD)/g)² + 4A(4ACF - AE² - B²F + BDE - CD² ) /g = 0
Let y₁ = ((4AC - B²)/g)y+(2AE - BD)/g
⇒ ((4AC - B²)/g)x₁² + gy₁² + 4A(4ACF - AE² - B²F + BDE - CD² ) /g = 0
Find recurrences among the solutions of the general quadratic equation
Once some solutions of the equation were found, other solutions of the family of infinite solutions of the general quadratic equation can also be determined.by Xₙ₊₁ = P Xₙ + Q Yₙ + K; Yₙ₊₁ = R Xₙ + S Yₙ +L where P, Q, R, S, K and L should be determined.
Subsitute x by Px + Qy + K and y by Rx + Sy + L in general quadratic equation Ax² + Bxy + Cy² + Dx + Ey + F = 0
⇒ 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² + (2AKP + B(KR+LP) + 2CLR + DP + ER)x + (2AKQ + B(KS+LQ) + 2CLS + DQ + ES)y + (AK² + BKL + CL² + DK + EL + F) = 0
As assume P=r and R=As
⇒ AP² + BPR + CR² = Ar² + BrAs + CA²s² = A(r² + Brs + ACs²)
Since r² + Brs + ACs² = 1
⇒ AP² + BPR + CR² = A
As assume P=r and S=r+Bs
⇒ 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²)
Since r² + Brs + ACs² = 1
⇒ 2APQ + B(PS+QR) + 2CRS = B
As assume Q=-Cs and S=r+Bs
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²)
Since r² + Brs + ACs² = 1
AQ² + BQS + CS² = C
Therefore the new x of the general quadratic equation Ax² + Bxy + Cy² + Dx + Ey + F = 0 can be rewritten as
⇒ Ax² + Bxy + Cy² + (2AKP + B(KR+LP) + 2CLR + DP + ER)x + (2AKQ + B(KS+LQ) + 2CLS + DQ + ES)y + (AK² + BKL + CL² + DK + EL + F) = 0
Imply
2AKP + B(KR+LP) + 2CLR + DP + ER = D
2AKQ + B(KS+LQ) + 2CLS + DQ + ES = E.
Or equivalent to
(2AP+BR)K + (BP+2CR)L = -D(P-1) - ER
(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) + B2 (QR - PS))
⇒ L = (D[B(PS-RQ-S) - 2AQ] + E[BR - 2A(PS-RQ-P)])/(4AC (PS - QR) + B2 (QR - PS))
Since PS - QR = r(r+Bs) - (-Cs)As = r² + Brs + ACs² = 1
⇒ K = (D[BQ - 2C(1-S)] + E[B(1-P) - 2CR])/(4AC - B2)
⇒ L = (D[B(1⇒ L = (D[B(1-S) - 2AQ] + E[BR - 2A(1-P)])/(4AC - B2)
The value (AK² + BKL + CL² + DK + EL + F) of the equation should therefore equals to F also
⇒ Z=AK² + BKL + CL² + DK + EL =0
The exapnasion is a multiple of 4AC-B²
⇒ Z(4AC-B²) = AD²Q² - 2ADEPQ + AE²P² - AE² + BD²QS - BDEPS - BDEQR + BDE + BE²PR + CD²S² - CD² - 2CDERS + CE²R²
⇒ Z(4AC-B²) = AD²Q² + BD²QS + CD²S² - CD² - 2ADEPQ - BDEPS - BDEQR - 2CDERS + BDE + AE²P² + BE²PR + CE²R² - AE²
⇒ Z(4AC-B²) =D² (AQ² + BQS + CS²) - CD² - DE(2APQ - BPS - BQR - 2CRS) + BDE + E²(AP² + BPR + CR²) - AE²
Since AP² + BPR + CR² = A, 2APQ + B(PS+QR) + 2CRS = B, and AQ² + BQS + CS² = C
⇒ Z(4AC-B²) =CD² - CD² - BDE + BDE + AE² - AE² = 0
⇒ Z = 0
⇒ Z= AK² + BKL + CL² + DK + EL =0 is true
⇒ (AP² + BPR + CR²)x² + (2APQ + B(PS+QR) + 2CRS)xy + (AQ² + BQS + CS²)y² + (2AKP + B(KR+LP) + 2CLR + DP + ER)x + (2AKQ + B(KS+LQ) + 2CLS + DQ + ES)y + (AK² + BKL + CL² + DK + EL + F) = 0 is true
Let K = (KDD + KEE)/(4AC - B²) and L = (LDD + LEE)/(4AC - B²)
⇒KD = BQ - 2C(1 - S)
⇒KD = B(-Cs) - 2C(1 - r - Bs)
⇒KD = -BCs - 2C + 2Cr + 2BCs
⇒KD = C(-2 + 2r + Bs)
⇒KD = C(P + S - 2)
⇒LE = BR - 2A(1 - P)
⇒LE = ABs - 2A + 2Ar
⇒LE = A(-2 + 2r + Bs)
⇒LE = A(P + S - 2)
⇒KE = B(1 - P) - 2CR
⇒KE = B(1 - r) - 2ACs
⇒KE = B - Br - 2ACs
⇒LD = B(1 - S) - 2AQ
⇒LD = B(1 - r - Bs) + 2ACs
⇒LD = B - Br - B²s + 2ACs
⇒LD - KE = (4AC - B²)s
Therefore
K = (CD(P+S-2) + E(B-Br-2ACs))/(4AC - B2)
L = (D(B-Br-2ACs) + AE(P+S-2))/(4AC - B2) + Ds
Since the numerators will not always be the multiple of (4AC - B2) , not all values of D and E can be used to find a recurrence.
In other words, only tor some values of D and E, there will be solutions.
By equations P=r, Q=-Cs, R=As, and S=r+Bs
⇒KDLE - KELD = 4ACr² + 4ABCrs + 4A²C²s² - B²r² - B³rs - AB²Cs² - 4ABCs - B³s + 4AC - B² - 8ACr + 2B²r
⇒KDLE - KELD = (4AC - B²) (r² + Brs + ACs²) - (4AC - B²)Bs + (4AC - B²) - (4AC - B²)2r
⇒KDLE - KELD = (4AC - B²) (2 - 2r - Bs)
⇒KDLE - KELD ≡ 0 ⇒ KDLE ≡ KELD (mod (4AC - B²))
Since K and L must be integers, From equations K = (KDD + KEE)/(4AC - B²) and L = (LDD + LEE)/(4AC - B²)
⇒KDD + KEE = 0 => E = (-KD/KE)D
⇒LDD + LEE = 0 => E = (-LD/LE)D
These equations are consistent because of equation KDLE ≡ KELD
In some cases a recurrence can be found by using the solutions -r and -s since (-r)² + B(-r)(-s) + AC(-s)² = r² + Brs + ACs² = 1
If no solutions were found, the next pair of solutions (r₁, s₁) of r² + Brs + ACs² = 1 should be used because there will always be recurrence solutions.
From equations
P=r, Q=-Cs, R=As, and S=r+Bs where r² + Brs + ACs² = 1
⇒r₁ = r r + (-ACs)s = r²- ACs²
⇒s₁ = s r + (r + Bs)s = 2rs + Bs²
Subsitute the values of r and s by r₁ and s₁.
⇒P=r⇒P₁ = r₁ = r² - ACs²
⇒Q=-Cs⇒Q₁=-Cs₁=-C(2rs + Bs²)
⇒R=As⇒R₁=As₁=A(2rs + Bs²)
⇒S=r+Bs ⇒S₁=r₁+Bs₁=r² + 2Brs + (B² - AC)s²
From KD = C(-2 + 2r + Bs)
⇒K₁D = C(-2 + 2r₁ + Bs₁)
⇒K₁D = C[-2 + 2(r² - ACs²) + B(2rs + Bs²)]
⇒K₁D = C[-2 + 2(r² + Brs + ACs²) - 4ACs² + B2s²]
⇒K₁D = C[-2 + 2 + (B² - 4AC)s²]
⇒K₁D = (B² - 4AC)Cs²
From KE = B - Br - 2ACs
⇒K₁E = B - Br₁ - 2ACs₁
⇒K₁E = B - Br²+ ABCr² - 4ACrs - 2ABCr²
⇒K₁E = B - B(r² + ACs²) - 4ACrs
⇒K₁E = B - B(r² + ACs² + Brs - Brs) - 4ACrs
⇒K₁E = B - B(1 - Brs) - 4ACrs
⇒K₁E = (B² - 4AC)rs
From LD - KE = (4AC - B²)s
⇒L₁D - K₁E = (4AC - B²)s1
⇒L₁D = (B² - 4AC) (rs - 2rs - Bs²)
⇒L₁D = (B² - 4AC) (-rs - Bs²)
Therefore,
K₁ = (K₁DD + K₁EE)/(4AC - B²) = -CDs² - Ers
L₁ = (L₁DD + L₁EE)/(4AC - B²) = Ds(r + Bs) - AEs²
Imply
Xₙ₊₁ = (r² - ACs²)Xₙ - Cs(2r+Bs)Yₙ - CDs² - Ers
Yₙ₊₁ = As(2r+Bs)Xₙ + [r² + 2Brs + (B²-AC)s²]Yₙ + Ds(r+Bs) - AEs²
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.
For example, 3x² + 13xy + 5y² + Dx + Ey + F = 0
The first solution of r² + Brs + ACs² = r² + 13 rs + 15 s² = 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²) = (-340605/109)D + (87174/109)E
L = (D(B-Br-2ACs) + AE(P+S-2))/(4AC-B²) + Ds = (798399/109)D - (204363/109)E
The numerator of K and L are 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 E = (-KD/KE)D
and E = (-LD/LE)D, that is when E ≡ 93 D (mod 109).
Using the solution r = 8351, s = -6525, imply
⇒ P = r = 8351
⇒ Q = -Cs = 32625
⇒ R = As = -19575
⇒ S = r + Bs = -76474
K = (CD(P+S-2) + E(B-Br-2ACs))/(4AC-B²) = 3125D - 800E
L = (D(B-Br-2ACs) + AE(P+S-2))/(4AC-B²) + Ds = -7325D + 1875E
So, the recursive relation between solutions is:
Xₙ₊₁ = 8351 Xₙ - 32625 Yₙ + (3125 D - 800 E)
Yₙ₊₁ = -19575 Xₙ - 76474 Yₙ + (-7325 D + 1875 E)
example: x = 2, y = 3 is a solution of 3x² + 13xy + 5y² - 11x - 7y - 92 = 0, find other two solutions.
Subsitute D = -11 and E = -7 into equations
Xₙ₊₁ = 8351 Xₙ - 32625 Yₙ + (3125 (-11) - 800 (-7)) = 8351 Xₙ - 32625 Yₙ - 28775
Yₙ₊₁ = -19575 Xₙ - 76474 Yₙ + (-7325 (-11) + 1875 (-7)) = -19575 Xₙ - 76474 Yₙ + 67450
So substitute x₀ = 2 and y₀ = 3, imply
X₁ = 8351 X₀ - 32625 Y₀ - 28775 = 8351 (2) - 32625 (3) - 28775 = 85802
Y₁ = -19575 X₀ - 76474 Y₀ + 67450 = -19575 (2) - 76474 (3) + 67450 = -201122
So substitute x₁ = 85802 and y₁ = -201122 imply
X₂ = 8351 X₁ - 32625 Y₁ - 28775 = 8351 (85802) - 32625 (-201122) - 28775 = -5845101523
Y₂ = -19575 X₁ - 76474 Y₁ + 67450 = -19575 (85802) - 76474 (-201122) + 67450 = 13701097128
Therefore f(x,y)=3x² + 13xy + 5y² - 11x - 7y - 92 =0
⇒f(2,3)=f(85802,-201122)=f(-5845101523,13701097128)=0
For another example, 3x2 + 14xy + 6y2 + Dx + Ey + F = 0
The first solution of r² + Brs + ACs² = r² + 14 rs + 18 s² = 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²) = -147D + 35E
L = (D(B-Br-2ACs) + AE(P+S-2))/(4AC-B²) + Ds = 308D - (147/2)E
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 case E = is even.
Using the solution r = 391, s = -273, imply
⇒ P = r = 391
⇒ Q = -Cs = 1638
⇒ R = As = -819
⇒ S = r + Bs = -3431
K = (CD(P+S-2) + E(B-Br-2ACs))/(4AC-B²) = (-4653/31)D - (1092/31)E
L = (D(B-Br-2ACs) + AE(P+S-2))/(4AC-B²) + Ds = (4563/62)D - (9555/31)E
The numerator of L and K are 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 E = (-KD/KE)D
and E = (-LD/LE)D.
By
Xₙ₊₁ = (r² - ACs²)Xₙ - Cs(2r+Bs)Yₙ - CDs² - Ers
Yₙ₊₁ = As(2r+Bs)Xₙ + [r² + 2Brs + (B²-AC)s²]Yₙ + Ds(r+Bs) - AEs²
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:
Xₙ₊₁ = -1188641 Xₙ - 4979520 Yₙ + (106743 D - 447174 E)
Yₙ₊₁ = 2489760 Xₙ + 10430239 Yₙ + (936663 D - 223587 E)
example: x = 4, y = 7 is a solution of 3x² + 14xy + 6y² - 17x - 23y - 505 = 0, find other two solutions.
Subsitute D = -17 and E = -23 into equations
Xₙ₊₁ = -1188641 Xₙ - 4979520 Yₙ + (106743 (-17) - 447174 (-23)) = -1188641 Xₙ - 4979520 Yₙ + 5146869
Yₙ₊₁ = 2489760 Xₙ + 10430239 Yₙ + (936663 (-17) - 223587 (-23)) = 2489760 Xₙ + 10430239 Yₙ - 10780770
So substitute x₀ = 4 and y₀ = 7, imply
X₁ = -1188641 X₀ - 4979520 Y₀ + 5146869 = -1188641 (4) - 4979520 (7) + 5146869 = -34464335
Y₁ = 2489760 X₀ + 10430239 Y₀ - 10780770 = 2489760 (4) + 10430239 (7) - 10780770 = 72189943
So substitute x₁ = -34464335 and y₁ = 72189943, imply
X₂ = -1188641 X₁ - 4979520 Y₁ + 5146869 = -1188641 (-34464335) - 4979520 (72189943) + 5146869 = -318505538201756
Y₂ = 2489760 X₁ + 10430239 Y₁ - 10780770 = 2489760 (-34464335) + 10430239 (72189943) - 10780770 = 667150425396007
Therefore f(x,y)=3x² + 14xy + 6y² - 17x - 23y - 505 = 0
⇒f(4,7)=f(-34464335,72189943)=f(-318505538201756,667150425396007)=0
Nu Html Checker 
53 
na 
na