Wednesday, May 23, 2012

Cubic Diophantine computations

So yesterday I found myself wondering what would happen if I extended my idea of looking modulo D-1 to a cubic Diophantine, which is just about curiosity! Here, I'll do a post with some computations.

To recap, I found that given x3 - Dy3 = 1, I could solve for y with:

3(2y+r)2  = 4r-1 - r2  mod D-1

where x = y+r mod D-1, and r is a residue which has a modular inverse modulo D-1.

So I'll arbitrarily use a situation where I have a solution, which is D=26, as x=3, y=1 works.

Then:  3(2y+r)2  = 4r-1 - r2  mod 25, and I'll try r=1, so (2y+1)2  = 1 mod 25.

Which gives 2y + 1 = 1 or -1 mod 25. So y = 0 or -1 mod 25, which works trivially.

Moving to r=2.

3(2y+2)2  = 4(13) - (2)2  mod 25 = 23 mod 25, so (2y+2)2  = 16 mod 25.

Which gives two solutions. One is 2y + 2 = 4 mod 25, so y = 1 mod 25.

For the other 2y = -4 mod 25, so y = 22 mod 25, then x = 24 mod 25.

And (24)3 - 26(22)3 = -263024 = 1 - (10521)(25) = 1 mod 25 as required.

James Harris

Tuesday, May 22, 2012

Considering a cubic Diophantine

It is intriguing to me to consider now a cubic Diophantine with the approach of considering it modulo D-1.

Given x3 - Dy3 = 1 I'll try to find modular solutions for x and y modulo D-1:

x3 - Dy3 = 1 mod D-1, and D mod D-1 = 1, so:

x3 - y3 = 1 mod D-1

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

x-y = r mod D-1 and x2 + xy + y2 = r-1 mod D-1, so, x = y+r mod D-1, allowing me to substitute:

(y+r)2 + (y+r)y + y2 = r-1 mod D-1

and expanding out gives:

y2 + 2yr + r2 + y2 + ry + y2 = r-1 mod D-1, so:

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

y2 + yr + r2 /4 -  r2 /4+( r2  -  r-1 )/3 = 0 mod D-1, which is: (y+r/2)2  = -(r2 - 4r-1)/12  mod D-1, so:

3(2y+r)2  = 4r-1 - r2  mod D-1

And I think it is kind of ugly. But I'd think you could get answers with it, but just have to be able to find a quadratic residue, if it exists.

Just a curiosity. I'll put this up and maybe come back later to check my derivation and try it with some numbers.

I don't know of a practical use for this result, but it seemed like a fun thing to just extend a bit, and see what I got.

James Harris

Saturday, May 19, 2012

Deriving x and y modular solution

Given x2 - Dy2 = 1 it is trivial to find modular solutions for x and y modulo D-1:

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

I like leaving the 2 on the left hand side rather than use its modular inverse, which may not exist, or write a fraction on the right hand side.

That is easy to generalize mod D - k2, as well as with x2 - Dy2 = F.

x2 - Dy2 = F mod D-k2, and D mod D-k2  =  k2, if k2 is less than D so:

x2 - k2y2 = F mod D-k2 where now r1(r2) = F mod D-k2, so:

x+ky = r1 mod D-k2  and x-ky = r2 mod D-k2, and you have:

2x = r1 + r2 mod D-k2  and

2ky = r1 -  r2 mod D-k2

Here if the modular inverse of r1 modulo D-k2 exists I can substitute out r2 by using r2 = Fr1-1 mod D-k2 and have:

2x =  r1 + Fr1-1 mod D-k2  and

2ky = r1 - Fr1-1 mod D-k2

Derivation complete.

And I've derived the solution for y before, using a substitution x = z-y, but I think the above is a little cleaner looking and more direct. But it's not as applicable as it requires that k2 is less than D, unless that requirement is actually there with my prior results, where I just didn't see it. Puzzling over that detail though it makes sense as otherwise you could just make k really huge and pull out explicit solutions that way?

Regardless, I like finding multiple ways to do derivations and think this approach is elegant, and looks prettier while also being very easy.

James Harris

Saturday, May 05, 2012

Shifting to math is fun perspective

I like playing with numbers, and figuring things out about them. And admitting that to myself helps a lot, and I think this blog has plenty of interesting things for people who like to play with numbers and I've put up some introductory information including a page introducing modular arithmetic to help people get quickly to things that work.

It's better I think to shift to math is fun. And I have so many math ideas where you can just play with numbers and see things for yourself.

Like counting quadratic residue pairs! I didn't even know what a quadratic residue pair was until recently, because of a discovery.

Quadratic residues are the squares of modular arithmetic, like with x2 = r mod N, r is the quadratic residue.

Here are the quadratic residues for 29:

1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28

Some are explicitly squares, like 4, 9 and 16, while others are not as you flip over when you get past 29, so for instance 62 = 36 = 7 mod 29.

And some of the quadratic residues follow each other, like 4 and 5 and 5 and 6, and math people call those quadratic residue pairs and I figured out a way to count them. There was a way known before, but I found my own way, which I like better.

The end equations have to be the same, of course.

And if p is prime, and p mod 4 = 1, the count is (p-5)/4, which for 29 is 6.

And here are the pairs with participating numbers in bold. Note that 4,5 is a pair, as is 5,6, so they count as two.

1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28

Go with what people can prove. If you like playing with numbers there are lots of things on this blog, where I explain and derive. I'm not a mathematician though, and am not trained in writing things in some peculiar format, so I have my own style. Proof is rigorous though.

And besides the numbers speak more eloquently. There can be such a thrill in watching numbers follow these beautiful mathematical rules. Math IS fun.

All of the above is the confident, act like I really know what I'm doing kind of thing, but at the end, yeah, it is about the numbers. If your math is right, the numbers behave by stated rules. And for some, the precision and beauty of numbers IS all that's really important when it comes to discussing useful mathematics.

James Harris

Friday, May 04, 2012

Simplifying number theory

Surprisingly to me, I have found my ability to simplify certain areas of number theory to be the best path to confidence in my ideas, and importantly in discrete mathematics I found a way to reduce Diophantine equations like:

c1x2 + c2xy + c3y2 = c4 + c5x + c6y

which is called a binary quadratic Diophantine as x and y are the unknowns, to a general form like:

u2 - Dv2 = C

where u and v are the new unknowns and in solving them you find x and y with the original equation.

It's a simplification of number theory as the traditional ways to reduce involve three different ways depending on the values of the c's, while I found there is one way available.

I used a mathematical tool I call tautological spaces for that discovery, which also gave me a very useful relation on the simplified form, where I'll go back to x and y for the unknowns:

The equation x2 - Dy2 = F

requires that

(x+Dy)2 - D(x+y)2 = -F(D-1).

Remarkably that alone allowed me to connect equations when F=1, with Pythagorean Triples when D-1 is a square, which was the first indication for me, of the importance of D-1, where since then I've been able to explain the size of fundamental solutions, with factors of D-1 being part of it.

That covers research mostly completed in 2008. I've updated some of it recently, for better exposition.

These results were I believed intriguing and they helped my confidence as I could just play with actual numbers and watch them behave as the equations required. But I still was looking for social validation from mathematical society.

Recently I found that I could do even more with the simplified form and solve for y modularly:

Instead of x2 - Dy2 = F, let x = z-ky or x = -(z-ky), so:

(z-ky)2 - Dy2 = F.

Then it can be shown that if integer solutions for x2 - Dy2 = F exist, it must be true that:

2ky = z - Fz-1 mod D-k2

(z-ky)2 = k2y2 + F mod D-k2

Here there is the additional requirement that 2kyz + F = -1 or 1 mod 8, or 0 mod 4, if D-k2 is a square.

And now it was REALLY cool watching numbers behave as expected including quadratic residues where their spacing now made mathematical sense as being governed by those equations.

James Harris