Wednesday, October 19, 2011

Two Conics Equation Modular Solutions

It is weird to try and absorb just how much was missed with x2 - Dy2 = 1, by mathematicians, when it is one of their most famous equations. They call it Pell's Equation, and then say John Pell doesn't deserve that honor, so recently I began calling it the two conics equation.

But even weirder than the name thing, consider a few things they missed.

Turns out you can just solve for modular solutions really easily, by using a different form.

(n-m)2 - Dm2 = 1

So now 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:

n2 - 2mn - 1 = (D-1)m2

which is:

n2 - 2mn - 1 = 0 mod D-1

And I can just solve for m: 2m = n-1(n2 - 1) mod D-1

I've left the 2 on the left-hand side because if D-1 is even, you'd divide it off, while n must be coprime to D-1, which means not share any prime factors, because of the modular inverse.

So you have as a modular solution for x2 - Dy2 = 1 that:

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

Wow, that was easy.

Here's an example, where I know n from working back from a solution for D=38.

With n=6, I have:

2y = 6-1(62 - 1) mod 37 = 31*(36-1) mod 37 = 12 mod 37

So I get y = 6 mod 37, and with this picked example 372 - 38(6)2 = 1.

Of course one problem is it doesn't necessarily give you the smallest non-trivial integer solution, which is called the fundamental solution, but it is still of interest.

Maybe I shouldn't move too quickly from how remarkable the solution is. It is an answer which solves the equation modularly. And it shows a powerful role for the difference between a number and its modular inverse as of course that is also:

2y = n - n-1 mod D-1

That even remarkably has implications for quadratic residues!

So it is a stunning result, with a huge reach across number theory.

So x2 - Dy2 = 1 has an easy and beautifully simple modular solution modulo D-1.

But also that is just very, very strange that it's not part of the known accepted literature, as my research is on the fringe. I'm not an establishment source. And this equation is HUGE in number theory. It's an extremely famous equation for mathematicians. And I've looked up "Pell's Equation" on the web lots of times, gone to link after link after link, and never seen even a clue that you could solve it modularly so easily. Very, very weird.

And this approach works on alternate forms, like:

(n-m)2 - Dm2 = -1

n2 - 2mn + 1 = (D-1)m2

which is: n2 - 2mn + 1 = 0 mod D-1

And I can just solve for m: 2m = n-1(n2 + 1) mod D-1

So easily enough for (n-m)2 - Dm2 = 2, I have: 2m = n-1(n2 - 2) mod D-1

And finally, for (n-m)2 - Dm2 = -2, I have: 2m = n-1(n2 + 2) mod D-1

Those alternate forms if they have solutions actually lead to solutions for the original x2 - Dy2 = 1, but they may not have solutions. For instance each requires a quadratic residue, for instance (n-m)2 - Dm2 = -1, cannot have integer solutions if -1 is not a quadratic residue modulo D.

These results are not just minor curiosities either, as solutions for the alternate forms of the two conics equation tend to be smaller by roughly a square. So answers are approximately the square root of solutions to the original, and if m is less than D-1 for a solution then you get it simply handed to you.

But it gets better. I've proven that what I call a quadratic residue engine leads to a way to count quadratic residue pairs. So this path leads to results on quadratic residues, which is just extraordinary.

So how about the alternates? Here are their corresponding quadratic residue engines:

1. (n-m)2 - Dm2 = -1

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

2. (n-m)2 - Dm2 = 2

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

3. (n-m)2 - Dm2 = -2

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

And each gives quadratic residue results when they have solutions, and I should note that the equations above are valid when fundamental solutions exist, which for instance in all cases excludes D a perfect square. But for the original two conics equation that is the only exclusion, while for the alternates there are others.

So not as powerful as the original, which for instance, gives a way to count quadratic residue pairs for all primes, but still intriguing, as when those equations hold sway they will force quadratic residues to have certain patterns.

The first, of course, just gives quadratic pairs again, but the other two force some quadratic residues to be 2 away from each other, and one wonders how different values impact, as of course I could keep going with alternates, but chose the minimum three necessary to cover the range of solutions to the original two conics equation, as again I'll mention that to solve the original, you can instead solved the alternates. To see me discuss that more you can go to an earlier post.

So the equation x2 - Dy2 = 1 still had quite a few surprises left with elementary results in easy reach, including the ability to just solve the thing modulo D-1, which is just extraordinary.

How were these results missed before? I can only speculate, but maybe with so much history and the tendency of mathematicians to revere the past, along with known methods for solving it, people just didn't keep playing with the thing. But again, I'm only speculating.

But that left some truly beautiful results for me to stumble across and I can only marvel at the oddity of the situation, and consider how lucky I am.

These results presumably should have been found over a hundred years ago.

James Harris
Post a Comment