Translate

Saturday, May 19, 2012

Deriving x and y modular solution

Given x2 - Dy2 = 1 it is trivial to find modular solutions for x and y modulo D-1:

x2 - Dy2 = 1 mod D-1, and D mod D-1 = 1, so:

x2 - y2 = 1 mod D-1

Which is: (x+y)(x-y) = 1 mod D-1, and letting r be any residue with an inverse modulo D-1:

x+y = r mod D-1 and x-y = r-1 mod D-1, so:

2x = r + r-1 mod D-1 and 2y = r -  r-1 mod D-1

I like leaving the 2 on the left hand side rather than use its modular inverse, which may not exist, or write a fraction on the right hand side.

That is easy to generalize mod D - k2, as well as with x2 - Dy2 = F.

x2 - Dy2 = F mod D-k2, and D mod D-k2  =  k2, if k2 is less than D so:

x2 - k2y2 = F mod D-k2 where now r1(r2) = F mod D-k2, so:

x+ky = r1 mod D-k2  and x-ky = r2 mod D-k2, and you have:

2x = r1 + r2 mod D-k2  and

2ky = r1 -  r2 mod D-k2

Here if the modular inverse of r1 modulo D-k2 exists I can substitute out r2 by using r2 = Fr1-1 mod D-k2 and have:

2x =  r1 + Fr1-1 mod D-k2  and

2ky = r1 - Fr1-1 mod D-k2

Derivation complete.

And I've derived the solution for y before, using a substitution x = z-y, but I think the above is a little cleaner looking and more direct. But it's not as applicable as it requires that k2 is less than D, unless that requirement is actually there with my prior results, where I just didn't see it. Puzzling over that detail though it makes sense as otherwise you could just make k really huge and pull out explicit solutions that way?

Regardless, I like finding multiple ways to do derivations and think this approach is elegant, and looks prettier while also being very easy.


James Harris
Post a Comment