Given n such that: n

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

^{2}- Dy

^{2}= 1 mod p.

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

r = x + ny mod p

and

r

^{-1}= x - ny mod p

Since r(r

^{-1}) = 1 mod p, I can just multiply and get:

r(r

^{-1}) = 1 = x

^{2}- n

^{2}y

^{2}mod p

Which is: x

^{2}- n

^{2}y

^{2}= 1 mod p

And introduce D, such that: D = n

^{2}mod p, and I have: x

^{2}- Dy

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

Post a Comment