Difference between revisions of "Chakravala method"

Revision as of 11:05, 3 March 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 an 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 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.

@@ 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 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===

Page

Toolbox

Search