Tuesday, August 28, 2012

Derivations are fun

Finding math derivations is something I enjoy doing, where I like finding multiple ones for the same thing as it helps understanding, and is an enjoyable exercise for me. So here is a post deriving a result I've already derived.

Given n such that: n2 = D mod p, where p is a prime number, and r, any residue modulo p:

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

gives solutions for x2 - Dy2 = 1 mod p.

Here I'll give a different derivation by considering two modular equations:

r = x + ny mod p


r-1 = x - ny mod p

Since r(r-1) = 1 mod p, I can just multiply and get:

r(r-1) = 1 = x2 - n2y2 mod p

Which is: x2 - n2y2 = 1 mod p

And introduce D, such that: D = n2 mod p, and I have: x2 - Dy2 = 1 mod p

Solving for x and y then is just a matter of adding and subtracting and simplifying with my original equations. Adding to solve for x and subtracting to solve for y, to get finally:

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

Here I like leaving the 2 on the left side as I think it is a little bit cleaner. And looking modulo p, means I don't have to worry if the modular inverse exists. Note, I don't consider 0 to be a residue.

This result will solve the original equation explicitly and non-trivially if you have p greater than x and y, and you happen to pick the right residue! Or just run through them all till you find it. So it's not like it's practical. But I like it.

Oh yeah, it will solve explicitly non-trivially as long as D is not a perfect square, because if D is a perfect square then you have (x-ny)(x+ny) = 1, which has only x=1 or -1, y = 0 as an integer solution.

Re-deriving results over and over again is maybe one of those things that others might not understand, but I think it's fun, and it's something that keeps the mind active for a bit before moving on to other things.

James Harris

No comments: