Monday, April 23, 2012

Quadratic residue spacing

The equation x2 - Dy2 = F has become extremely interesting to me, as I've found the mechanism, which I call a quadratic residue engine, by which number theory spaces quadratic residues by a seemingly minor shift from the established old form.

Instead of x2 - Dy2 = F, let x = z-ky or x = -(z-ky), so:

(z-ky)2 - Dy2 = F.

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.

The result 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, which governs spacing of quadratic residues relative to each other.

The rules allow only 3 possibilities for quadratic residues of D-k2:

1. y = 0 mod D-k2
2. Some quadratic residue is exactly F mod D-k2 away from another.
3. Some quadratic residue plus F mod D-k2 equals 0 mod D-k2.

These can be fairly severe constraints.

For instance 12 has no quadratic residues 1 away from another, and 11 is not a quadratic residue, so condition 1. is forced when F=1 mod D-k2.

Here are the quadratic residues for 12: 1, 4, 9

Intriguingly that limits F, for x2 - 13y2 = F, only allowing F = 0, 3, 8 or 11 mod 12.

For example: 16 - 13 = 3, 25 - 13 = 12, 36 -13 = 23 = 11 mod 12.

But the quadratic residues for 13 are: 1, 3, 4, 9, 10, 12

And 11 is not a quadratic residue of 13, but notice 23 mod 13 = 10, which is, so you also know that explicitly F will never equal 11. It also can't exactly equal 8 for the same reason.

Without the quadratic residue engine one might erroneously believe that the only constraint on F is that it be a quadratic residue of 13 or equal 0 mod 13.

It's intriguing then that numbers with fewer quadratic residues exert an extraordinary influence.

As notice the result covers infinity as if D-k2 = 12, then F mod 12 = 0, 3, 8, or 11 at most, but may be less if 3, 8 or 11 is not a quadratic residue modulo D.

If D-k2 is prime then x2 - Dy2 = F has the most leeway for values of F, because primes have the most quadratic residues, so the equation with D=12 is less constrained than with D=13, as 11 gives more leeway for F.

The result is a new one for me to consider and I'll admit it's exciting and a bit overwhelming thinking through all the implications, where time is likely to indicate more.

But now the equation x2 - Dy2 = F is a LOT more interesting than it was before, as quadratic residue spacing emerges as a critical force in its behavior thanks to the find of the quadratic residue engine.

James Harris

No comments: