Command for negative pell equations in PARI-GP or SAGE

Question

Is there any common command for testing negative Pell equations in PARI-GP or Sage? I searched for this question online and realized that Testing negative Pell equations online is checking solubility, but won't work when the running time is exceeding 60 seconds.

Answer 1

pari-gp code:

npell()=
{
 S= Set();
 for(D=2, 100, if(!issquare(D),
  Q= bnfinit('x^2-D,1);
  fu= Q.fu[1]; \\print("Fundamental Unit: "fu);
  C= -1;
  N= bnfisintnorm(Q, C); \\print("Fundamental Solutions (Norm): "N"\n");
  for(k=1, #N, n= N[k];
   for(j=0, 10,
    s= lift(n*fu^j);
    X= abs(polcoeff(s, 0)); Y= abs(polcoeff(s, 1));  
    if(X^2-D*Y^2==C, if(Y, if(X==floor(X), if(Y==floor(Y),
\\     print("("X", "Y")        j = "j"        D = "D);
     S= setunion(S, [D])
    ))))
   )
  )
 ));
 print("\n"#S"\n"S)
};

Let $S$ is set of solvable $D$, $j$ is power of fundamental unit.

Note:

1. solution exist for $j \equiv 0\pmod 2$
2. $D$=2..100 and $j$=0 $\implies$ #$S$=13
3. $D$=2..100 and $j$=0..2 $\implies$ #$S$=20
4. $D$=2..1000 and $j$=0..2 $\implies$ #$S$=148
5. $D$=2..1000 and $j$=0..20 $\implies$ #$S$=152

Answer 2

Not an answer
Long winded comment

It is fairly simple to write your own program to check whether, for a given $~D~ \in \Bbb{Z^+} ~: D ~$ is square free, the following equation has any positive integer solutions:

$$X^2 - DY^2 = -1. \tag1 $$

See the following sources:

• Chapter 1, specifically, for Khinchin pdf.

• Olds pdf. See especially, chapter 4.

You have to be careful, examining the two sources, because the first source uses the convention of expressing continued fractions as $~[a_0;a_1,a_2,\cdots],~$ while the second source uses the convention of expressing continued fractions as $~[a_1;a_2,a_3,\cdots].$

Because of the two different conventions, the two sources express the corresponding theorems with different indexing.

Basically, (1) above will have a solution if and only if the length of the period of the continued fraction is odd, rather than even. So, the thing to do is write your own program to compute the period.

Once it is computed, you can then count the number of digits in the period.

An alternative approach, once the period is computed, is to find the primitive solution $(X_1,Y_1)$ of

$$X^2 - DY^2 = \pm 1. \tag2 $$

You can then check whether

$$X_1^2 - DY_1^2 ~\text{equals 1 or -1}.$$

Note further that once the primitive solution $(X_1,Y_1)$ is computed, you can then easily generate all solutions $~\left(X_k,Y_k\right) ~$to (2) above, via

$$\left(X_k + Y_k\sqrt{D}\right) = \left(X_1 + Y_1\sqrt{D}\right)^k.$$

---

The remainder of this response is computer programming oriented, rather than Math oriented.

Whatever computer programming language that you use, you will definitely need to access its facility to handle very large integers (e.g. perhaps over 100 digits). Java has a BigInteger class. I strongly suspect that programming languages like C or Python have a similar facility.

Your program should work entirely with integers. That is, stay away from any use of (for example) floating decimals. That approach will (flat out) not work here.

If you have never programmed before, I recommend making Python your first language.