Difference between revisions of "Chakravala method"
(Completed method of composition information.) |
(→Method of composition: Corrected for the case where q is negative) |
||
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 <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 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 24: | Line 24: | ||
</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 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 | + | For the second claim, we prove that <math>\gcd(q\alpha,q\beta) = |q|</math>. Suppose that a positive 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>. | + | 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=== |
Revision as of 11:05, 3 March 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 an 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 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.