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
or
(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:
Post a Comment