Chakravala method
The chakravala method is an algorithm for solving the Pell equation
Contents
[hide]Method of composition
We let and be integers such that , and we notate .
We then choose an integer and let
Existence of suitable choice
We claim that it is always possible to choose such that is an integer.
Because , we have , so
Suppose . Then Because , also divides , so .
We can construct a set of possible integer values of , none congruent to another ; the corresponding values of take all distinct values , so there must be one element in the set such that ; that is, is an integer.
Recovery of initial conditions
We further claim that if is an integer, then
- is also an integer, and
- .
Evaluation
We now claim that .