Wednesday, October 05, 2011

Quadratic Residue Pairs

Remarkably enough the math itself gave me a different way to consider a famous equation, as it gave me a new form when I did some detailed analysis.

It gave me: (n-m)2 - Dm2 = 1

And that is a seemingly minor shift from the traditional x2 - Dy2 = 1.

But in my post yesterday I noted that it gives a quadratic residue engine:

2m = n-1(n2 - 1) mod D-1

(n - m)2 = m2 + 1 mod D-1

Which I just fully realized yesterday and here's a quick example I tossed up.

Let D=12, to see mod 11. And let n=2, then:

2m = 2-1(3) mod 11 = 6(3) mod 11, so m = 9 mod 11

And now we go to the second equation and have:

(2 - 9)2 = 92 + 1 mod 11

which is: 72 = 5 mod 11

With such a new result there is so much to figure out, and already this one is intriguing because it reveals what I've decided to call quadratic residue pairs, which are quadratic residues that differ by 1.

In this case the pair is 4, 5, as both are quadratic residues modulo 11, and they differ by 1.

And it is an awesomely cool result as now you can look at lists of quadratic residues and see some fairly odd things. For instance, if D is a square, so that the original equation does not give integer answers, then you may have no quadratic residues that differ by 1.

Now, if you scan through quadratic residues when D is not a square you'll see there is usually at least one case, except when D-1 is a perfect square. With some exceptions like D=13, where 12 has no quadratic residues that differ by 1.

The behavior is controlled by the second half of the quadratic residue engine:

(n - m)2 = m2 + 1 mod D-1

There m2 plus 1 is forced to be a quadratic residue as well or to equal 0 mod D-1.

But from the first equation of the engine, since n has to be coprime to D-1 for the modular inverse to exist, for m to equal 0 for all n, it must be true that n2 - 1 = 0 mod D-1, for all allowed values of n. For D=13, it just so happens that it is. That also happens for D=17, as 16 has no quadratic residues that differ by 1.

And those are things I just figured out while pondering this latest line of approach.

It is beautiful and amazing to me that the math itself gave me a different way to write an equation! And its way is MUCH better than the traditional one, and gives more rules for the behavior of quadratic residues.

The math knew better than people.

It had to show me the better way to write the equation. Wow.

But of course, it makes sense. We are limited by our imaginations while mathematics itself is not.

James Harris

No comments: