Pell's equation, also called the Pell–Fermat equation, is any Diophantine equation of the form where n is a given positive nonsquare integer, and integer solutions are sought for x and y. In Cartesian coordinates, the equation is represented by a hyperbola; solutions occur wherever the curve passes through a point whose x and y coordinates are both integers, such as the trivial solution with x = 1 and y = 0. Joseph Louis Lagrange proved that, as long as n is not a perfect square, Pell's equation has infinitely many distinct integer solutions. These solutions may be used to accurately approximate the square root of n by rational numbers of the form x/y.
This kind of equation was first studied extensively in India starting with Brahmagupta, who found an integer solution to in his Brāhmasphuṭasiddhānta circa 628. Bhaskara II in the 12th century and Narayana Pandit in the 14th century both found general solutions to Pell's equation and other quadratic indeterminate equations. Bhaskara II is generally credited with developing the chakravala method, building on the work of Jayadeva and Brahmagupta. Solutions to specific examples of Pell's equation, such as the Pell numbers arising from the equation with n = 2, had been known for much longer, since the time of Pythagoras in Greece and a similar date in India. William Brouncker was the first European to solve Pell's equation. The name of Pell's equation arose from Leonhard Euler mistakenly attributing Brouncker's solution of the equation to John Pell.As early as 1732–1733 Euler believed that John Pell had developed a method to solve Pell's equation, even though Euler knew that Wallis had developed a method to solve it (although William Brouncker had actually done most of the work): From p. 182: "At si a huiusmodi fuerit numerus, qui nullo modo ad illas formulas potest reduci, peculiaris ad invenienda p et q adhibenda est methodus, qua olim iam usi sunt Pellius et Fermatius." (But if such an a be a number that can be reduced in no way to these formulas, the specific method for finding p and q is applied which Pell and Fermat have used for some time now.) From p. 183: "§. 19. Methodus haec extat descripta in operibus Wallisii, et hanc ob rem eam hic fusius non-expono." (§ 19. This method exists described in the works of Wallis, and for this reason I do not present it here in more detail.) Lettre IX. Euler à Goldbach, dated 10 August 1750 in: From page 37: (For solving such questions, the Englishman Dr. Pell devised a singular method [which is] shown in Wallis' works.) From p. 227: (§ 98 Concerning this, a learned Englishman by the name of Pell has previously found a quite ingenious method, which we will explain here.) English translation: See especially footnote 4.In Euler's (pp. 227ff), he presents a solution to Pell's equation which was taken from John Wallis' , specifically, Letter 17 () and Letter 19 () of: The letters are in Latin. Letter 17 appears on pp. 56–72. Letter 19 appears on pp. 81–91. French translations of Wallis' letters: Letter 17 appears on pp. 457–480. Letter 19 appears on pp. 490–503. Wallis' letters showing a solution to the Pell's equation also appear in volume 2 of Wallis' (1693), which includes articles by John Pell: Letter 17 is on pp. 789–798; letter 19 is on pp. 802–806. See also Pell's articles, where Wallis mentions (pp. 235, 236, 244) that Pell's methods are applicable to the solution of Diophantine equations: (On Algebra by Dr. John Pell and especially on an incompletely determined problem), pp. 234–236. (Example of Pell's method), pp. 238–244. (Another example of Pell's method), pp. 244–246. See also: Whitford, Edward Everett (1912) "The Pell equation", doctoral thesis, Columbia University (New York, New York, USA), p. 52.
History Special cases As early as 400 BC in India and Greece, mathematicians studied the numbers arising from the n = 2 case of Pell's equation,
and from the closely related equation
because of the connection of these equations to the square root of 2. Indeed, if x and y are positive integers satisfying this equation, then x/y is an approximation of . The numbers x and y appearing in these approximations, called side and diameter numbers, were known to the Pythagoreans, and Proclus observed that in the opposite direction these numbers obeyed one of these two equations. Similarly, Baudhayana discovered that x = 17, y = 12 and x = 577, y = 408 are two solutions to the Pell equation, and that 17/12 and 577/408 are very close approximations to the square root of 2.
Later, Archimedes approximated the square root of 3 by the rational number 1351/780. Although he did not explain his methods, this approximation may be obtained in the same way, as a solution to Pell's equation.. Likewise, Archimedes's cattle problem—an ancient word problem about finding the number of cattle belonging to the sun god Helios—can be solved by reformulating it as a Pell's equation. The manuscript containing the problem states that it was devised by Archimedes and recorded in a letter to Eratosthenes, and the attribution to Archimedes is generally accepted today.
General case Around AD 250, Diophantus considered the equation
where a and c are fixed numbers, and x and y are the variables to be solved for. This equation is different in form from Pell's equation but equivalent to it. Diophantus solved the equation for (a, c) equal to (1, 1), (1, −1), (1, 12), and (3, 9). Al-Karaji, a 10th-century Persian mathematician, worked on similar problems to Diophantus.
In Indian mathematics, Brahmagupta discovered that
a form of what is now known as Brahmagupta's identity. Using this, he was able to "compose" triples and that were solutions of , to generate the new triples and Not only did this give a way to generate infinitely many solutions to starting with one solution, but also, by dividing such a composition by , integer or "nearly integer" solutions could often be obtained. For instance, for , Brahmagupta composed the triple (10, 1, 8) (since ) with itself to get the new triple (192, 20, 64). Dividing throughout by 64 ("8" for and ) gave the triple (24, 5/2, 1), which when composed with itself gave the desired integer solution (1151, 120, 1). Brahmagupta solved many Pell's equations with this method, proving that it gives solutions starting from an integer solution of for k = ±1, ±2, or ±4..
The first general method for solving the Pell's equation (for all N) was given by Bhāskara II in 1150, extending the methods of Brahmagupta. Called the chakravala (cyclic) method, it starts by choosing two relatively prime integers and , then composing the triple (that is, one which satisfies ) with the trivial triple to get the triple , which can be scaled down to
When is chosen so that is an integer, so are the other two numbers in the triple. Among such , the method chooses one that minimizes and repeats the process. This method always terminates with a solution. Bhaskara used it to give the solution x = , y = to the N = 61 case.
Several European mathematicians rediscovered how to solve Pell's equation in the 17th century. Pierre de Fermat found how to solve the equation and in a 1657 letter issued it as a challenge to English mathematicians.In February 1657, Pierre de Fermat wrote two letters about Pell's equation. One letter (in French) was addressed to Bernard Frénicle de Bessy, and the other (in Latin) was addressed to Kenelm Digby, whom it reached via Thomas White and then William Brouncker. The letter to Frénicle appears on pp. 333–334; the letter to Digby, on pp. 334–335. The letter in Latin to Digby is translated into French in:
Both letters are translated (in part) into English in: In a letter to Kenelm Digby, Bernard Frénicle de Bessy said that Fermat found the smallest solution for N up to 150 and challenged John Wallis to solve the cases N = 151 or 313. Both Wallis and William Brouncker gave solutions to these problems, though Wallis suggests in a letter that the solution was due to Brouncker.In January 1658, at the end of (letter 19), Wallis effusively congratulated Brouncker for his victory in a battle of wits against Fermat regarding the solution of Pell's equation. From p. 807 of (Wallis, 1693): "Et quidem cum Vir Nobilissimus, utut hac sibi suisque tam peculiaria putaverit, & altis impervia, (quippe non omnis fert omnia tellus) ut ab Anglis haud speraverit solutionem; profiteatur tamen qu'il sera pourtant ravi d'estre destrompé par cet ingenieux & scavant Signieur; erit cur & ipse tibi gratuletur. Me quod attinet, humillimas est quod rependam gratias, quod in Victoriae tuae partem advocare dignatus es, ..." (And indeed, Most Noble Sir [i.e., Viscount Brouncker], he [i.e., Fermat] might have thought [to have] all to himself such an esoteric [subject, i.e., Pell's equation] with its impenetrable profundities (for all land does not bear all things [i.e., not every nation can excel in everything]), so that he might hardly have expected a solution from the English; nevertheless, he avows that he will, however, be thrilled to be disabused by this ingenious and learned Lord [i.e., Brouncker]; it will be for that reason that he [i.e., Fermat] himself would congratulate you. Regarding myself, I requite with humble thanks your having deigned to call upon me to take part in your Victory, ...) Note: The date at the end of Wallis' letter is "Jan. 20, 1657"; however, that date was according to the old Julian calendar that Britain finally discarded in 1752: most of the rest of Europe would have regarded that date as January 31, 1658. See Old Style and New Style dates#Transposition of historical event dates and possible date conflicts.
John Pell's connection with the equation is that he revised Thomas Branker's translation. of Johann Rahn's 1659 book Teutsche AlgebraTeutsch is an obsolete form of Deutsch, meaning "German". Free E-book: Teutsche Algebra at Google Books. into English, with a discussion of Brouncker's solution of the equation. Leonhard Euler mistakenly thought that this solution was due to Pell, as a result of which he named the equation after Pell.
The general theory of Pell's equation, based on continued fractions and algebraic manipulations with numbers of the form was developed by Lagrange in 1766–1769."Solution d'un Problème d'Arithmétique", in Joseph Alfred Serret (ed.), Œuvres de Lagrange, vol. 1, pp. 671–731, 1867. In particular, Lagrange gave a proof that the Brouncker–Wallis algorithm always terminates.
Solutions Fundamental solution via continued fractions
Let denote the unique sequence of convergents of the regular continued fraction for . Then the pair of positive integers solving Pell's equation and minimizing x satisfies x1 = hi and y1 = ki for some i. This pair is called the fundamental solution. The sequence of integers in the regular continued fraction of is always eventually periodic. It can be written in the form , where denotes integer floor, and the sequence repeats infinitely. Moreover, the tuple is palindromic, the same left-to-right or right-to-left.
The fundamental solution is
The computation time for finding the fundamental solution using the continued fraction method, with the aid of the Schönhage–Strassen algorithm for fast integer multiplication, is within a logarithmic factor of the solution size, the number of digits in the pair . However, this is not a polynomial-time algorithm because the number of digits in the solution may be as large as , far larger than a polynomial in the number of digits in the input value n..
Additional solutions from the fundamental solution Once the fundamental solution is found, all remaining solutions may be calculated algebraically from
expanding the right side, equating coefficients of on both sides, and equating the other terms on both sides. This yields the recurrence relations
Concise representation and faster algorithms