^{2}- Dy

^{2 }= 1 as I'm bored and it's easy to do. Earlier I noted that:

x

^{2}- Dy

^{2}= 1 mod D-1, is solved modularly by:

2x = r + r

^{-1}mod D-1 and 2y = r - r

^{-1}mod D-1

Now I've thought up another easy one using some prime p for which D is a quadratic residue, so there exists n, such that:

n

^{2}= D mod p

Then I have (x + ny)(x - ny) = 1 mod p.

And with x + ny = r mod p, and x - ny = r

^{-1}mod p, then

2x = r + r

^{-1}mod p and 2y = n

^{-1}(r - r

^{-1}) mod p

Giving yet another way to solve for x and y modularly.

And, of course, as it's a modular solution it is for:

x

^{2}- Dy

^{2}= 1 mod p

So you don't necessarily get an explicit answer to the original equation.

Of course you can generalize easily enough modulo some natural number N for which D is a quadratic residue, and continue even further to solve modularly for the equation:

x

^{2}- Dy

^{2}= F

Where F is some natural number.

If "mod" is unfamiliar to you, I made up a small primer covering modular arithmetic that you may find useful.

James Harris

## No comments:

Post a Comment