Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Chakravala method

Revision as of 22:25, 2 March 2023 by Orange quail 9 (talk | contribs) (Completed method of composition information.)

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Chakravala_method&oldid=190534"