Chakravala method

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

  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 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.