Quadratic residue modular solution

So I've started playing around with trivial modular solutions to x² - Dy² = 1 as I'm bored and it's easy to do. Earlier I noted that:

x² - Dy² = 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² = 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² - Dy² = 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² - Dy² = 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