Translate

Sunday, November 27, 2011

A Math Mystery Resolved

The equation x2 - Dy2 = 1 has one of the weirdest stories in mathematics, with a convoluted history that goes back thousands of years, and the story just keeps getting stranger.

I like to call it the two conics equation because in rationals it gives you hyperbolas or ellipses depending on the sign of D, while mathematicians like to consider it only with integers and call it Pell's Equation, but then say that John Pell doesn't deserve that credit.


But they also seem to fail to mention that there was a mystery in the relation between D and the size of the fundamental solution, which is the first non-zero integer solution.  And that's kind of a BIG DEAL as without that explanation the equation can seem to be a little crazy.


For instance, with D=2, it's nice and sweet with a nice and easy fundamental solution:  32 - 2(2)2 = 1

And it's hard to see easier than that!  Though you often do see other solutions that are easy.  And lots of them.

But then you have ones that are hard where the fundamental solution is huge, where the most famous one because Fermat used it as a challenge problem--yeah, this equation is old and was even old when he played with it--is for the D=61 case.

17663190492 - 61(226153980)2 = 1

But is immediately followed by an easy one: 632 - 62(8)2 = 1

But why?  Some may know that if D+2 is a square you get easy solutions from an identity, but I can go a little further to D=72, and you get the easy:  172 - 72(2)2 = 1

Now that's just damn strange.

And if you wish you can go to a page on MathWorld where they conveniently list the solutions for D to 102--go down to the bottom half of the page to see them.  They skip squares as D can't be a square, since (x - sqrt(D)y)(x + sqrt(D)y) = 1.

If you see a pattern there, then you should congratulate yourself, as then you figured out the rules!

And here they are solving an ancient math mystery:

1. If D is prime or twice a prime, solutions will tend to be larger, where that is because x = 1 mod D or -1 mod D, for those cases.

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 other 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.

So if you figured that out then you managed to see something that I managed to prove September, when I finally got them right as for a while I missed the x = 1 mod D or -1 mod D thing for reasons that still escape me.  

So now you know what Fermat didn't know, and if he had known then he'd have invented modular arithmetic, which he could have done, but history says he didn't and modular arithmetic didn't emerge fully until the 1800's and Gauss had a lot to do with that emergence.

Such a cool story.  I love mentioning those names.

So today we're in the 21st century and those rules are backed by a really cool proof, which isn't very formal now as you can say, it's still at first draft as I just figured everything out.  Polishing up math proofs takes time, and motivation.  For now I'd like to get some attention to the result!  Then can make it all pretty.

And it should be easy to get attention here.  Math people didn't even realize there was a mystery, apparently mostly deciding that what they call Pell's Equation was just crazy, and it bounced around with D for no particular reason at all!  Since they call it Pell's Equation and then say John Pell doesn't deserve credit, maybe they just think crazy goes with the thing.


James Harris

Saturday, November 05, 2011

Generalizing quadratic Diophantine

Using an alternate form from x2 - Dy2 = F, I can generalize as follows.

(z-ky)2 - Dy2 = F

Expand out:

z2 - 2kyz + k2y2 - Dy2 = F

Now obviously, it makes sense to group the y2, and see:

z2 - 2kyz - (D-k2)y2 = F, which is also z2 - 2kyz - F = (D-k2)y2, which requires that 2kyz + F = -1 or 1 mod 8, or 0 mod 4.

And now for what is an amazing trick, which only arrived with modular arithmetic, as before, to mathematicians who did not have it, the above would be pointless.

They literally could not see what happens next:

z2 - 2kyz = F mod D-k2

And now you can move that F to the left hand side:

z2 - 2kyz - F = 0 mod D-k2

And solve for y, to find:

2y = (kz)-1(z2 - F) mod D-k2

which is also:

2y = k-1(z - Fz-1) mod D-k2

Turns out that I need one more equation.

Going back to: (z-ky)2 - Dy2 = F

Let's add k2y2 to both sides: (z-ky)2 + k2y2 - Dy2 = k2y2 + F

and now again focusing mod D-k2, I have:

(z-ky)2 = k2y2 + F mod D-k2

And I have what I like to call a quadratic residue engine, which then is as follows.

Given (z-ky)2 - Dy2 = F, if integer solutions for a chosen k exist, it must be true that:

2y = k-1(z - Fz-1) mod D-k2

(z-ky)2 = k2y2 + F mod D-k2

where 2kyz + F = -1 or 1 mod 8, or 0 mod 4, if D-k2 is a square.

Giving solutions for: x2 - Dy2 = F mod D-k2


James Harris

Thursday, November 03, 2011

A Neat Trick

The idea that modern advances in knowledge can greatly enhance and simplify is potent in just about every field of human endeavor and is fun for the amateur math researcher, where I can use a neat trick only available with modular arithmetic.

Consider x2 - Dy2 = 1, where mathematicians like to study it as a Diophantine equation, which means you try to find integer solutions, and in its case you look for nonzero ones instead of the trivial case where y=0. Nonzero integer solutions are called the fundamental solution and the equation is called Pell's Equation, in honor of John Pell, though oddly enough mathematicians also say he doesn't deserve it.

People have studied the equation for thousands of years, but modular arithmetic has been around for a lot shorter time, so a nifty solution was not possible until the time of Gauss, where I will shift its form to use a neat trick:

(z-y)2 - Dy2 = 1

Expand out:

z2 - 2yz + y2 - Dy2 = 1

Now obviously, it makes sense to group the y2, and see:

z2 - 2yz - (D-1)y2 = 1

And I've talked about this before in other posts, but zipped past what is an amazing trick, which only arrived with modular arithmetic, as before, to mathematicians who did not have it, the above would be pointless.

They literally could not see what happens next:

z2 - 2yz = 1 mod D-1

And now you can move that 1 to the left hand side: z2 - 2yz - 1 = 0 mod D-1

And solve for y, to find:

2y = z-1(z2 - 1) mod D-1

Without a way to solve for y modularly--as it hadn't been invented yet--previous math people found various clever ways to get solutions. And if you read about "Pell's Equation" on the web you can get a lot of history lessons on what they did, while I just solved it modularly, very quickly.

Now a modular solution is not necessarily an explicit answer, but the technique given can be generalized, with another variable, I'll call k:

(z-ky)2 - Dy2 = 1

Which gives from the same steps above:

2y = (kz)-1(z2 - 1) mod D-k2

which can also be written as:

2y = k-1(z - z-1) mod D-k2

where you also get an added rule, as z2 - 2kyz - 1 = (D-k2)y2, shows that D-k2 cannot be a square, if k is even.

Notice that k and z are forced to be coprime to D-k2 so that the modular inverses exist.

Turns out that I need one more equation.

Going back to: (z-ky)2 - Dy2 = 1

Let's add k2y2 to both sides: (z-ky)2 + k2y2 - Dy2 = k2y2 + 1

and now again focusing mod D-k2, I have:

(z-ky)2 = k2y2 + 1 mod D-k2

And I have what I like to call a quadratic residue engine, which then is as follows.

Given (z-ky)2 - Dy2 = 1, it must be true that:

2y = k-1(z - z-1) mod D-k2

(z-ky)2 = k2y2 + 1 mod D-k2

when if k is even, D-k2 is not a square.

Now you can get as many modular solutions for y as you want, and use them to get answers for y with something called the Chinese remainder theorem.

While I will not work it all the way through, it may help to get a sense of how it might work with a famous large case, which is D=61, which I looked up on the web to find that x = 1766319049, y = 226153980.

17663190492 - 61*2261539802 = 1

Let's start with k=1, and notice that 2y = (z - z-1) mod 60, requires that z be coprime to 60 so that its modular inverse exists, which means that z can only be: 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, or 59.

But the second equation show things are even simpler than that might indicate:

(z-y)2 = y2 + 1 mod 60, which requires that y=0 mod 60 or you need a quadratic residue that when 1 is added to it, is STILL a quadratic residue, which is called a quadratic residue pair, of which there is only one modulo 60, as here are all the quadratic residues modulo 60:

1, 4, 9, 16, 21, 24, 25, 36, 40, 45, 49

So we know that y2 = 0 mod 60 or y2 = 24 mod 60, so despite having 14 possible z's, there are only a few possible answers for y. And since we have the fundamental answer it's easy enough to see that 30 is in fact a factor of 226153980.

The curious might wonder with 2y = (z - z-1) mod 60, with all the possible z's, how many cases for y=0 come up.

Those cases for z are: 11, 19, 29, 31, 41, 49, 59, where for all those y2 = 0 mod 60.

(Intriguingly, for all the other cases the modular inverse of z is a prime number, which I'm not sure is significant.)

So you could have two possibilities for y mod 60, since for y2 = 24 mod 60, you'd only need one answer, and then can go on to other values by shifting k. But notice that 2 and 3 are definitely factors of y. So fewer possibilities with, k=2, as then you're modulo 57, where you know that 3 has to be a factor of y. And the quadratic residues modulo 57 are:

1, 4, 6, 7, 9, 16, 19, 24, 25, 28, 30, 36, 39, 42, 43, 45, 49, 54, 55

And each possible y is indeed forced to have 3 as a factor.

At k=3, you have modulo 52, which has for quadratic residues:

1, 4, 9, 12, 13, 16, 17, 25, 29, 36, 40, 48, 49

And at k=4, you are modulo 45, which has for quadratic residues:

1, 4, 9, 10, 16, 19, 25, 31, 34, 36, 40

That again shows 3 is a factor and gives 5 a choice, as y2 = 0 mod 45 is possible.

It is of interest that the k=6 case is blocked because k is even and 61 - 36 = 25, which is a square. That case has no quadratic residue pairs and if not blocked would falsely indicate that 5 must be a factor of y.

And still a long ways away from getting the actual answer for y, which is HUGE, but intriguingly enough, there is a short-cut, which in this case is to use m2 - 61n2 = -1, which has a solution here, as all the tricks above work with it, though the equations shift a bit.

It gives a solution to "Pell's Equation" from: x = 2m2 + 1.

For instance,

297182 - 61*38052 = -1, so m = 29718, gives

x = 1766319049, from x = 2m2 + 1

Notice the k=6 case is valid here as the rule that D-k2 cannot be a square if k is even doesn't apply and 5 gets forced as a factor. The curious reader can see how things shift for the other factors. I looked the answer up here as well, but 3805 is a lot more accessible so probably could have calculated that if I were interested in the effort.

With D a prime, if m2 - Dn2 = -1 doesn't have solutions then the other alternate equations m2 - Dn2 = -2 or m2 - Dn2 = 2, will, where again their answers are much smaller.

Lots of fun things then thanks to the advance called modular arithmetic, which allows you to just solve for y modularly, where without it, things are not so easy.

And possibly new ways to approach getting explicit answers where I just glanced at the surface of what is to me a less interesting issue, as people have ways of getting those now using other techniques.


James Harris