Translate

Saturday, September 06, 2008

Quadratic Diophantine Result

Quadratic Diophantine Theorem:

In the ring of integers, given the quadratic expression

c1x2 + c2xy + c3y2 = c4z2 + c5zx + c6zy

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

((c2 - 2c1)2 + 4c1(c2 - c1 - c3))v2 + (2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3))v + (c6 - c5)2 - 4c4(c2 - c1 - c3) = n2 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 x2 + y2 = z2, I have

c1 = 1, c2 = 0, c3 = 1, c4 = 1, c5 = 0, and c6 = 0

which gives

-4v2 + 8

is a quadratic residue modulo p, for every prime coprime to z, when v = -(x+y)z-1 mod p.

Making the substitution gives

-4(-(x+y)z-1)2 + 8 = n2 mod p

for some n, which is

-4(x+y)2 + 8z2 = n2z2 mod p

and since x2 + y2 = z2, I can substitute out z on the left side, to get

4(x-y)2 = n2z2 mod p.

Proof of theorem:

The theorem is proven using what I call a tautological space, where

x+y+vz = 0(mod x+y+vz)

as then I have x+y = -vz (mod x+y+vz), and can square both sides to get

x2 + 2xy + y2 = v2z2 (mod x+y+vz)

and multiply both sides by c1 and subtract from

c1x2 + c2xy + c3y2 = c4z2 + c5zx + c6zy

and use x = -y-vz (mod x+y+v) to substitute out x, and simplify to get

(c4 - c5v - c1v2)z2 + ((c2 -2c1)v - c5 + c6)zy + (c2 - c1 - c3)y2 = 0 (mod x+y+vz)

and then it's just a matter of completing the square, and collecting terms multiplied times y2 on the right, as you have an equation of the form

(Az + By)2 = Cy2 (mod x+y+vz)

and noting then that C must be a quadratic residue modulo p, where p is any prime such that

x+y+vz = 0 mod p

where coprimeness with z is required by the solution v = -(x+y)z-1 mod p.

Proof complete.

The Quadratic Diophantine Theorem allows determination of whether or not integer solutions are prohibited from existence for the given specified quadratic expression for various constants, because of the requirement that any prime coprime to z for a solution must have the given quadratic residue.

The theorem can be used prime by prime, or a more general result can be obtained by substituting out for v, in

((c2 - 2c1)2 + 4c1(c2 - c1 - c3))v2 + (2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3))v + (c6 - c5)2 - 4c4(c2 - c1 - c3) = n2 mod p

to get

((c2 - 2c1)2 + 4c1(c2 - c1 - c3))(x+y)2  - (2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3))(x+y)z + [(c6 - c5)2 - 4c4(c2 - c1 - c3)]z2 = n2z2 mod p

as then the left hand side must be a quadratic residue for any prime p, which requires then that

((c2 - 2c1)2 + 4c1(c2 - c1 - c3))(x+y)2 - (2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3))(x+y)z + [(c6 - c5)2 - 4c4(c2 - c1 - c3)]z2 = m2

where m is some integer.

Then you can substitute out for z2 as with my example before, and either have a perfect square as with that example, or solve for cases when integer solutions are available with something of the general form

A(x+y) = +/-Bz

for specific cases of m that will give integers.

Note: You have a requirement on a general quadratic diophantine solution in two variables by letting x=1.

The reach of the theorem is remarkable considering how simply it is derived and shows with yet another mathematical result the power of what I call tautological spaces.


James Harris

2 comments:

robkim55 said...

Can you offer any numerical examples (2 or 3)

James Harris said...

I can do better, as I used the result to find the best method known for generally reducing binary quadratic Diophantine equations.

I'm adding a link to a page on that where you can also see two numerical examples:

http://mymath.blogspot.com/2011/05/reducing-binary-quadratic-diophantines.html