Friday, September 28, 2012

Generalizing modular solution

The equation x2 - Dy2 = F where all variables are non-zero integers can be solved modularly.

Find a non-zero integer N for which a residue m exists where: m2 = D mod N, and r, any residue modulo N for which Fr-1 mod N exists then:

2x = r + Fr-1 mod N and 2y = m-1(r - Fr-1) mod N

if m does not share prime factors with N, otherwise: 2my = r - Fr-1 mod N.

Proving the above one simply relies on D being a quadratic residue modulo some N, so if D = m2 mod N you can factor the original as:

(x + my)(x - my) = F mod N

And then let x + my = r mod N, and x - my = Fr-1 mod N, and then you can just add to solve for x and subtract to solve for y.

I like to leave the 2 on the left hand side because it's simpler than handling cases where its modular inverse exists or does not.

Not doing so with m means I have to mention a special case and maybe I should do the same?

And I'm going to go now to the famous x2 - 61y2 = 1, and use an r that I found in a previous post, using the published explicit solution.

There I picked N = 1766352723, and m = 42028, as 420282 = 61 mod 1766352723.

And m-1 = 28957291 mod 1766352723.

And I found r = 55435303, which means that r-1 = 1710850072 mod 1766352723.


2x = 55435303 + 1710850072 mod 1766352723 = 1766285375 mod 1766352723

2y = (28957291)(55435303 - 1710850072) mod 1766352723 = 452307960 mod 1766352723

And 2-1 = 883176362 mod 1766352723, so I get finally:

x = (883176362)(1766285375) mod 1766352723 = 1766319049

y = (883176362)(452307960) mod 1766352723 = 226153980

Which are the exact solutions as:

17663190492 - (61)2261539802 = 1

Where I knew that as I used that solution to find r, but it's fun looking at the numbers going in the other direction with a famous case. It's also just kind of fun using big numbers even though the math does not care.

And that was with F=1, but the generalization doesn't care and will handle F, a non-zero integer.

It's interesting to me that the original equation can look like it doesn't factor if D is not a square, but of course it always does in modular arithmetic, so getting a modular solution is easy.

James Harris