Quadratic residue pairs and urge to know why

One of my favorite results explains the count of things called quadratic residue pairs. And while the way to count for primes has been known, I found a way to derive the result previously deduced. And it took some modular arithmetic and an alternate form to a well-known equation.

For example the quadratic residues of 31 are:

1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28

And there are 7 pairs: {1,2}, {4,5}, {7,8}, {8,9}, {9,10}, {18,19}, {19, 20}

Why would people care? Curiosity. And it's logical.

For a prime p, the quadratic residue pair count is [(p-1)/4], if p mod 4 = -1, or

(p-5)/4 if p mod 4 = 1.

Here I'm using [] for the floor() function, where for example [10/6] = 1, so just means throw away the remainder.

So with 31, since 31 mod 4 = -1, you have [(31 - 1)/4] = 7

That has been known for some time, but was figured out in some boring way that doesn't interest me as I found my own way!

I use (n-m)² - Dm² = 1, which is just an alternate form of x² - Dy² = 1. And consider it modulo D-1 to get:

2m = n^-1(n² - 1) mod D-1

(n - m)² = m² + 1 mod D-1

That second expression lets you see the quadratic residue pairs being forced! For people who are into numbers it's like this profound thing. Um, I guess it is. Should I try to speak for everyone interested in numbers? Well, for me it was just stunning. It still is. I just like to stare at it.

Notice there is no mention of primeness there as D-1 doesn't have to be prime. So it turns out there may not be solutions for m and n modulo D-1, because there are situations where there are no quadratic residues pairs. The math has to handle those situations of course.

I just LOVE that thing, so came up with a name for it.

Call it a quadratic residue engine.

Coming up with names is an awesome perk of discovery, but it's not intuitive! You need to think long and hard on it to get a style. It really bounces things along a bit. People like it more when you name these things.

Notice it doesn't care if D-1 is prime either, but that makes it easier to solve for the count, while you can use these equations to count in general, which I discussed as a possibility and is an example of something I can do later if get curious enough.

Go over far more including full derivation of count for primes in a post:

somemath.blogspot.com/2011/10/counting-quadratic-residue-pairs.html

What makes this result more interesting is that it is the first time the count is derived versus being deduced. Go out there and find the result from others to see how that was done. Think it was some kind of pigeonhole thing or something.

But I just figure it out directly. To me that's a LOT more satisfying as you can even in this instance literally see the mechanism forcing the existence of quadratic residue pairs and then work out the logic for how this mathematical machinery lets you count them.

Not surprisingly to me, it's one of my most popular results based on search dominance.

It tells you the 'why' and satisfies the urge to know with numbers.


James Harris