^{2}- Dy

^{2}= 1 it is trivial to find modular solutions for x and y modulo D-1:

x

^{2}- Dy

^{2}= 1 mod D-1, and D mod D-1 = 1, so:

x

^{2}- y

^{2}= 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 - k

^{2}, as well as with x

^{2}- Dy

^{2}= F.

x

^{2}- Dy

^{2}= F mod D-k

^{2}, and D mod D-k

^{2}= k

^{2}, if k

^{2}is less than D so:

x

^{2}- k

^{2}y

^{2}= F mod D-k

^{2}where now r

_{1}(r

_{2}) = F mod D-k

^{2}, so:

x+ky = r

_{1}mod D-k

^{2}and x-ky = r

_{2}mod D-k

^{2}, and you have:

2x = r

_{1}+ r

_{2}mod D-k

^{2}and

2ky = r

_{1}- r

_{2}mod D-k

^{2}

Here if the modular inverse of r

_{1}modulo D-k

^{2}exists I can substitute out r

_{2}by using r

_{2}= Fr

_{1}

^{-1}mod D-k

^{2}and have:

2x = r

_{1}+ Fr

_{1}

^{-1}mod D-k

^{2}and

2ky = r

_{1}- Fr

_{1}

^{-1}mod D-k

^{2}

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 k

^{2}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

## 2 comments:

This formulas use maths subject, Thanks solving x and y modular solution.

driver school

Thanks for your interest!

Post a Comment