# Calculating the integral points of an elliptic curve

I asked this question on Math stachexchange. The question I have is:

Can I use Mathematica to find the (integral points on the following elliptic curve) or can I find when the number $$\text{n}$$ is a perfect square?

$$\text{n}=9+108x^2(1+x)$$

You can find the integer points with Solve:

With[{s = 10^5},
Solve[n == 9 + 108 x^2 (1 + x) && -s <= n <= s && -s <= x <= s,
{n, x}, Integers]]

(*    {{n -> -97191, x -> -10}, {n -> -69975, x -> -9}, {n -> -48375, x -> -8},
{n -> -31743, x -> -7}, {n -> -19431, x -> -6}, {n -> -10791, x -> -5},
{n -> -5175, x -> -4}, {n -> -1935, x -> -3}, {n -> -423, x -> -2},
{n -> 9, x -> -1}, {n -> 9, x -> 0}, {n -> 225, x -> 1},
{n -> 1305, x -> 2}, {n -> 3897, x -> 3}, {n -> 8649, x -> 4},
{n -> 16209, x -> 5}, {n -> 27225, x -> 6}, {n -> 42345, x -> 7},
{n -> 62217, x -> 8}, {n -> 87489, x -> 9}}    *)


Thanks to @MichaelE2: if you want only square values for $$n=y^2$$,

Solve[y^2 == 9 + 108 x^2 (1 + x) && 0 <= y <= 10^6, {y, x}, Integers]

(*    {{y -> 3, x -> -1}, {y -> 3, x -> 0}, {y -> 15, x -> 1},
{y -> 93, x -> 4}, {y -> 165, x -> 6}}    *)


This takes 0.7 seconds. The same calculation up to $$y\le10^9$$ gives the same solutions but takes 29 seconds.

For much larger search spaces you can adapt the 128-bit-integer C code from this solution.

• Is there a way to start at a certain value of $s$. So that it checks the values between to certain values for $s$. So for example: I want to know if there is a solution between $s=10^6$ and $s=10^9$? Jan 5, 2020 at 14:41
• Solve[n == 9 + 108 x^2 (1 + x) && 10^6 <= n <= 10^9, {n, x}, Integers] would do that. There are 189 solutions. Jan 5, 2020 at 14:44
• You could use y^2 in place of n to get just the solutions with perfect squares on the lid Jan 5, 2020 at 16:21
• @MichaelE2 I don't think there are any solutions that satisfy both the curve and the perfect square. These seem to be two separate questions by the OP, as far as I can tell. Specifically, FindInstance[y^2 == 9 + 108 x^2 (1 + x), {n, x}, Integers] gives no answers. Jan 5, 2020 at 16:30
• I got five for y below 10^6 with Solve[] Jan 5, 2020 at 16:34

You see a number of integral points by inspection: e.g. {1,15},{1,-15},{0,3},{0,-3},{-1,3},{-1,-3}.

You can pick a "generator point" and scalar multiply and filter rational solutions to get other integers. For example:

f[x_] := 9 + 108 x^2 (x + 1)
fun[{xa_, ya_}, {"O", "O"}] := {xa, ya}
fun[{"O", "O"}, {xa_, ya_}] := {xa, ya}
fun[{xp_, yp_}, {xq_, yq_}] :=
Module[{s, res},
If[{xp, yp} == {xq, yq}, s = (324 xp^2 + 216 xp)/(2 yp),
If[xp - xq == 0, Return[{"O", "O"}],
s = (yp - yq)/(xp - xq)]];
res = Simplify[{x, (s (x - xp) + yp)}] /.
Solve[ (s (x - xp) + yp)^2 == f[x], x, Reals];
Complement[res, {{xp, yp}, {xq, yq}}][] {1, -1}
]


Iterating:

pts = NestList[fun[#, {1, 15}] &, {1, 15}, 30];
ip = Cases[pts, {_?IntegerQ, _?IntegerQ}];
ContourPlot[y^2 == f[x], {x, -2, 7}, {y, -200, 200},
Epilog -> {{Red, PointSize[0.02],
Point[ip~Join~(# {1, -1} & /@ ip)]},
Arrow /@ Partition[pts, 2, 1]}]
Column[ip~Join~(# {1, -1} & /@ ip)] This is not systematic or comprehensive. Perhaps you can play around.

Here is a brute force approach using NumberTheoryPowersRepresentationsDumpProbablePerfectSquareQ, which I got from this comment by JM on a question asking for the Fastest square number test.

Quiet@PowersRepresentations[];(* Just to load the necessary context *)

nums =
Table[{x, NumberTheoryPowersRepresentationsDumpProbablePerfectSquareQ[9 + 108 x^2 (1 + x)]},
{x, 1, 1000000}];
(candidates = Cases[nums, {n_, True} :> n]) // Length

(* Out: 98132 *)


So this approach found close to 100,000 tentative values of $$x$$ for which that expression may be a perfect square. That should be followed up with an exact check:

Select[candidates, IntegerQ@Sqrt@(9 + 108 #^2 (1 + #)) &]

(* Out: {1, 4, 6} *)

• Well that is strange because between -10^6 and 10^6 there only exists 5 solutions. Dec 25, 2019 at 23:41
• @Jan Note the name starts with Probable. It quickly filters out most of the non-squares, but one should follow it up with an actual square test. Dec 26, 2019 at 0:54