Monday, September 19, 2011

Was an unsolved problem

When I found the answer to why some fundamental solutions for x2 - Dy2 = 1, which are the smallest integer solutions with y not equal to 0, were much larger than others, I wasn't sure if it was an unsolved problem before my answer, but now I'm sure it was.

Before I had done a lot of web searches on "Pell's Equation" which is what mathematicians commonly call the equation, even though they also say that John Pell doesn't deserve that credit, and I didn't see the issue raised.

But it occurred to me recently to do the search on: Pell's Equation size

That DID bring up links discussing the question including some attempts at getting an answer, so now I know it was an unsolved problem.

My own solution came from connecting the equation which I like to call the two conics equation rather than Pell's Equation, to ellipses. Oh, I do have a lot of posts that have "Pell's Equation" used as I followed the conventional usage until recently.

So I found the following connection to ellipses, which is valid when x = 1 mod D or x = -1 mod D:

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


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

For instance with D=2, using x=17, y=12, as 172 - 2(12)2 = 1, I find the first one works:

j = ((17+2*12)-1)/2 = 20 is a solution giving:

202 + 212 = 292

Now it is remarkably easy to show why prime factors of D-1 solve the problem of the size of the fundamental solution.

With the first relation

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

note that:

(j+1)2 - (x+y)2 = 0 mod D-1

Now consider any prime factor p of D-1, then of course it also follows that:

(j+1)2 - (x+y)2 = 0 mod p

But now consider j = ((x+Dy)-1)/D, and since D-1 = 0 mod p, I have j = x+y-1 mod p, which remarkably forces all prime factors of D-1 into: (j+1 -(x+y))

Going back to my original full expression:

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

that of course is:

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

From x2 - Dy2 = 1 itself I have x2 - y2 = 1 mod p, so x+y must be coprime to D-1.

And knowing that D-1 is a factor of (x+y - (j+1)), it must be coprime to (x+y + j+1) for all its primes except 2.

Also then (x+y + j+1) is forced to be a perfect square or twice a perfect square.

If D-1 is prime, then (x+y + j+1) is only limited to not having that one prime as a factor, which is the easiest situation for the math, so fundamental solutions are at their smallest.

But if D-1 has a lot of small prime factors, then x+y+j+1 is forced to be coprime to each of them, except maybe 2, but even then it cannot have 4 as a factor. So the mathematics must look for solutions with more constraints on what is allowed, and still get a square or twice a square with (x+y + j+1).

Doing the above analysis with

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

merely shifts to D-1 a factor of (x+y - (j-1)), and (x+y + j-1) coprime to it for all odd factors.

The result then is that D-1 is the control, and its prime factors are what matters, which then was the previously unknown result. And the validity of that focus applies beyond the special case of x = 1 mod D or x = -1 mod D. And it is really actually cool that connecting to ellipses helps give the answer.

Now consider what you can easily see when the focus is on D-1.

I'll show five solutions where D-1 is prime in a row, and start with D = 24, which means 23, 29, 31, 37 and 41 being the primes, D will be 24, 30, 32, 38 and 42. Here are the solutions:

52 - 24(1)2 = 1,

112 - 30(2)2 = 1,

172 - 32(3)2 = 1,

372 - 38(6)2 = 1,

132 - 42(2)2 = 1

Notice relatively small solutions. Now see what happens when D-1 is divisible by 4, and has other prime factors. So values for D are close to the previous set, I'll start with 24, which gives me D-1 being 28, 32, 36, 40, 44, which means that D will be 29, 33, 37, 41, 45:

98012 - 29(1820)2 = 1,

232 - 33(4)2 = 1,

732 - 37(12)2 = 1,

20492 - 41(320)2 = 1,

1612 - 45(24)2 = 1

The mathematics is having to work harder now, as it deals with the additional constraints forced by the prime factors of D-1.

Given this information people looking for fundamental solutions to x2 - Dy2 = 1 can know when to expect very large ones, or when the solutions are more likely to be smaller.

The previously unsolved problem has been resolved.

James Harris

No comments: