×

On the solution of \(x^2+dy^2=m\). (English) Zbl 1106.11042

This work is an interesting contribution to the algorithmic analysis of Diophantine equations. In fact, in 1908, G. Cornacchia gave a fast algorithm for solving the Diophatine equation \(x^2+dy^2=4p\), for \(p\) prime using continued fractions. More generally, the same algorithm can be used to solve the Diophantine equation \(x^2+dy^2=m\), where \(1\leq d \leq m\). The importance of this algorithm is undeniable as it is widely used and implemented (see MATHEMATICA, PARI, MAGMA, …). So many proofs of the validity of this algorithm are given.
A modified version of this algorithm can be found in H. Cohen’s book [A course in computational algebraic number theory. Graduate Texts in Mathematics. 138. Berlin: Springer-Verlag (1993; Zbl 0786.11071)]. In 1990, F. Morain and J.-L. Nicolas gave a proof of the validity of the Cornacchia’s algorithm using continued fractions and Diophantine approximation [On Cornacchia’s algorithm for solving the Diophantine equation \(u^2+dv^2=m\). Courbes elliptiques et tests de primalité. Thèse, Université de Lyon, 20 Septembre (1990)]. In 1995, R. Schoof reported a proof, due to H. W. Lenstra, of the validity of the algorithm [Counting points on elliptic curves over finite fields. J. Théor. Nombres Bordx. 7, No.1, 219–254 (1995; Zbl 0852.11073)]. The algorithm is used to count the number of points on an elliptic curve \(E\), where the endomorphism ring of \(E\) is known.
In the present article, a different strategy is applied and a simpler proof is given. The proof is based on lattice theory. In fact, the author proves that if \(L_t:=\langle (m, 0), \, (t, 1) \rangle_{\mathbb Z}\), where \(t\) is an integer such that \(0\leq t \leq m\) and \(t^2\equiv -d\) (mod \(m\)), then a primitive solution \((x_0,\, y_0)\) to \(x^2+dy^2=m\) belongs to \(L_t\). Moreover, he solves completely the case \(d=1\), i.e. the equation \(x^2+y^2=m\).

MSC:

11Y50 Computer solution of Diophantine equations
11D09 Quadratic and bilinear Diophantine equations
11J70 Continued fractions and generalizations
11Y16 Number-theoretic algorithms; complexity
PDFBibTeX XMLCite
Full Text: DOI Euclid

References:

[1] Cohen, H.: A Course in Computational Number Theory. Grad. Texts in Math., 138. Springer-Verlag, New York, pp. 34-36 (1993). · Zbl 0786.11071
[2] Morain, F., and Nicolas, J.-L.: On Cornacchia’s Algorithm for Solving the Diophantine Equation \(u^2+dv^2=m\). Courbes elliptiques et tests de primalite These, Universite de Lyon I, 20 September (1990).
[3] Wada, H.: A note on the Pell equation. Tokyo J. Math., 2 , 133-136 (1979). · Zbl 0413.10008 · doi:10.3836/tjm/1270473565
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.