Thursday, March 14, 2013

Pondering the obvious

One of my new favorite things is playing with a very simple concept to get modular solutions for certain Diophantine equations. But it's kind of weird in a way as just look at:

x2 - Dy2 = F

And you're blocked from factoring if D isn't a perfect square, like if:

x2 - 5y2 = 1

That block for the explicit equation, is it a conceptual block for many?

Does it tell the human mind: cannot factor?

But 5 is a quadratic residue for an infinity of numbers! So there exists some 'm' such that modulo some 'N':

m2 = 5 mod N

where there are an infinity of possibilities! And I like infinity. So now I can just substitute:

x2 - m2y2 = F mod N

where m2 = D mod N, and now, of course, it factors!

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

And you can solve for x and y modulo N by using a residue 'r' and the existence of Fr-1 mod N:

2x = r + Fr-1 mod N and 2my = r - Fr-1 mod N

And you can use that simple principle all over the place, and use it with cubics too or higher, and it's just fun, fun, fun.

And it took me years to figure this out, which I find rather odd.

It's such a simple idea, why would it take me so long?

But, um, that's what I can contemplate quietly, pondering how such a simple idea would take me so long to notice.

Wondering how it could be new to an entire world? Well that's overwhelming, and I hesitate on that one as I don't know. What I DO know is that I go looking for this method on the web from someone other than me and don't see it, which doesn't prove that it is new. It just seems too simple to me to be new.

But then again I have made math discoveries, which I've verified are new, and I have been forced to ponder that before and just don't know how exactly I seem to be able to figure certain things out.

It is cool though.

If you have a citation where this idea is used please comment. I find it hard to believe such a simple thing is owned by me as yet one more of my discoveries. Seems too easy.

James Harris

Monday, March 11, 2013

Generalizing cubic Diophantine solution

Going to consider a cubic Diophantine modulo N adapting a prior post.

Given x3 - Dy3 = F I'll try to find modular solutions for x and y modulo N.

First find m, such that m3 = D mod N, so N must have D as a cubic residue.

For example you can simply find an N using N = m3 - D, which is cool so we can simply pick m and force N versus going the other way, figuring things out. So now I have:

x3 - Dy3 = F mod N, so:

x3 - m3y3 = F mod N

Which is: (x-my)(x2 + mxy + m2y2) = F mod N, and letting r be any residue with an inverse modulo N:

x-my = r mod N and x2 + mxy + m2y2 = Fr-1 mod N, so, x = my+r mod N, allowing me to substitute:

(my+r)2 + m(my+r)y + m2y2 = Fr-1 mod N

and expanding out gives:

m2y2 + 2myr + r2 + m2y2 + rmy + m2y2 = Fr-1 mod N, so:

3m2y2 + 3myr + r2  -  Fr-1 = 0 mod N, and I'll use fractions--though it can be done without them--to make things easier for me and complete the square:

m2y2 + myr + r2 /4 -  r2 /4+( r2  -  Fr-1 )/3 = 0 mod N,

which is: (my+r/2)2  = -(r2 - 4Fr-1)/12  mod N, so:

3(2my+r)2  = 4Fr-1 - r2  mod N

Which was easy enough.

Interesting. So you can solve for x and y modulo N, if D is a cubic residue modulo N, F is a cubic residue modulo D if a certain quadratic residue exists, and m has a modular inverse modulo N.

This particular approach could also work for the quartic case, easily enough. But I think that's it though I'm not sure.

James Harris