### Thursday, September 11, 2008

## Solving Quadratic Diophantine equations in 2 variables

Last Friday I discovered the following theorem, which I call the Quadratic Diophantine Theorem:

In the ring of integers, given the quadratic expression

c_1*x^2 + c_2*xy + c_3*y^2 = c_4*z^2 + c_5*zx + c_6*zy

where the c's are constants, for solutions to exist it must be true that

((c_2 - 2c_1)^2 + 4c_1*(c_2 - c_1 - c_3))v^2 + (2(c_2 - 2c_1)*(c_6 - c_5) + 4c_5*(c_2 - c_1 - c_3))v + (c_6 - c_5)^2 - 4c_4*(c_2 - c_1 - c_3) = n^2 mod p

for some n, where p is any prime coprime to z for a given solution, when

v = -(x+y)z^{-1} mod p.

For example with x^2 + y^2 = z^2, I have

c_1 = 1, c_2 = 0, c_3 = 1, c_4 = 1, c_5 = 0, and c_6 = 0

which gives

-4v^2 + 8 = n^2 mod p

for every prime coprime to z, for some n (remember ring is ring of integers) when v = -(x+y)z^{-1} mod p.

Making the substitution for v gives

-4(-(x+y)z^{-1})^2 + 8 = n^2 mod p

so

-4(x+y)^2 + 8z^2 = n^2*z^2 mod p

and since x^2 + y^2 = z^2, I can substitute out z, to get

4(x-y)^2 = n^2*z^2 mod p

so the requirement is met, as of course, there are an infinity of integer solutions to x^2 + y^2 = z^2.

And a square was required here because p can be any prime coprime to a solution for z, so an infinite number of primes must work!

Notice that the result also applies to the general diophantine quadratic in 2 variables by making z=1.

The theorem is proven easily using what I call tautological spaces.

Intriguingly the theorem shows a route to generally solving any quadratic Diophantine in 2 variables by letting z=1, as then you have

c_1*x^2 + c_2*xy + c_3*y^2 = c_4 + c_5*x + c_6*y

and the result is that

((c_2 - 2c_1)^2 + 4c_1*(c_2 - c_1 - c_3))v^2 + (2(c_2 - 2c_1)*(c_6 - c_5) + 4c_5*(c_2 - c_1 - c_3))v + (c_6 - c_5)^2 - 4c_4*(c_2 - c_1 - c_3) = n^2 mod p

where v = -(x+y) mod p, so you can substitute out, and have a result true for all primes p:

((c_2 - 2c_1)^2 + 4c_1*(c_2 - c_1 - c_3))(x+y)^2 - (2(c_2 - 2c_1)*(c_6 - c_5) + 4c_5*(c_2 - c_1 - c_3))(x+y) + (c_6 - c_5)^2 - 4c_4*(c_2 - c_1 - c_3) = S^2

where S is some integer. Notice then using some additional variables to make the exposition easier that with

A =(c_2 - 2c_1)^2 + 4c_1*(c_2 - c_1 - c_3)

B = 2(c_2 - 2c_1)*(c_6 - c_5) + 4c_5*(c_2 - c_1 - c_3)

and

C = (c_6 - c_5)^2 - 4c_4*(c_2 - c_1 - c_3)

you have

A(x+y)^2 - B(x+y) + C = S^2

and by completing the square and simplifying you have that

(2A(x+y) - B)^2 + 4AC - B^2 = 4AS^2

which is just another Diophantine equation in 2 variables but much simplified, and when you solve for x+y and S, you immediately get a solution for

c_1*x^2 + c_2*xy + c_3*y^2 = c_4 + c_5*x + c_6*y

but also you can check solvability easily with the result that

(2A(x+y) - B)^2 = 4AS^2 mod (B^2 - 4AC)

so A must be a quadratic residue modulo (B^2 - 4AC).

The result is important enough for all of that alone, but I'll mention that I looked for preliminary results with the theorem by using it on Pell's Equation, and found several tidbit results:

With x^2 - Dy^2 = 1, I have that

S^2 - D(x+y)^2 = -D + 1

so you see the second Diophantine equation connected to the first!

With D=2, I get then that x^2 - 2y^2 = 1, is connected to

S^2 - 2(x+y)^2 = -1

so for every solution of the first there is a solution of the second.

For example with D=2, I have x=17 and y=12 as solutions, but to x^2 - 2y^2 = 1, but notice I can immediately get that S = 41 is a solution using 17+12=29, so I have for the second equation 41^2 - 29^2 = -1.

Another result of interest I found with Pell's Equation is that for every solution to x^2 - 2y^2 = 1, there is a Pythagorean Triplet—an integer solution to u^2 + v^2 = w^2—of a particular form, which is that v=u+1, and w = x+y.

So for the result I noted above where x=17, and y = 12, I have u = 20 and v=21, and w=29, as

20^2 + 21^2 = 29^2.

The further result for x^2 - Dy^2 = 1, is that for every case where D-1 is a square there is a relation with a Pythagorean Triplet, and if it's not a square, there is a relation to the ellipse:

(D-1)u^2 + v^2 = w^2

where again w=x+y.

So in some sense Pell's Equation may be elliptical which may explain to some extent how it comes up in the sciences.

I hope my fellow physics explorers will welcome these new additions to our mathematical arsenal and look to see what deeper answers may be found through this simplification of quadratics in 2 variables.

For further information including the proof of the theorem, go to my math blog.

In the ring of integers, given the quadratic expression

c_1*x^2 + c_2*xy + c_3*y^2 = c_4*z^2 + c_5*zx + c_6*zy

where the c's are constants, for solutions to exist it must be true that

((c_2 - 2c_1)^2 + 4c_1*(c_2 - c_1 - c_3))v^2 + (2(c_2 - 2c_1)*(c_6 - c_5) + 4c_5*(c_2 - c_1 - c_3))v + (c_6 - c_5)^2 - 4c_4*(c_2 - c_1 - c_3) = n^2 mod p

for some n, where p is any prime coprime to z for a given solution, when

v = -(x+y)z^{-1} mod p.

For example with x^2 + y^2 = z^2, I have

c_1 = 1, c_2 = 0, c_3 = 1, c_4 = 1, c_5 = 0, and c_6 = 0

which gives

-4v^2 + 8 = n^2 mod p

for every prime coprime to z, for some n (remember ring is ring of integers) when v = -(x+y)z^{-1} mod p.

Making the substitution for v gives

-4(-(x+y)z^{-1})^2 + 8 = n^2 mod p

so

-4(x+y)^2 + 8z^2 = n^2*z^2 mod p

and since x^2 + y^2 = z^2, I can substitute out z, to get

4(x-y)^2 = n^2*z^2 mod p

so the requirement is met, as of course, there are an infinity of integer solutions to x^2 + y^2 = z^2.

And a square was required here because p can be any prime coprime to a solution for z, so an infinite number of primes must work!

Notice that the result also applies to the general diophantine quadratic in 2 variables by making z=1.

The theorem is proven easily using what I call tautological spaces.

Intriguingly the theorem shows a route to generally solving any quadratic Diophantine in 2 variables by letting z=1, as then you have

c_1*x^2 + c_2*xy + c_3*y^2 = c_4 + c_5*x + c_6*y

and the result is that

((c_2 - 2c_1)^2 + 4c_1*(c_2 - c_1 - c_3))v^2 + (2(c_2 - 2c_1)*(c_6 - c_5) + 4c_5*(c_2 - c_1 - c_3))v + (c_6 - c_5)^2 - 4c_4*(c_2 - c_1 - c_3) = n^2 mod p

where v = -(x+y) mod p, so you can substitute out, and have a result true for all primes p:

((c_2 - 2c_1)^2 + 4c_1*(c_2 - c_1 - c_3))(x+y)^2 - (2(c_2 - 2c_1)*(c_6 - c_5) + 4c_5*(c_2 - c_1 - c_3))(x+y) + (c_6 - c_5)^2 - 4c_4*(c_2 - c_1 - c_3) = S^2

where S is some integer. Notice then using some additional variables to make the exposition easier that with

A =(c_2 - 2c_1)^2 + 4c_1*(c_2 - c_1 - c_3)

B = 2(c_2 - 2c_1)*(c_6 - c_5) + 4c_5*(c_2 - c_1 - c_3)

and

C = (c_6 - c_5)^2 - 4c_4*(c_2 - c_1 - c_3)

you have

A(x+y)^2 - B(x+y) + C = S^2

and by completing the square and simplifying you have that

(2A(x+y) - B)^2 + 4AC - B^2 = 4AS^2

which is just another Diophantine equation in 2 variables but much simplified, and when you solve for x+y and S, you immediately get a solution for

c_1*x^2 + c_2*xy + c_3*y^2 = c_4 + c_5*x + c_6*y

but also you can check solvability easily with the result that

(2A(x+y) - B)^2 = 4AS^2 mod (B^2 - 4AC)

so A must be a quadratic residue modulo (B^2 - 4AC).

The result is important enough for all of that alone, but I'll mention that I looked for preliminary results with the theorem by using it on Pell's Equation, and found several tidbit results:

With x^2 - Dy^2 = 1, I have that

S^2 - D(x+y)^2 = -D + 1

so you see the second Diophantine equation connected to the first!

With D=2, I get then that x^2 - 2y^2 = 1, is connected to

S^2 - 2(x+y)^2 = -1

so for every solution of the first there is a solution of the second.

For example with D=2, I have x=17 and y=12 as solutions, but to x^2 - 2y^2 = 1, but notice I can immediately get that S = 41 is a solution using 17+12=29, so I have for the second equation 41^2 - 29^2 = -1.

Another result of interest I found with Pell's Equation is that for every solution to x^2 - 2y^2 = 1, there is a Pythagorean Triplet—an integer solution to u^2 + v^2 = w^2—of a particular form, which is that v=u+1, and w = x+y.

So for the result I noted above where x=17, and y = 12, I have u = 20 and v=21, and w=29, as

20^2 + 21^2 = 29^2.

The further result for x^2 - Dy^2 = 1, is that for every case where D-1 is a square there is a relation with a Pythagorean Triplet, and if it's not a square, there is a relation to the ellipse:

(D-1)u^2 + v^2 = w^2

where again w=x+y.

So in some sense Pell's Equation may be elliptical which may explain to some extent how it comes up in the sciences.

I hope my fellow physics explorers will welcome these new additions to our mathematical arsenal and look to see what deeper answers may be found through this simplification of quadratics in 2 variables.

For further information including the proof of the theorem, go to my math blog.