Difference between revisions of "Chakravala method"

(Temporary save.)
 
(Completed method of composition information.)
Line 5: Line 5:
  
 
We then choose an integer <math>c</math> and let
 
We then choose an integer <math>c</math> and let
<cmath>\begin{align*} \alpha &= \frac{ac+bD}{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 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 <cmath>q \mid a + bc - (a + bc') = b(c - c').</cmath> 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 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 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 an 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.

Revision as of 22:25, 2 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

  1. $\alpha$ is also an integer, and
  2. $\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 an 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.