Quadratic Residue Engine

For me it is fascinating continuing to play with x² - Dy² = 1, which has revealed wonderful secrets like the rules governing the fundamental solution, which is what mathematicians call the smallest positive non-trivial integer solution, where the trivial integer solution of course is when y=0.

Mathematicians call x² - Dy² = 1, Pell's Equation, and then usually tell you John Pell doesn't deserve credit, which is weird, but weirder is how little they appear to know about awesome things with regard to it, like in this post I want to show this quadratic residue engine that I finally noticed this morning just a few minutes ago. (Hot, hot research result.)

Turns out that the usual way of displaying it isn't most effective as consider instead:

(n-m)² - Dm² = 1

Just a little change and of course m = y or m = -y from the original, but then n = x+y or n = x-y.

From that format we can now focus on D-1:

n² - 2mn - 1 = (D-1)m²

which is:

n² - 2mn - 1 = 0 mod D-1

So now I can actually solve for m or n to get two equations which are the quadratic residue engine:

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

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

And I haven't tried it yet, so here is the moment of truth. Why type up a post before I even do a single numerical example to be sure? I don't know. Seems obvious enough, and if it doesn't work then I just won't put the post up. But enough talking to myself! Let's try a number.

So let D=12, as I want to see mod 11. And let n=2, as that is the first one that will work.

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)² = 9² + 1 mod 11

which is:

7² = 5 mod 11

Which is correct so the equations work and we solved a quadratic residue!

But D-1 prime is boring, as the real question is, what happens if it is a composite? So let's use D=22, so D-1 = 21, and again use n=2:

2m = 2^-1(3) mod 21 = 11(3) mod 21, and m = 6

(2 - 6)² = 6² + 1 mod 21

which is: 4² = 16 mod 21

And that's not remarkable or informative, but let's keep going. Notice that n=3 is blocked because it's not coprime to 21, so the modular inverse doesn't exist. Maybe the math figures we must know it's a factor as something interesting happens at n=4.

2m = 4^-1(15) mod 21 = 16(15) mod 21, and m = 15

(4 - 15)² = 15² + 1 mod 21

which is: 11² = 16 mod 21

Which tells us that 11² = 4² = 16 mod 21, and 11-4 = 7, and 11+4 = 15, which means we can factor 21 with the result.

The math didn't care. It gave either quadratic residue answer.

Of course those are toy examples which I'm doing now as I type up this post. I have no idea if there are any additional constraints that may kick in to limit the efficacy of this result with larger numbers.

But it is remarkable that such a simple little quadratic residue engine was buried in a well-known equation.


James Harris