Difference between revisions of "Chakravala method"
(Added summary of the algorithm.) |
m (Fixed article to indicate that c must be positive.) |
||
Line 4: | Line 4: | ||
We let <math>a</math> and <math>b</math> be integers such that <math>\gcd(a,b) = 1</math>, and we notate <math>a^2 - Db^2 = q</math>. | We let <math>a</math> and <math>b</math> be integers such that <math>\gcd(a,b) = 1</math>, and we notate <math>a^2 - Db^2 = q</math>. | ||
− | We then choose | + | We then choose a positive integer <math>c</math> and let |
<cmath>\begin{align*} \alpha &= \frac{ac+Db}{q}, \\ | <cmath>\begin{align*} \alpha &= \frac{ac+Db}{q}, \\ | ||
\beta &= \frac{a+bc}{q}.\\ \end{align*}</cmath> | \beta &= \frac{a+bc}{q}.\\ \end{align*}</cmath> | ||
Line 15: | Line 15: | ||
Suppose <math>a + bc \equiv a + bc' \pmod{|q|}</math>. Then <math>q \mid b(c - c')</math>. Because <math>\gcd(q,b) = 1</math>, <math>q</math> also divides <math>c - c'</math>, so <math>c \equiv c' \pmod{|q|}</math>. | Suppose <math>a + bc \equiv a + bc' \pmod{|q|}</math>. Then <math>q \mid b(c - c')</math>. Because <math>\gcd(q,b) = 1</math>, <math>q</math> also divides <math>c - c'</math>, so <math>c \equiv c' \pmod{|q|}</math>. | ||
− | We can therefore construct a set of <math>q</math> possible integer values of <math>c</math>, none congruent to another <math>\mathrm{mod} \; |q|</math>; the corresponding values of <math>a + bc</math> take all <math>|q|</math> distinct values <math>\mathrm{mod} \; |q|</math>, so there must be one element <math>c_0</math> in the set such that <math>a + bc_0 \equiv 0 \pmod q</math>; that is, <math>\frac{a + bc_0}{q}</math> is an integer. | + | We can therefore construct a set of <math>q</math> possible positive integer values of <math>c</math>, none congruent to another <math>\mathrm{mod} \; |q|</math>; the corresponding values of <math>a + bc</math> take all <math>|q|</math> distinct values <math>\mathrm{mod} \; |q|</math>, so there must be one element <math>c_0</math> in the set such that <math>a + bc_0 \equiv 0 \pmod q</math>; that is, <math>\frac{a + bc_0}{q}</math> is an integer. |
===Recovery of initial conditions=== | ===Recovery of initial conditions=== |
Latest revision as of 17:58, 21 May 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 a positive 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 positive 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.