Difference between revisions of "Chakravala method"
(→Method of composition: Corrected for the case where q is negative) |
(Added summary of the algorithm.) |
||
Line 34: | Line 34: | ||
From [[Brahmagupta's Identity]] (with <math>n = -D</math> and <math>d = 1</math>) we have <cmath>(ac+Db)^2 - D(a+bc)^2 = (a^2-Db^2)(c^2-D).</cmath> | From [[Brahmagupta's Identity]] (with <math>n = -D</math> and <math>d = 1</math>) we have <cmath>(ac+Db)^2 - D(a+bc)^2 = (a^2-Db^2)(c^2-D).</cmath> | ||
That is, <cmath>(q\alpha)^2 - D(q\beta)^2 = q(c^2-D).</cmath> Dividing both sides by <math>q^2</math> gives the desired result. | That is, <cmath>(q\alpha)^2 - D(q\beta)^2 = q(c^2-D).</cmath> Dividing both sides by <math>q^2</math> gives the desired result. | ||
+ | |||
+ | ==Algorithm== | ||
+ | We begin by choosing initial [[relatively prime]] integers <math>a</math> and <math>b</math>. At each step, we choose the value of <math>c</math> that minimizes <math>|c^2 - D|</math> (among the values of <math>c</math> for which <math>\beta</math> is an integer) and replace the values of <math>a</math> and <math>b</math> with the resulting values of <math>\alpha</math> and <math>\beta</math>. Repeating this step, the value of <math>q</math> eventually reaches <math>1</math>, yielding a solution to the Pell equation. |
Revision as of 16:08, 3 March 2023
The chakravala method is an algorithm for solving the Pell equation
Contents
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 a positive 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.
Algorithm
We begin by choosing initial relatively prime integers and
. At each step, we choose the value of
that minimizes
(among the values of
for which
is an integer) and replace the values of
and
with the resulting values of
and
. Repeating this step, the value of
eventually reaches
, yielding a solution to the Pell equation.