So I found out recently that a certain well-known equation could be solved modularly:

A modular solution to x

^{2}- Dy

^{2}= 1 is:

2x = r + r

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

^{-1}mod D-1

Proof:

x

^{2}- Dy

^{2}= 1 mod D-1, and D mod D-1 = 1, so:

x

^{2}- y

^{2}= 1 mod D-1

Which is: (x+y)(x-y) = 1 mod D-1, and letting r be any residue with an inverse modulo D-1:

x+y = r mod D-1 and x-y = r

^{-1}mod D-1, so:

2x = r + r

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

^{-1}mod D-1

Proof complete.

That one is easy and short so I decided to use more of a traditional format. Math people can get really weird about how you present things. It's their way, or...well it's just THEIR way. And they get

*years*of training at colleges and universities for a particular format. I didn't get that training in their format. I was a physics student. But I digress.

Next step is to generalize beyond modulo D-1.

Given n such that: n

^{2}= D mod p, where p is a prime number, and r, any residue modulo p:

2x = r + r

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

^{-1}(r - r

^{-1}) mod p

gives solutions for x

^{2}- Dy

^{2}= 1 mod p.

And THAT can be generalized to modulo N.

But this approach can be taken still further to something even more general.

With x

^{2}- Dy

^{2}= F where all variables are non-zero integers:

Given 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 2my = r - Fr

^{-1}mod N

Which of course gives you the original result, with F = 1 and N = D-1.

Or the modulo p result with F = 1, N = p.

Of course the simple reality I'm exploiting is that in modular arithmetic a non-zero D is always a square!

Proof: Let N = D - m

^{2}, or N = m

^{2}- D, for any non-zero integer m, then D is a quadratic residue modulo N.

To me it is a very surprising progression, with simple solutions which can actually solve these equations explicitly if x and y exist less than N, though I'm not suggesting it as a practical technique in these forms.

Why such a simple, basic modular arithmetic concept is not part of what I'm seeing on math websites about these equations is a puzzle to me.

James Harris

## No comments:

Post a Comment