Difference between revisions of "Chakravala method"
(Temporary save.) |
m (Fixed article to indicate that c must be positive.) |
||
(3 intermediate revisions by the same user not shown) | |||
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+ | + | <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 13: | Line 13: | ||
Because <math>\gcd(a,b) = 1</math>, we have <math>\gcd(a^2,b) = 1</math>, so <cmath>\gcd(q,b) = \gcd(a^2-Db^2,b) = 1.</cmath> | Because <math>\gcd(a,b) = 1</math>, we have <math>\gcd(a^2,b) = 1</math>, so <cmath>\gcd(q,b) = \gcd(a^2-Db^2,b) = 1.</cmath> | ||
− | Suppose <math>a + bc \equiv a + bc' \pmod q</math>. Then < | + | 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 construct a set of <math>q</math> possible integer values of <math>c</math>, none congruent to another <math>\mod q</math>; the corresponding values of <math>a + bc</math> take all <math>q</math> distinct values <math>\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=== | ||
Line 23: | Line 23: | ||
<li><math>\gcd(\alpha, \beta) = 1</math>. | <li><math>\gcd(\alpha, \beta) = 1</math>. | ||
</ol> | </ol> | ||
+ | |||
+ | For the first claim, we use the fact that <math>\beta</math> is an integer to conclude that <math>a \equiv -bc \pmod{|q|}</math>. Therefore, <cmath>a(-bc) - Db^2 \equiv a^2 - Db^2 \pmod{|q|}.</cmath> The right-hand side of the above congruence is <math>q</math>; the left side is <math>-b(ac+Db) = -bq\alpha</math>. Because <math>-bq\alpha</math> is a multiple of <math>q</math> and <math>\gcd(q,b) = 1</math>, <math>-q\alpha</math> is also a multiple of <math>q</math>. Thus, <math>\alpha</math> is an integer. | ||
+ | |||
+ | For the second claim, we prove that <math>\gcd(q\alpha,q\beta) = |q|</math>. Suppose that a positive integer <math>k</math> divides both <math>q\alpha</math> and <math>q\beta</math>. | ||
+ | Similarly to before, we consider <math>-bq\alpha = -b(ac+Db) = a(-bc) - Db^2</math> and use the assumption that <math>q\beta</math> is a multiple of <math>k</math> to make the substitution <math>a \equiv -bc \pmod k</math>, obtaining <cmath>-bq\alpha \equiv a^2 - Db^2 \pmod k.</cmath> But <math>-bq\alpha</math> is a multiple of <math>k</math>, so <math>a^2 - Db^2 = q</math> is also a multiple of <math>k</math>. Thus, <math>k</math> is a divisor of <math>|q|</math>. | ||
===Evaluation=== | ===Evaluation=== | ||
We now claim that <math>\alpha^2 - D\beta^2 = \frac{c^2-D}{q}</math>. | We now claim that <math>\alpha^2 - D\beta^2 = \frac{c^2-D}{q}</math>. | ||
+ | |||
+ | 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. | ||
+ | |||
+ | ==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. |
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.