Large fundamental solutions of Pell's equation

---

Introduction Results References Links Contact [Up]

---

Introduction

Let A be a positive integer which is not a perfect square. It is well known that there exist an infinite number of integer solutions of the equation Ax^2+1=y^2, known as Pell's equation. The first non-trivial solution of this Diophantine equation, from which all others are easily computed, can be found using, e.g., the cyclic method [1], known in India in the 12th century, or using the slightly less efficient but more regular English method [1] (17th century). There are other methods to compute this so-called fundamental solution, some of which are based on a continued fraction expansion of the square root of A.

Results

This page describes our attempts to find the values of A that give rise to record-holders in the number of iterations of the cyclic and/or English methods, denoted respectively by n_c(A) and n_e(A), or in the size of the fundamental solution, denoted by s(A). We define the size of the fundamental solution as the number of base 10 digits of the smallest y higher than one that solves Pell's equation (actually, we use the base 10 logarithm of the fundamental solution). As usual, A is a record-holder for, e.g., the size of the solution, if s(B)<s(A) for all 1<B<A, i.e., the size of the fundamental solution for A is larger than the size of all previous fundamental solutions. Although our search is not exhaustive, we are confident that we have not missed any record-holder.

We have tested all interesting values of A up to 10001104330681. We found empirically that for A>394 all record-holders appear to be congruent, modulo 60, to either 1 or 49. Furthermore, for these values of A all record-holders appear to be prime numbers. We thus restricted our search to the values of A satisfying these conditions. We also found that many small primes tend to be quadratic residues of the record-holders. By Gauss' quadratic reciprocity law, the reverse is also true because the interesting values of A are of the form 4k+1 (it is interesting to note that, modulo 60, the only numbers that are simultaneously quadratic residues modulo 3, 4, and 5 are congruent, modulo 60, to either 1 or 49). This observation allowed us, for large values of A, to restrict the search even more.

The following table present some of the n_c(A), n_e(A), and s(A) record-holders. The current complete list of record-holders, in an obvious ASCII format, is also available [31k, compressed with gzip].

The following figure presents some of the record-holders, in a log-log graph.

From this figure it is apparent that there exist approximate power laws between A and n_c(A), n_e(A), and s(A), all with an exponent close to 0.52. An analysis of all available data also shows that, for large A, the ratio n_e(A) / n_c(A) appears to converge to a value between 1.440 and 1.441 and that the ratio s(A) / n_e(A) appears to converge (slower) to a value close to 0.515. This last value is probably related with the Gauss-Kus'min theorem [2], in which context the number

   1             1            log(1+x)         pi^2          
-------  INTEGRAL   -log(x) d -------- = ----------------- = 0.515320417...
log(10)          0             log(2)    12 log(2) log(10)   

appears more or less naturally. The exponent 0.52 mentioned above may tend as well to this value, since it appears that the rates of growth of the three curves of the figure are decreasing very slowly.

References

Additional links

• MathWorld's Gauss-Kuzmin-Wirsing Constant page.
• MathSoft's Gauss-Kuzmin Constants page.
• CALC has a function to compute the first solution of Pell's equation.

Tomás Oliveira e Silva Departamento de Electrónica, Telecomunicações e Informática Universidade de Aveiro 3810-193 AVEIRO PORTUGAL				January 1, 2009
Phone: +351-234-370379 Fax: +351-234-370545		Phone (internal): 23013 Office: DET 237
E-mail address: tos@ua.pt Home page: http://www.ieeta.pt/~tos/