x

^{3}- Dy

^{3}= 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: m

^{3}= D mod N, and r is some residue modulo N, where Fr

^{-1}exists.

Then:

3(2my+r)

^{2}= 4Fr

^{-1 }- r

^{2}mod N

and

x = my + r mod N

Here's a link to derivation of the result. The gist is just factoring x

^{3}- m

^{3}y

^{3}= 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 }- r

^{2}mod 16,

And 3(11) = 1 mod 16, so: (6y+r)

^{2}= 12Fr

^{-1 }- 11r

^{2}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 3

^{3}- 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 }- r

^{2}mod 53, and 3(18) = 1 mod 53, so:

(8y+r)

^{2}= 19Fr

^{-1 }- 18r

^{2}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 = m

^{3}- 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:

Post a Comment