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 therefore 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
- .
For the first claim, we use the fact that is an integer to conclude that . Therefore, The right-hand side of the above congruence is ; the left side is . Because is a multiple of and , is also a multiple of . Thus, is an integer.
For the second claim, we prove that . Suppose that an integer divides both and . Similarly to before, we consider and use the assumption that is a multiple of to make the substitution , obtaining But is a multiple of , so is also a multiple of . Thus, is a divisor of .
Evaluation
We now claim that .
From Brahmagupta's Identity (with and ) we have That is, Dividing both sides by gives the desired result.