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.
Then:
3(2my+r)2 = 4Fr-1 - r2 mod N
and
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:
Post a Comment