Saturday, April 21, 2012

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.


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
Post a Comment