Translate

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

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

Quadratic Residues and Binary Quadratic Diophantine

Quadratic residues have interesting control features with regard to binary quadratic Diophantine equations, where a simple shift of variables with a traditionally known equation quickly leads to substantial results.

Instead of x2 - Dy2 = C, if a Diophantine solution exists, a shift of variables, also simplifies everything allowing you to solve for y modularly:

(z-y)2 - Dy2 = C

So x = z-y or x = -(z-y), as you can have plus or minus.

So:

z2 - 2zy + y2 - Dy2 = C, so: z2 - 2zy + (1- D)y2 = C

2zy = z2 - C - (D-1)y2

And finally:

2y = z - Cz-1 mod D-1.

So z must be coprime, which means, not share any prime factors, with D-1 for the modular inverse to exist.

The result then has the general validity of:

x2 - Dy2 = C mod D-1, which of course is: x2 - y2 = C mod D-1

At first blush the result might seem to have limited efficacy as what good are modular solutions anyway?

But now we can introduce quadratic residues as a control feature.

Going again to: (z-y)2 - Dy2 = C

Add y2 to both sides and switch to a modular equation as before and you have:

(z-y)2  = y2 + C mod D-1

Which is, of course, also valid with the original: x2  = y2 + C mod D-1

That constraint from quadratic residues can have a huge impact, for instance, with C=1, October last year I used it to count quadratic residue pairs.

The mechanism is that the separation between quadratic residues is controlled by this equation, and then is shown to be related back to x2 - Dy2 = C.

But that covers infinity, as if a solution exists for a given D, for any particular C, then there is a constraint from the quadratic residues of D-1.

However, I can generalize further!

In November of last year, I generalized with (z-ky)2 - Dy2 = F.

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

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

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

which I call  a quadratic residue engine.

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

And now you have the route to solutions for: x2 - Dy2 = F mod D-k2

Wow. So not only does D-1 push requirements based on the distance between its quadratic residues but D-k2  does as well! And k can go to infinity.

Let's consider an interesting D. Let D = 2n + 1, where n is a counting number. And use the simpler case with k=1 and F=1, then the quadratic residue engine is:

2y = (z - z-1) mod 2n

(z-y)2 = y2 + 1 mod 2n

For instance with n=5, the quadratic residues are: 1, 4, 9, 16, 17*, 25

Which forces y = 0 or 4 mod 32 with x2 - (25 + 1)y2 = 1.

To consider Mersenne primes, let D = 2n - 1, and k=1, with F=1, then the engine is:

2y = (z - z-1) mod 2n - 2

(z-y)2 = y2 + 1 mod 2n - 2

So, let's say n=7, just for a random pick that's not too large. Here are the quadratic residues for 126:

1, 4, 7, 9, 16, 18, 22, 25, 28, 36, 37*, 43, 46, 49, 58, 63, 64*, 67, 70, 72, 79, 81, 85, 88, 91, 99, 100*, 106, 109, 112, 121

So y2 can only be 0, 36, 63, or 99 mod 126 when x2 - (27 - 1)y2 = 1.

Now that's what I call fun. Such an intriguingly powerful result that shows that quadratic residues have a huge role in number theory with regard to binary quadratic Diophantine equations.

They are the powers that rule this number theoretic domain.


James Harris