Instead of x

^{2}- Dy

^{2}= C, if a Diophantine solution exists, a shift of variables, also simplifies everything allowing you to solve for y modularly:

(z-y)

^{2}- Dy

^{2}= C

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

So:

z

^{2}- 2zy + y

^{2}- Dy

^{2}= C, so: z

^{2}- 2zy + (1- D)y

^{2}= C

2zy = z

^{2}- C - (D-1)y

^{2}

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

^{2}- Dy

^{2}= C mod D-1, which of course is: x

^{2}- y

^{2}= 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}- Dy

^{2}= C

Add y

^{2}to both sides and switch to a modular equation as before and you have:

(z-y)

^{2}= y

^{2}+ C mod D-1

Which is, of course, also valid with the original: x

^{2}= y

^{2}+ 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

^{2}- Dy

^{2}= 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}- Dy

^{2}= F.

Given (z-ky)

^{2}- Dy

^{2}= 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

^{2}

(z-ky)

^{2}= k

^{2}y

^{2}+ F mod D-k

^{2}

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

^{2}is a square.

And now you have the route to solutions for: x

^{2}- Dy

^{2}= F mod D-k

^{2}

Wow. So not only does D-1 push requirements based on the distance between its quadratic residues but D-k

^{2}does as well! And k can go to

*infinity*.

Let's consider an interesting D. Let D = 2

^{n}+ 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

^{n}

(z-y)

^{2}= y

^{2}+ 1 mod 2

^{n}

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}- (2

^{5}+ 1)y

^{2}= 1.

To consider Mersenne primes, let D = 2

^{n}- 1, and k=1, with F=1, then the engine is:

2y = (z - z

^{-1}) mod 2

^{n}- 2

(z-y)

^{2}= y

^{2}+ 1 mod 2

^{n}- 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

^{2}can only be 0, 36, 63, or 99 mod 126 when x

^{2}- (2

^{7}- 1)y

^{2}= 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

## No comments:

Post a Comment