Sunday, August 19, 2012

My math comfort

For years I've realized I find comfort in the solidity of mathematics and turn to it when the world seems screwy, or I'm under a lot of pressure. Then I kind of reflexively find myself musing on some result and I feel better, as math can give you that certainty that can be missing in an often arbitrary world.

And recently I've found myself turning often to the equation x2 - Dy2 = 1. I've found quite a few things about it, and lots of results about it that I enjoy. Here I'll talk about one of the latest.

Back in June of this year I noticed a way to solve for x and y mod p, where p is a prime for which D is a quadratic residue, so there exists n such that: n2 = D mod p

Then where r is any residue modulo p:

2x = r + r-1 mod p and 2y = n-1(r - r-1) mod p

Which gives solutions for x2 - Dy2 = 1 mod p.

So you don't necessarily get an explicit answer to the original equation, but you can use any prime p you want as long as D is a quadratic residue. You can easily move to composite N versus prime p, but I find it simpler to just focus on primes for just playing around, so for instance I know the modular inverse will exist.

And you can find p as big as you want.

Now let's plug in some numbers! For me with number theory it's so cool when you watch the numbers follow the rules. Perfectly. They do it with absolute perfection.

Here I'll use D=23, and I just checked and it's a quadratic residue of 101, which I picked arbitrarily. So let p=101. Then n = 15 is a solution, as 152 = 23 mod 101.

And I need its modular inverse and 15-1 = 27 mod 101.

And I can use whatever residue I want for r, where I note I don't consider 0 a residue, and 1 would be boring I'm sure, and 2 might be ok, but I'll just use r = 3, because that might be more interesting.

And I need its modular inverse and 3-1 = 34 mod 101.

So now I can solve for x and y:

2x = 3 + 34 = 37 mod 101, and 2y = 27(3 - 34) = 27(-31) = 27(70) = 72 mod 101.

And now I need the modular inverse of 2, and 2-1 = 51 mod 101.


x =51(37) = 69 mod 101, and y = 51(72) = 36 mod 101

So do they work? They HAVE to work, as it's math! But let's plug them in and check:

692 - 23(36)2 = -25047 = 1 - 248(101) = 1 mod 101

So they work! But of course they do, it's math.

But you don't get an explicit solution for x and y, and I'm curious about what r would give it to you.

I looked up the explicit solution even though it's easy to figure it out, and it is:

x = 24, and y = 5, as 242 - 23(5)2 = 1

From my derivation I have that r = x + ny mod 101, so: 24 + 15(5) = 99.

So guess I should have worked down from 101 instead of up!

The interested reader can run through with r = 99 and see that it all works.

And for me that is relaxing! It is just really cool seeing the numbers do as expected. And they follow rules that I found! Is it really practical? What do I care. I like the perfection and keeping my mind occupied.

For years when the world stresses me, I've had my math to rely on. It's a comfort like no other, and its perfection is a great shelter.

James Harris

No comments: