^{2}- Dy

^{2}= F can be shown to be controlled by a number theoretic structure I call a quadratic residue engine.

First you need new variables z and k, where x = z - ky or x = -(z-ky).

Then it can be shown that if integer solutions for x

^{2}- Dy

^{2}= F exist, it must be true that:

2ky = z - Fz

^{-1}mod D-k

^{2}

(z-ky)

^{2}= k

^{2}y

^{2}+ F mod D-k

^{2}

Here there is the additional requirement that 2kyz + F = -1 or 1 mod 8, or 0 mod 4, if D-k

^{2}is a square.

So you can solve for y modularly for: x

^{2}- Dy

^{2}= F mod D-k

^{2}

The result allows you to generate quadratic residues k

^{2}y

^{2}+ F at will using the variable z as a driver, as that gives you y mod D-k

^{2}from the first equation in the engine, but will only give quadratic residues that are either F mod D-k

^{2}itself or F mod D-k

^{2}away from another quadratic residue.

Now consider z and z', such that:

2ky = z

^{-1}(z

^{2}- F) = z'

^{-1}(z'

^{2}- F) mod D-k

^{2}

Then:

z'*z

^{2}- z'F = z*z'

^{2}- zF mod D-k

^{2}, so

z'*z

^{2}- z*z'

^{2}= (z' - z)F mod D-k

^{2}, and:

z'*z(z - z') = (z' - z)F mod D-k

^{2}, and now if z - z' is coprime to D-k

^{2}, then I have finally z'*z = -F mod D-k

^{2}, or z' = -Fz

^{-1}mod D-k

^{2}.

With F=1 and k=1, this result allows you to count quadratic residue pairs.

The quadratic residue engine can be used to note distances between residues, for instance with D=127, which is prime, and F=1, I can picked the nearest square greater than 127, which is 144, to find:

12

^{2}- 127(1)

^{2}= 17

That tells me that 17 is a quadratic residue, there exists a gap of 17 between at least one set of quadratic residues for 127, or some quadratic residue plus 17 equals 0 mod 127.

The quadratic residues for 127 are:

1, 2, 4, 8, 9, 11, 13, 15, 16, 17, 18, 19, 21, 22, 25, 26, 30, 31, 32, 34, 35, 36, 37, 38, 41, 42, 44, 47, 49, 50, 52, 60, 61, 62, 64, 68, 69, 70, 71, 72, 73, 74, 76, 79, 81, 82, 84, 87, 88, 94, 98, 99, 100, 103, 104, 107, 113, 115, 117, 120, 121, 122, 124

So 17 is a quadratic residue, and also I noticed 15 and 32 work for that requirement.

But there is also a requirement for 127 - k

^{2}for other than k=1, so for instance, 123 must have the same requirements as well. But for k = 11, the requirement is 17 mod 6, which is 5.

The quadratic residues for 6 are: 1, 3, 4

And the requirement is fulfilled by 1, since 1+5 = 0 mod 6.

James Harris

## No comments:

Post a Comment