Counting quadratic residue pairs

The story of x² - Dy² = 1 revealed yet another twist a few days ago when I realized I could count quadratic residue pairs, with what I call a quadratic residue engine, revealed by using its alternate form (n-m)² - Dm² = 1.

The quadratic residue engine is simple enough:

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

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

And it shows how quadratic residue pairs--which I hadn't thought about until a few days ago--are actually often forced to occur, with the ability also to count them.

That is just amazing for a supposedly well researched equation, as mathematicians tend to call x² - Dy² = 1, Pell's Equation, and then tell you John Pell doesn't deserve that credit, but also they say it is well studied. Clearly they are wrong.

A quadratic residue result is HUGE and is such a giant thing in number theory that there is no way they had a clue that "Pell's Equation" lead to a key result on quadratic residue pairs. And I doubt they'd have kept the wrong attribution if the importance of the equation were well-known.

Now to math, and for those curious about what a quadratic residue pair looks like, here's a list of quadratic residues for 31:

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}

And that count is given by: floor((31 - 1)/4) = 7

In general for odd prime p, the count of quadratic residue pairs is:

floor((p-1)/4), if p mod 4 = -1, or

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

And with the first to remove the floor you can just use (p-3)/4.

Deriving those results is surprisingly easy.

One important initial result is that with

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

if D-1 is prime there is a unique m for each unique {n, n^-1} pair.

Proving it is easy, as consider n and n', such that:

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

Then:

n'*n² - n' = n*n'² - n mod D-1, so

n'*n² - n*n'² = n' - n mod D-1, and:

n'*n(n - n') = n' - n mod D-1, and if n - n' is coprime to D-1 you get finally n'*n = -1 mod D-1, or n' = -n^-1 mod D-1. The coprimeness requirement is fulfilled if D-1 is prime as no difference of residues can equal the modulus.

Now notice that multiplying the modular inverse through with 2m = n^-1(n² - 1) mod D-1, gives:

2m = n - n^-1 mod D-1

So with n', you have 2m = n' - n'^-1 = -n^-1 + n mod D-1

So each n is associated uniquely with m, when D-1 is prime.

Now consider D-1 to be a prime p. Then there are p-1 residues, but n has a unique modular inverse so there are only (p-1)/2 unique m's. But half of those are -m mod D-1, so you again divide by 2 to give approximately (p-1)/4.

But if p mod 4 = 1, it's also possible that m² = -1 mod D-1.

And in that case one is removed, so (p-1)/4 - 1 = (p-5)/4

That one case can be seen with p = 29:

1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28

Which has 6 quadratic residue pairs as required.

Intriguingly the principle can be used to count residue pairs for other than primes, as long as D is not a square. But you wouldn't have the full residue count to start like before because n must be coprime to D-1.

And from the count of available n's two different m's can work with:

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

Then of course m'² = m² mod D-1, requires that D-1 be composite, if m does not equal m' or -m' mod D-1.

(m' - m)(m' + m) = 0 mod D-1

And the m's would factor D-1, and you subtract 1 for each unique pair {m,m'}.

But there is also the possibility with D-1 a composite that m=0 for multiple cases, so you also subtract for each unique n such that n² = 1 mod D-1, except the trivial cases of n=1 or -1 mod D-1, and in that way can get the full count.

So it is an exercise in combinatorics.

It is possible for the count to be 0, for example that is the case for 12, 16 and 24.

Though 24 is not covered by these relations as D cannot be a perfect square for non-trivial integer solutions to the two conics equation.

The reality that x² - Dy² = 1 steps into the realm of controlling quadratic residues in this way is remarkable and really cool.

So now there is this result that has no mention of what I call the two conics equation, which mathematicians call Pell's Equation, showing it has a power beyond what mathematicians realized and increasingly my research is showing it may be one of the most important control equations in number theory.

So it may be one of the most important number theory equations of them all.


James Harris