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
During AMC testing, the AoPS Wiki is in read-only mode and no edits can be made.

Chakravala method

Revision as of 21:03, 2 March 2023 by Orange quail 9 (talk | contribs) (Temporary save.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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+bD}{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 a + bc - (a + bc') = b(c - c').\] Because $\gcd(q,b) = 1$, $q$ also divides $c - c'$, so $c \equiv c' \pmod q$.

We can construct a set of $q$ possible integer values of $c$, none congruent to another $\mod q$; the corresponding values of $a + bc$ take all $q$ distinct values $\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$.

Evaluation

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

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