Saturday, February 12, 2011

Idle Pell's Equation musings

Found myself doing some math clean-up with old results, and there seem to be a few odd things lying around that I'll toss into this post.

Back in 2008 I noticed I could connect x2 - Dy2 = 1, commonly called Pell's Equation by mathematicians, with Pythagorean Triples.

If x2 - Dy2 = 1, and x = 1 mod D, or x = -1 mod D:

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


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

which, of course, gives a Pythagorean triple whenever D-1 is a square.

So I decided recently to try and find what else I could with the result, and one stands out to me for its simplicity, where I use the first relation.

I discovered I needed two new integer variables n and m, where j = 2nm, and substituting gives me:

(D-1)(2nm)2 + (2nm+1)2 = (x+y)2, where 2nm = ((x+Dy)-1)/D

And with some analysis I found that:

(n-m)2 - Dm2 = 1

So I had Pell's Equation back again!

But also 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 ever needing the connection to Pythagorean Triples, or the requirement that x = 1 or -1 mod D.

Though I still think it's a cool connection.

You can actually generalize to (n-mk)2 - Dm2 = 1, to get:

2mk = (n2 - 1)n-1 mod (D-k2)

Here I don't bother splitting up cases as n has to be coprime to D-k2 because it's coprime to n2 - 1, while if 2k has factors in common with D-1 and n2 - 1, you'd just divide those off.

So intriguingly you can use x = n-mk, and y = m, to get residues modulo D-k2 for some solution to Pell's Equation, but the equations don't seem to indicate a way to be sure it's the smallest non-trivial, where trivial one is y=0.

And you already have x2 = 1 mod D, so you can then get x2 mod D(D-k2), when D and D-k2 are coprime, easily enough using the Chinese remainder theorem, or my little congruence result.

But I don't see what good that does you. So for now it's just a curiosity. And that's all I can think of so far, but may edit to put in more to this post later if I think of anything else rather than keep putting up need posts on the same subject.

Oh, looks like you can generalize beyond Pell's Equation to

(n-mk)2 - Dm2 = F, to get:

2mk = (n2 - F)n-1 mod (D-k2)

That looks kind of interesting. Hmmm...just put that out a little bit ago, but thinking about it now I don't see any indication it cares about signs, so:

m(2k) = (n2 - F)n-1 mod (k2 - D)

is the same thing actually, but then it seems a little more obvious that k can be very much larger than D, which is sort of weird?

Can also write as:

m(2k) = (n - Fn-1) mod (k2 - D)

Seems like could be a general route to finding m explicitly, by just using k large enough?

But isn't that too easy? Will toss it up but will think more on it.

I think the problem is in picking n, and I think I've had this result before and eventually didn't think much of it, so will leave it here so that I don't keep re-discovering it over and over again.

James Harris

No comments: