When derivation is surprisingly easy

One of my favorite and more popular results is a derivation of the already known way to count things called quadratic residue pairs, but with a derivation can go beyond what was known before it.

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

Deriving that is easy, and fun!

Turns out MAYBE though I took a slightly long route as you can look at:

x² - Dy² = 1

Which I like to call a two conics equation as it gives hyperbolas or ellipses depending on the sign of D, and look at it modulo D-1:

x² - y² = 1 mod D-1, so:

x² = y² + 1 mod D-1

And you can notice easily enough that a quadratic pair can be there though the full set of rules for when it is, are not obvious there. Like for D-1 = 12, there are none. So how does the math do that? I think y always has prime factors of 12 or something, and um, it isn't very simple. Check out my post linked above for the derivation where I explain a LOT, as just sitting here now am like, it's not THAT simple.

If you can, you might want to try yourself! See if you can derive a quadratic residue pair count from here, or even more fun, find a derivation out there in the wild. That's kind of a trick thing to put though as I found the first, and to my knowledge only derivation. Do some research to see how the result was found before which if I remember correctly involved something called the pigeonhole principle.

Oh yeah, so I used "mod" so much I quit using a congruence symbol years ago, and don't think I lost anything. Also for those who'd like a primer for me on the subject, wrote one in a blog post years ago:

Focus on modular arithmetic

I really think modular is one of the coolest things ever, and of course can show up beyond mathematics. In mathematics though modular concepts lead to astonishing simplifications. I like to say, modular algebra gives a handle on infinity.


James Harris