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 x² - Dy² = C, if a Diophantine solution exists, a shift of variables, also simplifies everything allowing you to solve for y modularly:

(z-y)² - Dy² = C

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

So:

z² - 2zy + y² - Dy² = C, so: z² - 2zy + (1- D)y² = C

2zy = z² - C - (D-1)y²

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:

x² - Dy² = C mod D-1, which of course is: x² - y² = 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)² - Dy² = C

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

(z-y)²  = y² + C mod D-1

Which is, of course, also valid with the original: x²  = y² + 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 x² - Dy² = 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)² - Dy² = F.

Given (z-ky)² - Dy² = 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-k²

(z-ky)² = k²y² + F mod D-k²

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-k² is a square.

And now you have the route to solutions for: x² - Dy² = F mod D-k²

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

Let's consider an interesting D. Let D = 2ⁿ + 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 2ⁿ

(z-y)² = y² + 1 mod 2ⁿ

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

Which forces y = 0 or 4 mod 32 with x² - (2⁵ + 1)y² = 1.

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

2y = (z - z^-1) mod 2ⁿ - 2

(z-y)² = y² + 1 mod 2ⁿ - 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 y² can only be 0, 36, 63, or 99 mod 126 when x² - (2⁷ - 1)y² = 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