^{2}- Dy

^{2}= F, I can generalize as follows.

(z-ky)

^{2}- Dy

^{2}= F

Expand out:

z

^{2}- 2kyz + k

^{2}y

^{2}- Dy

^{2}= F

Now obviously, it makes sense to group the y

^{2}, and see:

z

^{2}- 2kyz - (D-k

^{2})y

^{2}= F, which is also z

^{2}- 2kyz - F = (D-k

^{2})y

^{2}, 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:

z

^{2}- 2kyz = F mod D-k

^{2}

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

z

^{2}- 2kyz - F = 0 mod D-k

^{2}

And solve for y, to find:

2y = (kz)

^{-1}(z

^{2}- F) mod D-k

^{2}

which is also:

2y = k

^{-1}(z - Fz

^{-1}) mod D-k

^{2}

Turns out that I need one more equation.

Going back to: (z-ky)

^{2}- Dy

^{2}= F

Let's add k

^{2}y

^{2}to both sides: (z-ky)

^{2}+ k

^{2}y

^{2}- Dy

^{2}= k

^{2}y

^{2}+ F

and now again focusing mod D-k

^{2}, I have:

(z-ky)

^{2}= k

^{2}y

^{2}+ F mod D-k

^{2}

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

Given (z-ky)

^{2}- Dy

^{2}= F, if integer solutions for a chosen k exist, it must be true that:

2y = k

^{-1}(z - Fz

^{-1}) mod D-k

^{2}

(z-ky)

^{2}= k

^{2}y

^{2}+ F mod D-k

^{2}

where 2kyz + F = -1 or 1 mod 8, or 0 mod 4, if D-k

^{2}is a square.

Giving solutions for: x

^{2}- Dy

^{2}= F mod D-k

^{2}

James Harris

## No comments:

Post a Comment