Translate

Thursday, December 06, 2012

Surprising modular discovery progression

After years with my own mathematical results I was surprised to come across something which to me is bizarrely simple for the 21st century, as how can this approach be new? But I haven't found it elsewhere yet, while I keep looking. And I'll put it up in a bit, and then walk down the progression from it to a general modular solution.

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

A modular solution to x2 - Dy2 = 1 is:

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

Proof:

x2 - Dy2 = 1 mod D-1, and D mod D-1 = 1, so:

x2 - y2 = 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: n2 = 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 x2 - Dy2 = 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 x2 - Dy2 = F where all variables are non-zero integers:

Given 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 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 - m2, or N = m2 - 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
Post a Comment