^{2}- Dy

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

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

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

^{2}- 61y

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

^{2}= 61 mod 1766352723.

And m

^{-1}= 28957291 mod 1766352723.

And I found r = 55435303, which means that r

^{-1}= 1710850072 mod 1766352723.

Then

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:

1766319049

^{2}- (61)226153980

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

## No comments:

Post a Comment