This post will be primarily mathematical and is to show the building of the factorization I often like to use to show a problem with the ring of algebraic integers, where that ring contradicts what you can prove from the field of complex numbers.
The ring is the ring of objects.
See: http://somemath.blogspot.com/2005/03/object-ring.html
I will be using tautological spaces.
The tautological space is an identity. With it I use what I call a conditional, as unlike the identity, it is not always true.
The conditional is x2 + xy + y2 = z2. It was chosen by me for several reasons but for this discussion the primary importance is that it be in the ring of objects, which it is.
The tautological space is x+y+vz = 0(mod x+y+vz).
x+y = -vz (mod x+y+vz), squaring both sides gives: x2 + 2xy + y2 = v2 z2 (mod x+y+vz), subtracting the conditional gives
xy = (v2 - 1)z2 mod (x+y+vz), so (v2 - 1)z2 - xy = 0(mod x+y+vz).
From the tautological space itself: x = -y-vz (mod x+y+vz), so I can substitute to get:
(v2 - 1)z2 + (y+vz)y = 0(mod x+y+vz), so (v2 - 1)z2 + vzy + y2 = 0(mod x+y+vz).
Now let v = -1 + mf, then I have:
(1 - 2mf + m2 f2 - 1)z2 + (-1+mf)zy + y2 = 0(mod x+y+vz)
which is:
(m2 f2 - 2mf )z2 + (mf - 1)zy + y2 = 0(mod x+y+vz)
Now let P(m) = (m2 f2 - 2mf )z2 + (mf - 1)zy + y2.
It's easier to look at it as:
P(m) = y2 + (mf - 1)zy + (m2 f2 - 2mf )z2
My usual example has y = a, m = x, f = 7 and z=1, which is:
P(x) = a2 + (7x - 1)a + (72 x2 - 2(7)x )
And I've shifted the '7' in front of the variable.
Next I derive the actual factorization. Some of what I do is a bit abstruse, but the point is to make sure everything is being done in the object ring without assumptions.
Now multiply both sides by 4, and complete the square:
4P(m) = 4y2 + 4(mf - 1)zy + (mf - 1)2 z2 - (mf - 1)2 z2+ 4(m2 f2 - 2mf )z2
so:
4P(m) = (2y + (mf - 1)z)2 - [ (mf - 1)2 - 4(m2 f2 - 2mf )]z2
Now I need the result that in general x2 - y2 = (x+y)(x-y), which can be constructed from within the tautological space as an intrinsic property:
x+y+vz = x+y+vz, x= -y - vz + (x+y+vz), squaring both sides, gives:
x2 = y2 + 2yvz + v2 z2 - 2(y+vz)(x+y+vz) + (x+y+vz)2
x2 - y2 = 2yvz + v2 z2 - 2(y+vz)(x+y+vz) + (x+y+vz)2, and setting v = 0, I have:
x2 - y2 = - 2y(x+y) + (x+y)2, which is: x2 - y2 = (x+y)(-2y + x +y),
so: x2 - y2 = (x+y)(x-y).
4P(m) = (2y + (mf - 1)z)2 + [(mf - 1)2 - 4(m2 f2 - 2mf )]z2
4P(m) = (2y + (mf - 1)z + sqrt[(mf - 1)2 - 4(m2 f2 - 2mf )]z)(2y + (mf - 1)z - sqrt[(mf - 1)2 - 4(m2 f2 - 2mf )]z)
and now I can flip things around so that z is first in each factor and divide the 4 back off:
P(m) = (((mf - 1) + sqrt[(mf - 1)2 - 4(m2 f2 - 2mf )]z/2 + y)(((mf - 1) - sqrt[(mf - 1)2 - 4(m2 f2 - 2mf )]z/2 + y)
and I have a1(m) = ((mf - 1) + sqrt[(mf - 1)2 - 4(m2 f2 - 2mf )]/2, and
a2(m) = ((mf - 1) - sqrt[(mf - 1)2 - 4(m2 f2 - 2mf )]/2
where P(m) = (a1(m)z + y)(a2(m)z + y).
Note that with y = uf, P(m) has a factor of f.
And that's a complete derivation from conditional all the way through, doing everything in the object ring.
The reason that derivation comes up as an issue is that one objection some people raise is that you can show another contradiction by breaking the construction, for instance with something like:
a2 - (x-1)a + (49x2 - 14x) = 0
where they just break the original factorization by deleting off a key 7, so that x=1, will zero out the 'a' coefficient.
With what's shown above that's equivalent to just changing:
P(m) = y2 + (mf - 1)zy + (m2 f2 - 2mf )z2
into:
P(m) = y2 + (m - 1)zy + (m2 f2 - 2mf )z2
But that is NOT constructible in the object ring. So it's like just changing something with a derived equation.
This post goes through some of the underlying machinery in order to show a full construction within the object ring, primarily to handle that type of objection.
Also I think it's just way cool.
Figuring out details like the above helped me gain confidence in something I introduced, as I discovered tautological spaces. So I don't have the guide of a lot of history, but had to feel my way mostly on my own.
James Harris
Wednesday, September 28, 2011
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
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
Tuesday, September 20, 2011
Two Conics Equation Size
A few years ago back in 2008, I decided to use mathematical tools I discovered that I call tautological spaces against binary quadratic Diophantine equations. One of my early results showed how to connect x2 - Dy2 = 1, which I call the two conics equation, to Pythagorean Triples, and I got that result from a mistake!
Key to my ability to connect the two conics equation to ellipses is a relation that is found by using my method for generally reducing binary quadratic Diophantine equations on the equation:
x2 - Dy2 = F
That gives:
(x+Dy)2 - D(x+y)2 = -F(D-1)
With the two conics equation F=1, so I have:
(x+Dy)2 - D(x+y)2 = -(D-1)
Years ago, when I had an early version of the above I had the variable S, for a piece I didn't know at that time, which is x+Dy. In that post, which I've corrected mathematically, I also am still using the phrase "Pell's Equation" which I did for years before recently shifting to calling it the two conics equation.
Shifting things around a bit, I have:
(x+Dy)2 + (D-1) = D(x+y)2
And I can group to divide off D, so doing so and dividing it off:
[(x+Dy)2 - 1]/D + 1 = (x+y)2
At this point I made a little mistake years ago, as I wrongly thought that x+Dy = 1 mod D or x+Dy = -1 mod D followed, but that is only definite if D is prime. But it leads to a really cool result, allowing us to connect to ellipses, so now we'll shift to the special case of x = 1 mod D or x = - 1 mod D.
And with that assumption I'll use x+Dy = jD +/- 1, where j is some unknown integer, and one of those cases will be true. That usage is a little confusing, but I did it to keep from having to write x+Dy = jD + 1 or x+Dy = jD - 1, over and over again.
And making that substitution gives:
[(jD +/- 1)2 - 1]/D + 1 = (x+y)2
And squaring and simplifying a bit gives:
Dj2 +/- 2j + 1 = (x+y)2
So now I just subtract and add j2 so that I can complete the square to get:
(D-1)j2 + (j +/- 1)2 = (x+y)2
And I've successfully connected to ellipses!
Of course if D-1 is a square you are connected to Pythagorean Triples. Here is an example I've used for years.
With D=2, using x=17, y=12, as 172 - 2(12)2 = 1, I find:
j = ((17+2*12)-1)/2 = 20 is a solution giving:
202 + 212 = 292
The +/- usage can be a bit confusing so more recently I've not used it, so the full result without it is:
(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
where the first follows if x = 1 mod D, or the second if x = -1 mod D.
Interestingly, of course, that is fulfilled if D is prime, so the result says that ellipses directly connect to the two conics equation, when D is prime.
From that result I did deeper analysis to find out that the prime factors of D-1 control the size of fundamental solutions to x2 - Dy2 = 1, which is an answer that appears to apply in general, even when x = 1 mod D or x = - 1 mod D is not the case!
So what happened was that in studying my connection I found I got the equation:
(n-m)2 - Dm2 = 1
So that analysis gave me my main equation back again, but with the variables shifted in this special way, which is kind of cool.
I noticed that I could solve for the residue of m mod D-1, where that split by whether or not D-1 was even, where for the odd D-1:
m = (n2 - 1)(2n)-1 mod (D-1)
While for the even D-1:
m = ((n2 - 1)/2)n-1 mod (D-1)
And I realized that I could have had those results just from considering
(n-m)2 - Dm2 = 1
without needing the connection to ellipses, or that x = 1 or -1 mod D.
And it is easy to figure out that n = x+y or n = x-y, and the modular inverse requires that n be coprime to D-1, or (D-1)/2 for the even D-1 case, so a lot of small prime factors still provides a harder case, as n is being more and more constrained.
However, if x = 1 mod D or x = -1 mod D is not true, then the impact I think is less, as intriguingly enough if it is true then you also get the requirement that x+y+j+1 or x+y+j-1 must be a square or twice a square.
To see that result only requires a little bit more analysis, where I start with:
(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.
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.
So when D is a prime, and D-1 has a lot of small prime factors, the mathematics has to fulfill a special requirement, which also connects it to ellipses, which I just mention again as I think it is really cool.
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.
There trivially easy solutions to x2 - Dy2 = 1 exist, which I found by exploring the connection even further, where I found I needed to split j up into two more variables:
j = nm or j = 2nm
The gave me a control set of relations when D-1 is odd, where at least one will work:
1. n = m +/- sqrt(Dm2 + 2), m = (n2 - 2)(2n)-1 mod (D-1)
2. n = m +/- sqrt(Dm2 + 1), m = (n2 - 1)(2n)-1 mod (D-1)
3. n = m +/- sqrt(Dm2 - 2), m = (n2 + 2)(2n)-1 mod (D-1)
4. n = m +/- sqrt(Dm2 - 1), m = (n2 + 1)(2n)-1 mod (D-1)
and, when D-1 is even:
1. n = m +/- sqrt(Dm2 + 2), m = ((n2 - 2)/2)n-1 mod ((D-1)/2)
2. n = m +/- sqrt(Dm2 + 1), m = ((n2 - 1)/2)n-1 mod ((D-1)/2)
3. n = m +/- sqrt(Dm2 - 2), m = ((n2 + 2)/2)n-1 mod ((D-1)/2)
4. n = m +/- sqrt(Dm2 - 1), m = ((n2 + 1)/2)n-1 mod ((D-1)/2)
You can see the trivial solutions at D-1, a square, when Pell's Equation connects directly to Pythagorean triples, and also at D+1, D-2, and D+2 perfect squares. With those the square root is trivial to resolve with m=1, so it's like a release valve. There are also corresponding identities that give solutions trivially. For instance the D+1 trivial case is given by: n2 - (n2 - 1)(1)2 = 1
In wondering why I made a mistake back in 2008 that was equivalent to assuming that x = 1 mod D or x = -1 mod D, I'm not sure, but might have been in a hurry, or just not thinking carefully. I had just done a lot of the analysis and was anxious to find something useful with my Quadratic Diophantine Theorem. Or in the back of my mind I may have been assuming D was prime. The D=61 case is a famously large case and there of course D is prime.
Then I wandered off and did other things. Only recently have I completely re-visited the result and last night noticed the mistake.
Oh, it is of interest I think to test the additional constraints with the results above for the D=61 case, as it is so famous.
17663190492 - 61*2261539802 = 1
x = 1766319049, y = 226153980, and x = 1766319049 = -1 mod 61, so the second equations apply.
(D-1)j2 + (j - 1)2 = (x+y)2, j = (x+Dy+1)/D
Which gives j = 255110030, and it must be true that (x+y + j-1) is a square or twice a square:
(x+y + j-1) = 2247583058, and 2*335232 = 2247583058.
Of course 33523 is coprime to D-1, which is 60, and 33523 = 7*4789, so it looks like the math went to the next smallest prime available which was 7, since 2, 3 and 5 were blocked.
60*2551100302 + 2551100292 = 19924730292
Often a mistake can crash an argument but in this case it didn't matter much as it still lead to the correct result that D-1 and its prime factors are key, where the effect is simply much larger if D is prime, or if x = 1 mod D, or x = -1 mod D, which can occur even when it is not. Like when D is twice a prime it is forced as well, so those solutions also are much bigger. Fascinating.
Such a cool story. The connections are amazing. It's like all these equations are like a family, and prime numbers are important to the story too!
James Harris
Key to my ability to connect the two conics equation to ellipses is a relation that is found by using my method for generally reducing binary quadratic Diophantine equations on the equation:
x2 - Dy2 = F
That gives:
(x+Dy)2 - D(x+y)2 = -F(D-1)
With the two conics equation F=1, so I have:
(x+Dy)2 - D(x+y)2 = -(D-1)
Years ago, when I had an early version of the above I had the variable S, for a piece I didn't know at that time, which is x+Dy. In that post, which I've corrected mathematically, I also am still using the phrase "Pell's Equation" which I did for years before recently shifting to calling it the two conics equation.
Shifting things around a bit, I have:
(x+Dy)2 + (D-1) = D(x+y)2
And I can group to divide off D, so doing so and dividing it off:
[(x+Dy)2 - 1]/D + 1 = (x+y)2
At this point I made a little mistake years ago, as I wrongly thought that x+Dy = 1 mod D or x+Dy = -1 mod D followed, but that is only definite if D is prime. But it leads to a really cool result, allowing us to connect to ellipses, so now we'll shift to the special case of x = 1 mod D or x = - 1 mod D.
And with that assumption I'll use x+Dy = jD +/- 1, where j is some unknown integer, and one of those cases will be true. That usage is a little confusing, but I did it to keep from having to write x+Dy = jD + 1 or x+Dy = jD - 1, over and over again.
And making that substitution gives:
[(jD +/- 1)2 - 1]/D + 1 = (x+y)2
And squaring and simplifying a bit gives:
Dj2 +/- 2j + 1 = (x+y)2
So now I just subtract and add j2 so that I can complete the square to get:
(D-1)j2 + (j +/- 1)2 = (x+y)2
And I've successfully connected to ellipses!
Of course if D-1 is a square you are connected to Pythagorean Triples. Here is an example I've used for years.
With D=2, using x=17, y=12, as 172 - 2(12)2 = 1, I find:
j = ((17+2*12)-1)/2 = 20 is a solution giving:
202 + 212 = 292
The +/- usage can be a bit confusing so more recently I've not used it, so the full result without it is:
(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
where the first follows if x = 1 mod D, or the second if x = -1 mod D.
Interestingly, of course, that is fulfilled if D is prime, so the result says that ellipses directly connect to the two conics equation, when D is prime.
From that result I did deeper analysis to find out that the prime factors of D-1 control the size of fundamental solutions to x2 - Dy2 = 1, which is an answer that appears to apply in general, even when x = 1 mod D or x = - 1 mod D is not the case!
So what happened was that in studying my connection I found I got the equation:
(n-m)2 - Dm2 = 1
So that analysis gave me my main equation back again, but with the variables shifted in this special way, which is kind of cool.
I noticed that I could solve for the residue of m mod D-1, where that split by whether or not D-1 was even, where for the odd D-1:
m = (n2 - 1)(2n)-1 mod (D-1)
While for the even D-1:
m = ((n2 - 1)/2)n-1 mod (D-1)
And I realized that I could have had those results just from considering
(n-m)2 - Dm2 = 1
without needing the connection to ellipses, or that x = 1 or -1 mod D.
And it is easy to figure out that n = x+y or n = x-y, and the modular inverse requires that n be coprime to D-1, or (D-1)/2 for the even D-1 case, so a lot of small prime factors still provides a harder case, as n is being more and more constrained.
However, if x = 1 mod D or x = -1 mod D is not true, then the impact I think is less, as intriguingly enough if it is true then you also get the requirement that x+y+j+1 or x+y+j-1 must be a square or twice a square.
To see that result only requires a little bit more analysis, where I start with:
(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.
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.
So when D is a prime, and D-1 has a lot of small prime factors, the mathematics has to fulfill a special requirement, which also connects it to ellipses, which I just mention again as I think it is really cool.
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.
There trivially easy solutions to x2 - Dy2 = 1 exist, which I found by exploring the connection even further, where I found I needed to split j up into two more variables:
j = nm or j = 2nm
The gave me a control set of relations when D-1 is odd, where at least one will work:
1. n = m +/- sqrt(Dm2 + 2), m = (n2 - 2)(2n)-1 mod (D-1)
2. n = m +/- sqrt(Dm2 + 1), m = (n2 - 1)(2n)-1 mod (D-1)
3. n = m +/- sqrt(Dm2 - 2), m = (n2 + 2)(2n)-1 mod (D-1)
4. n = m +/- sqrt(Dm2 - 1), m = (n2 + 1)(2n)-1 mod (D-1)
and, when D-1 is even:
1. n = m +/- sqrt(Dm2 + 2), m = ((n2 - 2)/2)n-1 mod ((D-1)/2)
2. n = m +/- sqrt(Dm2 + 1), m = ((n2 - 1)/2)n-1 mod ((D-1)/2)
3. n = m +/- sqrt(Dm2 - 2), m = ((n2 + 2)/2)n-1 mod ((D-1)/2)
4. n = m +/- sqrt(Dm2 - 1), m = ((n2 + 1)/2)n-1 mod ((D-1)/2)
You can see the trivial solutions at D-1, a square, when Pell's Equation connects directly to Pythagorean triples, and also at D+1, D-2, and D+2 perfect squares. With those the square root is trivial to resolve with m=1, so it's like a release valve. There are also corresponding identities that give solutions trivially. For instance the D+1 trivial case is given by: n2 - (n2 - 1)(1)2 = 1
In wondering why I made a mistake back in 2008 that was equivalent to assuming that x = 1 mod D or x = -1 mod D, I'm not sure, but might have been in a hurry, or just not thinking carefully. I had just done a lot of the analysis and was anxious to find something useful with my Quadratic Diophantine Theorem. Or in the back of my mind I may have been assuming D was prime. The D=61 case is a famously large case and there of course D is prime.
Then I wandered off and did other things. Only recently have I completely re-visited the result and last night noticed the mistake.
Oh, it is of interest I think to test the additional constraints with the results above for the D=61 case, as it is so famous.
17663190492 - 61*2261539802 = 1
x = 1766319049, y = 226153980, and x = 1766319049 = -1 mod 61, so the second equations apply.
(D-1)j2 + (j - 1)2 = (x+y)2, j = (x+Dy+1)/D
Which gives j = 255110030, and it must be true that (x+y + j-1) is a square or twice a square:
(x+y + j-1) = 2247583058, and 2*335232 = 2247583058.
Of course 33523 is coprime to D-1, which is 60, and 33523 = 7*4789, so it looks like the math went to the next smallest prime available which was 7, since 2, 3 and 5 were blocked.
60*2551100302 + 2551100292 = 19924730292
Often a mistake can crash an argument but in this case it didn't matter much as it still lead to the correct result that D-1 and its prime factors are key, where the effect is simply much larger if D is prime, or if x = 1 mod D, or x = -1 mod D, which can occur even when it is not. Like when D is twice a prime it is forced as well, so those solutions also are much bigger. Fascinating.
Such a cool story. The connections are amazing. It's like all these equations are like a family, and prime numbers are important to the story too!
James Harris
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
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
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
Subscribe to:
Posts (Atom)