Some computational results on a problem of Eisenstein. (English) Zbl 0689.10024

Théorie des nombres, C. R. Conf. Int., Québec/Can. 1987, 869-886 (1989).
Eisenstein in 1844 posed the problem of determining an a priori criterion to decide, for positive square free \(D\equiv 5 \pmod 8\), whether the Diophantine equation \[ | x^2-Dy^2| =4 \] has a solution \(x, y\) in co-prime integers. Such a criterion is necessary in relating the class numbers and fundamental units of the orders with \(\mathbb Z\)-bases \(\{1,(1+\sqrt{D})/2\}\) and \(\{1,\sqrt{D}\}\) over \(\mathbb Q(\sqrt{D})\).
The authors develop an algorithm based on the continued fraction expansion of \(\sqrt{D}\), which is of \(O(D^{1/4+\varepsilon})\) binary operations using integers of binary size \(O(D^{\varepsilon})\). The previously best known algorithm was \(O(D^{+\varepsilon})\). They report their computational experience of computing for all such \(D<10^9\).
For \(z>0\), let \(t(z)\) be the number of positive square free \(D<z\), let \(s(z)\) be the number of these with solutions to (1) and let \(r(z)=s(z)/(t(z)-s(z))\). The authors computed \(r(z)\) for all \(z<10^9\), and noted that \(r(z)>2\), and appears to be asymptotic to 2.
[For the entire collection see Zbl 0674.00008.]


11Y65 Continued fraction calculations (number-theoretic aspects)
11Y50 Computer solution of Diophantine equations
11-04 Software, source code, etc. for problems pertaining to number theory
11D04 Linear Diophantine equations


Zbl 0674.00008