Saturday, November 05, 2011

Generalizing quadratic Diophantine

Using an alternate form from x2 - Dy2 = F, I can generalize as follows.

(z-ky)2 - Dy2 = F

Expand out:

z2 - 2kyz + k2y2 - Dy2 = F

Now obviously, it makes sense to group the y2, and see:

z2 - 2kyz - (D-k2)y2 = F, which is also z2 - 2kyz - F = (D-k2)y2, which requires that 2kyz + F = -1 or 1 mod 8, or 0 mod 4.

And now for what is an amazing trick, which only arrived with modular arithmetic, as before, to mathematicians who did not have it, the above would be pointless.

They literally could not see what happens next:

z2 - 2kyz = F mod D-k2

And now you can move that F to the left hand side:

z2 - 2kyz - F = 0 mod D-k2

And solve for y, to find:

2y = (kz)-1(z2 - F) mod D-k2

which is also:

2y = k-1(z - Fz-1) mod D-k2

Turns out that I need one more equation.

Going back to: (z-ky)2 - Dy2 = F

Let's add k2y2 to both sides: (z-ky)2 + k2y2 - Dy2 = k2y2 + F

and now again focusing mod D-k2, I have:

(z-ky)2 = k2y2 + F mod D-k2

And I have what I like to call a quadratic residue engine, which then is as follows.

Given (z-ky)2 - Dy2 = F, if integer solutions for a chosen k exist, it must be true that:

2y = k-1(z - Fz-1) mod D-k2

(z-ky)2 = k2y2 + F mod D-k2

where 2kyz + F = -1 or 1 mod 8, or 0 mod 4, if D-k2 is a square.

Giving solutions for: x2 - Dy2 = F mod D-k2

James Harris
Post a Comment