Thursday, August 13, 2015

Considering modular with a cubic Diophantine

Spend a lot of time with quadratics but also did extension of some ideas to the cubic equation:

x3 - Dy3 = F

And found that I could solve modulo N, where N is a cubic residue of D that does not share any prime factors with F, m is the cubed residue, so: m3 = D mod N, and r is some residue modulo N, where Fr-1 exists.


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


x = my + r mod N

Here's a link to derivation of the result. The gist is just factoring x3 - m3y3 = F mod N, in order to get those modular solutions.

Usage steps:

First step then is to find some N for which D is a cubic residue, which does not share prime factors with F, then find m, which is the cubed residue, then for some residue r, you can find y if it exists, and then x.

Some numeric examples:

To explore and confirm equations are correct will not specify F, but will see what I can do knowing just D, so for example if you have D = 11, a close cube is 27, so N = 16 will work if F is odd, and I have then m = 3.

So I have:

3(6y+r)2  = 4Fr-1 - r2  mod 16,

And 3(11) = 1 mod 16, so: (6y+r)2  = 12Fr-1 - 11r2  mod 16

And the only quadratic residues of 16, are: 1, 4 and 9

Can pick any odd r and have its modular inverse exist, so let r =3 to start. Then:

(6y+3)2  = 4F - 3  mod 16, which means:

F = 1, 5 mod 16 for 1, 4 is blocked, and 3, or 7 mod 16 for 9.

Which means F = 1, 3, 5, or 7 mod 16, which is all of the odd residues. Well that didn't tell me much then, but at least equations did work.

Noticed that 33 - 11 = 16, but that was excluded with N = 16, to keep F and N from sharing prime factors. But should be able to find that one with a different N.

So will try an odd N. Another close cube is 64, and 64 - 11 = 53, so N = 53, and m = 4.

3(8y+r)2  = 4Fr-1 - r2  mod 53, and 3(18) = 1 mod 53, so:

(8y+r)2  = 19Fr-1 - 18r2  mod 53.

And can figure out r, if x = 3, y =1, as then x = 4y + r mod 53.

So r = -1 mod 53 = 52 mod 53 = r-1 mod 53.

Quadratic residues of 53 are:

1, 4, 9, 12, 13, 16, 17, 25, 29, 36, 40, 48, 49

(8y+r)2  = 19(16)(-1) - 18  mod 53 = -322 mod 53 = -4 mod 53 = 49 mod 53

Which works with 8y - 1 = 7 mod 53, so y = 1 mod 53.

Lessons learned from examples:

Glad I just calculated an r that would work, as tried from the bottom with r = 2 mod 53, which didn't work at all. But I already knew that not every r would work.

And finding N and m is trivially easy. That's good. You can just find cubes near your D, which gives you m, and then N, with N = m3 - D.

Here the solution for y modulo N involving a quadratic residue means it might be possible to check for existence of solutions.

Proving explicit x and y do not exist would definitely involve checking each residue r available for a given N that fits the rules.

If you try each r modulo N, and find that no y modulo N exists, then of course there are no integer solutions for x and y.

Most of my focus with modular solutions has been on quadratics, but it's worth reminding some of the techniques can go beyond quadratics.

James Harris

No comments: