Difference between revisions of "Chakravala method"

Latest revision as of 16:58, 21 May 2023

The chakravala method is an algorithm for solving the Pell equation $x^2 - Dy^2 = 1.$

Method of composition

We let $a$ and $b$ be integers such that $\gcd(a,b) = 1$ , and we notate $a^2 - Db^2 = q$ .

We then choose a positive integer $c$ and let $\begin{align*} \alpha &= \frac{ac+Db}{q}, \\ \beta &= \frac{a+bc}{q}.\\ \end{align*}$

Existence of suitable choice

We claim that it is always possible to choose $c$ such that $\beta$ is an integer.

Because $\gcd(a,b) = 1$ , we have $\gcd(a^2,b) = 1$ , so $\gcd(q,b) = \gcd(a^2-Db^2,b) = 1.$

Suppose $a + bc \equiv a + bc' \pmod{|q|}$ . Then $q \mid b(c - c')$ . Because $\gcd(q,b) = 1$ , $q$ also divides $c - c'$ , so $c \equiv c' \pmod{|q|}$ .

We can therefore construct a set of $q$ possible positive integer values of $c$ , none congruent to another $\mathrm{mod} \; |q|$ ; the corresponding values of $a + bc$ take all $|q|$ distinct values $\mathrm{mod} \; |q|$ , so there must be one element $c_0$ in the set such that $a + bc_0 \equiv 0 \pmod q$ ; that is, $\frac{a + bc_0}{q}$ is an integer.

Recovery of initial conditions

We further claim that if $\beta$ is an integer, then

$\alpha$ is also an integer, and
$\gcd(\alpha, \beta) = 1$ .

For the first claim, we use the fact that $\beta$ is an integer to conclude that $a \equiv -bc \pmod{|q|}$ . Therefore, $a(-bc) - Db^2 \equiv a^2 - Db^2 \pmod{|q|}.$ The right-hand side of the above congruence is $q$ ; the left side is $-b(ac+Db) = -bq\alpha$ . Because $-bq\alpha$ is a multiple of $q$ and $\gcd(q,b) = 1$ , $-q\alpha$ is also a multiple of $q$ . Thus, $\alpha$ is an integer.

For the second claim, we prove that $\gcd(q\alpha,q\beta) = |q|$ . Suppose that a positive integer $k$ divides both $q\alpha$ and $q\beta$ . Similarly to before, we consider $-bq\alpha = -b(ac+Db) = a(-bc) - Db^2$ and use the assumption that $q\beta$ is a multiple of $k$ to make the substitution $a \equiv -bc \pmod k$ , obtaining $-bq\alpha \equiv a^2 - Db^2 \pmod k.$ But $-bq\alpha$ is a multiple of $k$ , so $a^2 - Db^2 = q$ is also a multiple of $k$ . Thus, $k$ is a divisor of $|q|$ .

Evaluation

We now claim that $\alpha^2 - D\beta^2 = \frac{c^2-D}{q}$ .

From Brahmagupta's Identity (with $n = -D$ and $d = 1$ ) we have $(ac+Db)^2 - D(a+bc)^2 = (a^2-Db^2)(c^2-D).$ That is, $(q\alpha)^2 - D(q\beta)^2 = q(c^2-D).$ Dividing both sides by $q^2$ gives the desired result.

Algorithm

We begin by choosing initial relatively prime integers $a$ and $b$ . At each step, we choose the value of $c$ that minimizes $|c^2 - D|$ (among the values of $c$ for which $\beta$ is an integer) and replace the values of $a$ and $b$ with the resulting values of $\alpha$ and $\beta$ . Repeating this step, the value of $q$ eventually reaches $1$ , yielding a solution to the Pell equation.

@@ 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 then choose an integer <math>c</math> and let
+We then choose a positive integer <math>c</math> and let
 <cmath>\begin{align*} \alpha &= \frac{ac+Db}{q}, \\
 \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>
-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===
@@ Line 24: / Line 24: @@
 </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 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 an integer <math>k</math> divides both <math>q\alpha</math> and <math>q\beta</math>.
+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>.
+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===
@@ 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>
 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.

Page

Toolbox

Search