Thursday, September 22, 2011

Cool rules, renaming Pell's Equation

For those who'd like the executive summary on what controls fundamental integer solutions to x2 - Dy2 = 1, here's a short post that just gives them.

Here are the rules for the fundamental solutions to x2 - Dy2 = 1:

1. If D is prime or twice a prime, solutions will tend to be larger, where the key is those conditions force x = 1 mod D or -1 mod D, and any solution where that is true will tend to be larger.

2. The more small prime factors of D-1, the larger solutions will tend to be.

3. If D is prime or twice a prime, or for any reason x = 1 mod D or -1 mod D, and D-1 has a lot of prime factors, and especially if 4 is a factor then solutions are the largest of all, unless D-1, D+1, D-2, or D+2 is a square, as then solutions will tend to be small regardless, as a sort of release valve kicks in for those special cases.

One cool kind of odd result which really blows up the size is:

If x = 1 mod D, then x+y+(x+Dy-1)/D + 1 must be a square or twice a square.

If x = -1 mod D, then x+y+(x+Dy+1)/D - 1 must be a square or twice a square.

So of course x and y start getting really big as D increases in size to give you that square in there!

An exception though is when D-1, D+1, D-2, or D+2 is a square, as then solutions will tend to be small regardless of other factors.

Those x = 1 mod D or -1 mod D rules follow from a connection to ellipses, and the large impact of that connection can be seen with a famous large case, which is D=61.

17663190492 - 61*2261539802 = 1

x = 1766319049, y = 226153980, and x = 1766319049 = -1 mod 61, so the second applies.

The connection to ellipses when x = -1 mod D is

(D-1)j2 + (j - 1)2 = (x+y)2

with j = (x+Dy+1)/D.

Which gives (x+Dy+1)/D = 255110030.

And it must be true that (x+y +(x+Dy+1)/D - 1) is a square or twice a square:

x+y + (x+Dy+1)/D - 1 = 2247583058, and 2*335232 = 2247583058

60*2551100302 + 2551100292 = 19924730292

So, two things come into play to make the solution so large when D=61, as 61 is prime, which forces, x = 1 mod 61 or x = -1 mod 61, and 60 has a lot of small prime factors as 60 = 4*3*5. Both things coming together makes a very large solution which was unknown as the reason before this research.

To see the full derivation of all the rules just read my article Two Conics Equation Size.

If the "mod" is unfamiliar to you, I have an article where I give a quick course on it: Focus on modular arithmetic

Why do mathematicians call it Pell's Equation and then say John Pell doesn't deserve the attribution? I've gotten tired of that error and now call it, the two conics equation.

Such a fun result with an amazing equation! Took me roughly 3 years to figure it all out with a key result posted on my math blog back in 2008. Of course I have been working on other things as well, so it just kind of percolated in the background until I worked it all out.

James Harris

No comments: