How to use the pell equation solver
- Enter a whole number D from 2 to 1,000,000 that is not a perfect square.
- Enter how many solutions to list, from 1 to 10.
- The page expands the square root of D as a continued fraction and finds the smallest solution of x squared minus D y squared equals 1.
- Read the smallest solution, the number of digits in x, the length of the period and whether the equation with -1 on the right can be solved.
Formula
Expand sqrt(D) as a continued fraction. Each convergent h / k has h^2 - D k^2 equal to a small number.
The first convergent with h^2 - D k^2 = 1 gives the smallest solution (x1, y1)
Every other positive solution is the next power of x1 + y1 sqrt(D): x(n+1) = x1 x(n) + D y1 y(n), y(n+1) = x1 y(n) + y1 x(n)
The equation with -1 is solvable exactly when the period of the continued fraction is odd
The calculation uses exact whole-number arithmetic with no rounding, so even answers with hundreds of digits are correct.
D = 2, 13, 61 and 109
For D = 2 the smallest solution is (3, 2), because 9 - 2 x 4 = 1, and the next ones are (17, 12), (99, 70) and (577, 408). The equation with -1 is also solvable: (1, 1) works, since 1 - 2 = -1.
D = 13 gives (649, 180), and its minus one form has the solution (18, 5). D = 61, a famous hard case, needs (1766319049, 226153980), and its minus one form has (29718, 3805). D = 109 gives (158070671986249, 15140424455100). Each satisfies x squared minus D y squared equals 1 exactly. For D = 3 the period is even, so the minus one equation has no solution.
A brief history
The equation is named after John Pell, though he had little to do with it. Indian mathematicians such as Brahmagupta and Bhaskara II found methods for it more than a thousand years ago, and Fermat challenged European mathematicians to solve it in the 1650s. The numbers can be enormous: for D = 61 the smallest x already has ten digits, and for some D below 1000 it has dozens.
The continued fraction used here is the same tool you can try in the continued fraction calculator. For solving linear equations in whole numbers, see the linear Diophantine equation solver.
Uses of the solutions
Solutions give the best rational approximations to a square root, since x / y is close to the square root of D when x squared minus D y squared equals 1. They also appear in the study of units in number fields and in puzzles such as Archimedes' cattle problem. Very long values are shortened on the screen with the number of digits shown, while the copy and CSV keep every digit.
To test whether a number is prime or to explore related number theory, use the prime number calculator.
Assumptions and limits
- D is a whole number from 2 to 1,000,000 and not a perfect square.
- The solutions listed are positive. Negative signs of x and y give more solutions.
- The smallest solution is the first convergent that works. It is the fundamental one.
- Whole-number arithmetic is exact, with no limit on digits beyond memory.
Frequently asked questions
What is the Pell equation?
It is x squared minus D y squared equals 1, where D is not a perfect square and the answers x and y must be whole numbers.
How do you solve it?
Expand the square root of D as a continued fraction. The first convergent that satisfies the equation is the smallest solution, and all others follow from it.
Why are the answers so large?
The smallest solution can grow very fast with D. For D = 61 it already has ten digits, and it can have far more for other values.
When does x squared minus D y squared equals -1 have a solution?
When the continued fraction of the square root of D has an odd period, as for D = 2, 13 and 61.