Translate

Saturday, April 21, 2012

Generalized quadratic residue engine

The binary quadratic Diophantine equation x2 - Dy2 = 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  x2 - Dy2 = F exist, it must be true that:

2ky = z - Fz-1 mod D-k2

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

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

So you can solve for y modularly for: x2 - Dy2 = F mod D-k2

The result allows you to generate quadratic residues k2y2 + F at will using the variable z as a driver, as that gives you y mod D-k2 from the first equation in the engine, but will only give quadratic residues that are either F mod D-k2 itself or F mod D-k2 away from another quadratic residue.

Now consider z and z', such that:

2ky = z-1(z2 - F) = z'-1(z'2 - F) mod D-k2

Then:

z'*z2 - z'F = z*z'2 - zF mod  D-k2, so

z'*z2 - z*z'2 = (z' - z)F mod  D-k2, and:

z'*z(z - z') = (z' - z)F mod  D-k2, and now if z - z' is coprime to D-k2, then I have finally z'*z = -F mod  D-k2, or z' = -Fz-1 mod  D-k2.

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:

122 - 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 - k2 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: