Difference between revisions of "Chakravala method"
(Added summary of the algorithm.) |
m (Fixed article to indicate that c must be positive.) |
||
Line 4: | Line 4: | ||
We let <math>a</math> and <math>b</math> be integers such that <math>\gcd(a,b) = 1</math>, and we notate <math>a^2 - Db^2 = q</math>. | We let <math>a</math> and <math>b</math> be integers such that <math>\gcd(a,b) = 1</math>, and we notate <math>a^2 - Db^2 = q</math>. | ||
− | We then choose | + | We then choose a positive integer <math>c</math> and let |
<cmath>\begin{align*} \alpha &= \frac{ac+Db}{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 15: | Line 15: | ||
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 positive 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=== |
Latest revision as of 16:58, 21 May 2023
The chakravala method is an algorithm for solving the Pell equation
Contents
[hide]Method of composition
We let and be integers such that , and we notate .
We then choose a positive integer and let
Existence of suitable choice
We claim that it is always possible to choose such that is an integer.
Because , we have , so
Suppose . Then . Because , also divides , so .
We can therefore construct a set of possible positive integer values of , none congruent to another ; the corresponding values of take all distinct values , so there must be one element in the set such that ; that is, is an integer.
Recovery of initial conditions
We further claim that if is an integer, then
- is also an integer, and
- .
For the first claim, we use the fact that is an integer to conclude that . Therefore, The right-hand side of the above congruence is ; the left side is . Because is a multiple of and , is also a multiple of . Thus, is an integer.
For the second claim, we prove that . Suppose that a positive integer divides both and . Similarly to before, we consider and use the assumption that is a multiple of to make the substitution , obtaining But is a multiple of , so is also a multiple of . Thus, is a divisor of .
Evaluation
We now claim that .
From Brahmagupta's Identity (with and ) we have That is, Dividing both sides by gives the desired result.
Algorithm
We begin by choosing initial relatively prime integers and . At each step, we choose the value of that minimizes (among the values of for which is an integer) and replace the values of and with the resulting values of and . Repeating this step, the value of eventually reaches , yielding a solution to the Pell equation.