Monday, June 25, 2012

Quadratic residue modular solution

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

x2 - Dy2 = 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:

n2 = 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:

 x2 - Dy2 = 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:

x2 - Dy2 = 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
Post a Comment