Translate

Friday, September 26, 2008

Solvability and Diophantine Quadratic Chains

Deciding to take my newly discovered Quadratic Diophantine Theorem for a spin against "Pell's Equation" turned out to be a good idea as besides letting me validate that I had derived the theorem correctly, it also showed me that the result I had didn't simply lead in a BFC--Big Freaking Circle.

Still there is more as it indicates a route to finding a general solution for all 2 variable Diophantine equations using what I now call quadratic chains, which are infinite chains of related Diophantine equations.

To derive the full theory I will use

c1x2 + c2xy + c3y2 = c4z2 + c5zx + c6zy

with z=1, so I have

((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,

like before but because z=1, I can immediately substitute and generalize to all primes as I did in my previous post with Pell's Equation to get

((c2 - 2c1)2 + 4c1(c2 - c1 - c3))(x+y)2 - (2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3))(x+y) + (c6 - c5)2 - 4c4(c2 - c1 - c3) = S2

for some integer S, and to simplify doing the next calculations let

A = (c2 - 2c1)2 + 4c1(c2 - c1 - c3)

B = 2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3)

and

C = (c6 - c5)2 - 4c4(c2 - c1 - c3)

so I have

A(x+y)2 - B(x+y) + C = S2

and it's immediately clear that I just have another quadratic Diophantine equation!

Now manipulating to complete the square gives

(A(x+y) - B/2)2 + AC - (B/2)2 = AS2

which is

(2A(x+y) - B)2 + 4AC - B2 = 4AS2

and I have then the new quadratic Diophantine:

(2A(x+y) - B)2 - 4AS2 = B2 - 4AC

and have the stunning result that every quadratic Diophantine in two variables is connected to a quadratic Diophantine of the form:

u2 - Dv2 = F

and I get an existence condition as

(2A(x+y) - B)2 = 4AS2 mod (B2 - 4AC)

so I have that A must be a quadratic residue modulo (B2 - 4AC) if A is coprime to B.

Also I have that if solutions exist and A is negative, then there are only a finite number of solutions.

But further

(2A(x+y) - B)2 - 4AS2 = B2 - 4AC

is another Diophantine equation so I can use it to get yet another equation of the same form.

And if one has rational solutions the next must have solutions, all the way out to infinity if the series goes on forever.

Next I note that if B does not equal 0 using the starting equation, with the next member of the chain you have that

c1=1, c2=0, c5 = 0, and c6 = 0, so I have

A = - 4c3, B=0, C = 4c4(1 + c3)

so I have

(2c3(x+y))2 + c3S2 = 4c3c4(1 + c3)

which is

4c3(x+y)2 + S2 = 4c4(1 + c3)

which is

(S/2)2 + c3(x+y)2 = c4(1 + c3)

so for the next iteration I'd have

4c3(S/2+x+y)2 + T2 = 4c4(1 + c3)2

and I can again re-group and divide off 4 from both sides to have

(T/2)2 + c3(S/2+x+y)2 = c4(1 + c3)2

and see the emergence of a pattern where c3 remains the same throughout.

Intriguingly some prior number theory can now be explained as in general after the initial equation, following equations in the chain look like

u2 + c3v2 = c4(1 + c3)j

where j can be 0 or a natural number

So with c3=-2, you just have

u2 - 2v2 = c4(-1)j

and the remarkable result that you have only two primary forms.

The only simpler case is with c3=-1, when you just get

u2 = v2.

So if A is negative and B2 - 4AC is 1, -1, 2 or -2--where the quadratic residue requirement is of no use--I can simply go down the chain until it applies and may have a solution.

However, there has to be an additional constraint along with the initial quadratic residue constraint, as consider

x2 - 10y2 = 3

as it has no solutions; although 10 mod 3 = 1, so 10 is a quadratic residue modulo 3.

Going back to the general case

u2 + c3v2 = c4(1 + c3)j

I have also that -c3 must be a quadratic residue modulo c4(1+c3), but I also importantly have that

c4(1 + c3)j

must be a quadratic residue modulo c3 as long as c4 does not have any square factors so that dual requirement provides the full existence conditions, and the dual residue requirement can be a means to a solution.

Author's note: Square factors are a big deal which have to be addressed more fully than I first hoped. If x2 + Dy2 = n2 then -D may not be a quadratic residue modulo n2, but dividing n2 from both sides gives

(x/n)2 + D(y/n)2 = 1

which has any solutions to u2 + Dv2 = 1, so x=nu, and y=nv.

In general with u2 + Dv2 = F, if F = Gn2, and -D is not a quadratic residue modulo F, then check modulo G. 10/19/08


For instance, if v2=1 mod c4(1 + c3)j from my little congruence result:

With c3 coprime to c4(1 + c3), if u2 = r1 mod c3 and u2 = r2 mod c4(1 + c3)j, you can find u2 mod c3c4(1 + c3)j with

u2 = r1 + kc3 mod c3c4(1 + c3)j

where k = (r2 - r1)c3-1 mod c4(1 + c3)j

where

r1 = c4(1 + c3)j mod c3 and

r2 = -c3 mod c4(1 + c3)j

and you find k, such that r1 + kc3 is a perfect square, where you increment up from j=0.

Picking v may seem suspect but if there are an infinity of solutions then unless particular residues are excluded for some unknown reason there would be solutions for any residue, but if there is a problem finding solutions with v2=1 mod c4(1 + c3)j, you can search with other values using

r2 = -c3v2 mod c4(1 + c3)j.

So if no residues are excluded that is the general theory for finding solutions.

Not bad for a theorem just recently discovered, and it shows the incredible power of what I call tautological spaces.

They have the power to simplify.


James Harris

Thursday, September 18, 2008

Considering a Diophantine chain

I am curious about the latest result and figured a simple test would allow me to see what Diophantine chains look like, so here goes.

The method works with an equation of the form

c1x2 + c2xy + c3y2 = c4 + c5x + c6y

and to keep things easy for me, I'll use

x2 + 2xy + 3y2 = 4 + 5x + 6y

so I have

c1 = 1, c2 = 2, c3 = 3, c4 = 4, c5 = 5, and c6 = 6

so next I need to calculate

A = (c2 - 2c1)2 + 4c1(c2 - c1 - c3) = -8

B = 2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3) = -40

and

C = (c6 - c5)2 - 4c4(c2 - c1 - c3) = 33

and I have then the new quadratic Diophantine:

(2A(x+y) - B)2 - 4AS2 = B2 - 4AC

which is

(-16(x+y) + 40)2 + 32S2 = 2656

and dividing off 16, I have

(-4(x+y) + 10)2 + 2S2 = 166.

Which has a solution at S=9, giving

-4(x+y) + 10 = +/- 2

and trying the positive first gives x+y = 2, while the negative gives x+y = 3.

Trying the first case, x = 2-y and plugging that into the equation gives

(2-y)2 + 2(2-y)y + 3y2 = 4 + 5(2-y) + 6y

which is

4 - 4y + y2 + 4y - 2y2 + 3y2 = 4 + 10 - 5y + 6y

which is

2y2 -y - 10 = 0,

so y = (1 +/- sqrt(1 + 80))/4 = (1+/-9)/2 = -2 as the other case is a fraction.

Then x=4, so I can try x=4, y=-2, with

x2 + 2xy + 3y2 = 4 + 5x + 6y

and get

16 + 2(4)(-2) + 3(-2)2 = 4 + 5(4) + 6(-2)

which is 12 = 12, so they balance out as they must. I'll leave the second solution to the reader. Notice there are only two.

That was easy to solve but I'm curious about the next value in the chain, so looking again at

(-4(x+y) + 10)2 + 2S2 = 166

I now have c1 = 1, c3=2, and c4 = 166, while all other values are 0, so

A = -8, B = 0, and C = 1992

so the new quadratic Diophantine after some simplifying is:

(-4(-4(x+y)+10 + S))2 + 2T2 = 3984

where the right hand side is definitely increasing which indicates an infinite chain.

Intriguingly 3984 = 16(3)(83), which is intriguing because -2 must be a quadratic residue modulo each prime or 0 modulo that prime, and notice that 3 - 2 = 1, and 83 - 2 = 81.

The existence condition from the quadratic residues is probably the absolute determinant as to whether or not integer solutions exist, I'd surmise.


James Harris

Sunday, September 07, 2008

Quadratic Diophantine Theorem and Pell's Equation

With the Quadratic Diophantine Theorem derived, it makes sense to try it out with a well-known equation in Diophantine theory which is Pell's Equation:

x2 - Dy2 = 1

with D a natural number.

Now again, the Quadratic Diophantine Theorem:

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.

So with Pell's Equation I have

c1 = 1, c2=0, c3 = -D, c4 = 1, c5 = 0, c6 = 0, and z=1

which gives

4Dv2 - 4D + 4 = n2 mod p

and v = -(x+y) mod p, so I have

4D(x+y)2 - 4D + 4 = n2 mod p

and since that must be true for all primes p, since z=1, I have in general that the left hand side must be a perfect square so it must be true then that

D(x+y)2 - D + 1 = S2

where S is some integer, and I have in general that

x+y = sqrt((S2 + D - 1)/D).

Example: From a reference I have that with D=2, x=17 and y=12 are solutions.

Working backwards I found that S=41 gives that solution, verifying the result.

Notice also that S2 = 1 mod D. It is of interest to consider the special case of S = 1 mod D or S = -1 mod D, and as that's tedious in what I follows I just use S = +/-1 mod D, where it's an OR, so both cases are not true.

So I can make the substitution S = jD +/- 1, to find

x+y = sqrt(Dj2 +/- 2j + 1)

which is

x+y = sqrt((D-1)j2 + (j +/- 1)2)

and I have the existence of solutions related to another Diophantine relation of the form

(D-1)u2 + v2 = w2

with the condition that u = j and v = j+/-1.

For instance with D=2, I have that I need solutions to

u2 + v2 = w2

with u=j, and v=j+/-1, and j=20 works as 202 + 212 = 292, and gives x+y = 29, and again x=17, y=12 is a known solution to x2 - 2y2 = 1.

So then x2 - 2y2 = 1 is related to certain Pythagorean triples, when D is prime.

Also notice that from

x+y = sqrt((S2 + D - 1)/D)

I have

S2 - D(x+y)2 = -D + 1

which means a second Diophantine equation connected to the first!

With D=2, I get then that x2 - 2y2 = 1, is connected to

S2 - 2(x+y)2 = -1

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

So there is an immediate result with the classical Pell's Equation, with little effort at all using the theorem, which can be used against any Diophantine quadratic in 2 variables, almost as easily, and also give results in 3 variables, though not quite as generally.


James Harris

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