차크라발라법

The chakravala method (Sanskrit: चक्रवाल विधि) is a cyclic algorithm to solve indeterminate quadratic equations, including Pell's equation. 일부에서는 자야데바(c. 950~1000CE)에 속하지만, 일반적으로 바스카라 2세(c. 1114 – 1185 CE)^[1][2]에 귀속된다.^[3] 자야데바는 브라흐마굽타의 이런 유형의 방정식 해결 접근법이 일반화될 수 있다고 지적한 뒤, 나중에 바스카라 2세가 그의 비자가니타 논문에서 다듬은 이 일반적인 방법을 설명했다. 그는 이것을 Chakravala 방법: 산스크리트어로 "바퀴"를 의미하는 Chakra라고 불렀는데, 이는 알고리즘의 주기적인 성질을 가리키는 말이다.^[4] C.-O. 셀레니우스는 바스카라 당시 유럽의 어떤 공연도 수학적 복잡성의 경이로운 높이를 넘지 못했다고 주장했다.^[1][4]

이 방법은 순환법으로도 알려져 있으며 수학적 유도의 흔적을 포함하고 있다.^[5]

역사

산스크리트어로 Chakra는 주기를 의미한다. 널리 알려진 전설에 따르면, Chakravala는 벽처럼 지구를 돌고 빛과 어둠에 의해 제한되지 않는 신화적인 산맥의 산들을 나타낸다.^[6]

628 CE의 브라마굽타는 펠의 방정식을 포함한 불확실한 2차 방정식을 연구했다.

${\displaystyle \,x^{2}=Ny^{2}+1,}$

최소 정수 x와 y의 경우 브라마굽타는 여러 N을 위해 해결할 수 있었지만 전부는 아니었다.

Jayadeva(9세기)와 Bhaskara(${\displaystyle 12세기{}^{}}$)는${\displaystyle {}^{}{}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$= ${\displaystyle 61}$y$$2 + 1, {\$displaystyle \,x$^{$2}=61y^{2}+1$,}에$$ 대해 찾는 Chakravala 방법을 사용하여 방정식에 대한 최초의 완전한 솔루션을 제공했다.

${\displaystyle \,x=1766319049,y=226153980.}$

이 사건은 난이도로 악명이 높았으며, 1657–58년 Fermat의 도전에 대응하여 유럽에서 처음으로 해결되었으며, 지속적인 분수를 사용했다. 일반적인 문제에 대한 방법은 1766년 라그랑주에 의해 완전히 엄격하게 설명되었다.^[7] 그러나 라그랑주의 방법은 61의 제곱근에 대해 21개의 연속적인 분수의 수렴을 계산해야 하는 반면, 차크라발라 방법은 훨씬 단순하다. 셀레니우스는 Chakravala 방법에 대한 평가에서 다음과 같이 말한다.

"이 방법은 최소 길이의 최적 근사 알고리즘을 나타내며, 몇 가지 최소화 특성 때문에 최소의 노력으로 많은 수를 방지하는 것이 자동으로 방정식에 대한 최선의 해결책을 산출한다. 차크라발라 방법은 유럽식 방법을 천년 이상 예상하였다. 그러나 바스카라보다 훨씬 늦은 시기에 대수학 전 분야에서 유럽의 어떤 성과도 우리 시대와 거의 대등한 것은 차크라발라의 경이로운 복잡성과 독창성을 동일시하지 않았다."^[1][4]

헤르만 한켈은 차크라발라법을 부른다.

"라그랑주 이전의 숫자 이론에서 달성한 가장 훌륭한 것"^[8]

방법

브라마굽타의 정체성으로부터, 우리는 주어진 N에 대해 관찰한다.

${\displaystyle (x_{1}x_{2}+Ny_{1}y_{2})^{2}-N(x_{1}y_{2}+x_{2}y_{1})^{2}=(x_{1}^{2}-Ny_{1}^{2})(x_{2}^{2}-Ny_{2}^{2})}$

For the equation ${\displaystyle x^{2}-Ny^{2}=k}$, this allows the "composition" (samāsa) of two solution triples ${\displaystyle (x_{1},y_{1},k_{1})}$ and ${\displaystyle (x_{2},y_{2},k_{2})}$ into a new triple

${\displaystyle (x_{1}x_{2}x_{2}y_{1}y_{2}\\,x_{1}y_{1}y_{2}+x_{2}+x_{1}y_{1}\}\,k_{1}k_{1}k_}k_{2}).}$

In the general method, the main idea is that any triple ${\displaystyle (a,b,k)}$ (that is, one which satisfies ${\displaystyle a^{2}-Nb^{2}=k}$) can be composed with the trivial triple ${\displaystyle (m,1,m^{2}-N)}$ to get the new triple ${\displaystyle (am+Nb,a+bm,k}$${\displaystyle (}$ ${\displaystyle {}^{}}$ 2${\displaystyle {}^{}}$- ${\displaystyle N}$)${\displaystyle(am$$+Nb,a+bm,k(m^{2}-N)})}$ ${\displaystyle gcd(}$ ${\displaystyle a}$, ${\displaystyle b}$)${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle \gcd(a,b)=1}$에$$대한 3중으로 시작했다고 가정하면 k로 축소할 수 있다(Bhaskara의 보조정리).

${\displaystyle a^{2}-Nb^{2}=k\오른쪽 화살표 \왼쪽({\frac {am+Nb}{k}}\오른쪽)^{2}-N\{\frac {a+bm}{k}}}^{2}={\frac {m^{2}-N}{k}}}}}{k}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

정사각형 내부의 기호는 중요하지 않기 때문에 다음과 같은 대체가 가능하다.

${\displaystyle a\frac {am+Nb}{{k}}}{{k}}},b\좌측 화살표 {\frac {a+bm}{k}}{k}}}}$

(a + bm)/k가 정수이도록 양의 정수 m을 선택한 경우, 나머지 두 숫자도 세 개의 정수인 것이다. 이러한 m 중에서 m² - N의 절대값과 그에 따른 (m² - N)/k의 절대값을 최소화하는 방법을 선택한다. 그런 다음 대체 관계는 선택한 값과 동일한 m에 적용된다. 이것은 새로운 3중(a, b, k)을 낳는다. 이 $과정$은 k${\displaystyle }$= ${\displaystyle 1}$ ${\displaystyle$ k$=1$}이$($가) 있는 세 쌍이 발견될$$ 때까지 반복된다. 이 방법은 항상 솔루션으로 종료된다(1768년 라그랑주 프로포즈).^[9] 선택적으로, 우리는 브라마굽타의 접근방식이 그러한 경우에 대한 해결책을 제공하므로 k가 ±1, ±2 또는 ±4일 때 멈출 수 있다.

브라마굽타의 구성법

In 628 AD, Brahmagupta discovered a general way to find ${\displaystyle x}$ and ${\displaystyle y}$ of ${\displaystyle x^{2}=Ny^{2}+1,}$ when given ${\displaystyle a^{2}=Nb^{2}+k}$, when k is ±1, ±2, or ±4.^[10]

k = -1

Brahmagupta의 정체성을 이용하여 스스로$$ 3중$({\displaystyle }$ ${\displaystyle a}$, b${\displaystyle }$, $){\displaystyle(a,b,k)}$을 구성한다.

${\displaystyle (a^{2}+Nb^{2})^{2}-N(2ab)^{2}}=k^{2}}:$ ${\displaystyle \Rightarrow }$ ${\displaystyle (2a^{2}-k)^{2}-N(2ab)^{2}}=k^{2}}:$

새로운 삼중수소는${\displaystyle }$(${\displaystyle {2\mathrm{}}^{}}$ a ${\displaystyle {}^{}}$ -${\displaystyle {}^{}k,}$ 2 ${\displaystyle \mathrm{a}}$ ${\displaystyle b,}$ k ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$로 $표현$될 수 있다$.$ ($2a^{2}-k, 2ab,$ k$^{2$ $k{\displaystyle }$= -${\displaystyle }$1 ${\displaysty k=-1}$로 대체하여$$ 솔루션을 구할 수 있다.

${\displaystyle x=a^{2}+1,y=2ab}$

k = ±2

다시 방정식을 사용하여${\displaystyle }$(${\displaystyle 2}$ ${\displaystyle a}$ ${\displaystyle {2\mathrm{}}^{}}$- k${\displaystyle {}^{}}$) ${\displaystyle 2{}^{}}$- ${\displaystyle {N\mathrm{}}^{}}$( ${\displaystyle 2}$ a ${\displaystyle b{}^{}}$) ${\displaystyle {2\mathrm{}}^{}}$= k ${\displaystyle {2\mathrm{}}^{}}$ ${\$$}}=k^{2$}}:$$${{\displaystyle \Rightarrow$${\displaystyle }$}(${\displaystyle \frac{{2\mathrm{}}^{}}{}}$ a${\displaystyle \frac{{}^{}}{}}$ -${\displaystyle {}^{}}$k )${\displaystyle {}^{}{2\mathrm{}}^{}}$- ${\displaystyle N}$(${\displaystyle 2\frac{\mathrm{}}{}}$ ${\displaystyle \frac{}{}{}^{}}$b )${\displaystyle {}^{}2}$ = 1 ${\displaystyle({\frac {2a^{2}-k}}}}}})^{2}-N({\frac {2}}}}}}}=1$}

${\displaystyle \mathrm{대체}}$ k${\displaystyle }$= 2 ${\displaystyle k=2$

${\displaystyle x=a^{2}-1,y=ab}$

${\displaystyle \mathrm{대체}}$ $k{\displaystyle }$=${\displaystyle }$- 2 ${\displaystyle$ k$=-2$

${\displaystyle x=a^{2}+1,y=ab}$

k = 4

Substituting ${\displaystyle k=4}$ into the equation ${\displaystyle ({\frac {2a^{2}-4}{4}})^{2}-N({\frac {2ab}{4}})^{2}=1}$ creates the triple ${\displaystyle ({\frac {a^{2}-2}{2}},{\frac {ab}{2}},1)}$.

${\displaystyle a}$이(가) 짝수인 경우 해결책:

${\displaystyle x={\frac {ab}{2}},y={\frac {a^{2}-2}}:}$

If a is odd, start with the equations ${\displaystyle ({\frac {a}{2}})^{2}-N({\frac {b}{2}})^{2}=1}$ and ${\displaystyle ({\frac {2a^{2}-4}{4}})^{2}-N({\frac {2ab}{4}})^{2}=1}$.

Leading to the triples ${\displaystyle ({\frac {a}{2}},{\frac {b}{2}},1)}$ and ${\displaystyle ({\frac {a^{2}-2}{2}},{\frac {ab}{2}},1)}$. Composing the triples gives ${\displaystyle ({\fra$$c {a}{2}}(a^{2}-3)^{2}-N({\frac {b}{2}}(a^{2}-1)^{2}=1}$

${\displaystyle a}$이(가) 홀수일 때

${\displaystyle x={\frac {a}{a}{2}}(a^{2}-3)^{2},y=({\frac {b}{2}}(a^{2}-1)^{2}}:2}}$

k = -4

When ${\displaystyle k=-4}$, then ${\displaystyle ({\frac {a}{2}})^{2}-N({\frac {b}{2}})^{2}=-1}$. Composing with itself yields ${\displaystyle ({\frac {a^{2}+Nb^{2}}{4}})^{2}-N({\frac {ab}{2}})^{2}=1}$${\displaystyle \Rightarrow }$${\displaystyle \Rightarrow }$${\displaystyle }$(${\displaystyle \frac{{}^{}}{\mathrm{}}}$ +${\displaystyle {}^{}\frac{2}{}}$ )${\displaystyle {}^{}{2\mathrm{}}^{}}$ - ${\displaystyle N}$ ${\displaystyle (\frac{b}{}}$ ${\displaystyle \frac{\mathrm{}}{}{}^{}}$) ${\displaystyle 2{}^{}}$= 1 ${\displaystyle({\frac {a^{2}+2$}){$2$$}{$2}$}}}^{2}-N({\frac$ {$ab}{2}})^{2}=1$}$$.

Again composing itself yields ${\displaystyle ({\frac {(a^{2}+2)^{2}+Na^{2}b^{2})}{4}})^{2}-N({\frac {ab(a^{2}+2)}{2}})^{2}=1}$${\displaystyle \Rightarrow }$ ${\displaystyle (\frac{a^4+4a^2+2}{2}{)}^2-N(\frac{ab(a^2+}{}}$${\displaystyle({\frac {a^{4}+4a^{2}+2}{2$$$$}}}^{2}-N({\frac {ab(a^{2}+2)}{2}})^{2}=1}$

Finally, from the earlier equations, compose the triples ${\displaystyle ({\frac {a^{2}+2}{2}},{\frac {ab}{2}},1)}$ and ${\displaystyle ({\frac {a^{4}+4a^{2}+2}{2}},{\frac {ab(a^{2}+2)}{2}},1)}$, to get

${\displaystyle ({\frac {(a^{2}+2)(a^{4}+4a^{2}+2)+Na^{2}b^{2}(a^{2}+2)}{4$$}})^{2}-N({\frac {ab(a^{4}+4a^{2}+3)}{2}})^{2}=1}$${\displaystyle \Rightarrow }$${\displaystyle ({\frac {(a^{2}+2)(a^{4}+4a^{2}+1)}{2$$}}}^{2}-N({\frac {ab(a^{2}+3)(a^{2}+1){2}{2$$}$$}})^{2}=1}$${\displaystyle \Rightarrow }$${\displaystyle ({\frac {(a^{2}+2)[(a^{2}+1)(a^{2}+3)-2)]}{2}})^{2}-N({\frac {ab(a^{2}+3)(a^{2}+1)}{2$$}})^{2}=1}$.

이것은 우리에게 해결책을 준다.

${\displaystyle x={\frac {(a^{2}+2)[(a^{2}+1)-1(a^{2}+3)-2)]{2}}y={{\frac {ab(a^{2}+3)(a^{2}+1){2}{2}}}{2}}}{2}}}}}$^[11]

(참고, $k{\displaystyle }$=${\displaystyle }$- ${\displaystyle 4}$ ${\displaystyle$ k$=-4}$는 Pell의 방정식에 대한 해결책을 찾는데 유용하지만, 항상 가장 작은 정수 쌍은 아니다. 예: ${\displaystyle {36}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ - ${\displaystyle 52{}^{}}$ 5 ${\displaystyle {2\mathrm{}}^{}}$=${\displaystyle }$- ${\displaystyle 4}$ ${\displaystyle 36^{2}-52*5^{$2}=-4$\}.$ The equation will give you ${\displaystyle x=1093436498,y=151632270}$, which when put into Pell's Equation yields ${\displaystyle 1195601955878350801-119560195587835080=1}$, which works, but so does ${\displaystyle x=649,y=90}$ for ${\displaystyle N}$${\displaystyle =}$ ${\displaystyle 52}$ $[\displaystyle N=52}$.

예

n = 61

수세기 후 페르마의 도전으로 발표된 n = 61 ${\displaystyle {케이스\mathrm{}}^{}}$(${\displaystyle 2{}^{}}$- ${\displaystyle 61}$ b ${\displaystyle {}^{}}$= $1{\displaystyle {}^{}}$ ${\displaystyle a^{2}-61b^{$2}={2}={2$}=1}$ )는 Bhaskara에 의해 예로 제시되었다.$$^[9]

${\displaystyle {2\mathrm{}}^{}}$ -${\displaystyle {}^{}61}$ ${\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$= ${\displaystyle k}$ ${\displaystyle a^{2}-61b^{2}=k}$의 솔루션으로 시작한다. In this case we can let b be 1, thus, since ${\displaystyle 8^{2}-61\cdot 1^{2}=3}$, we have the triple ${\displaystyle (a,b,k)=(8,1,3)}$. Composing it with ${\displaystyle (m,1,m^{2}-61)}$ gives the triple ${\displaystyle (8m+61,8+m,3(m^2-61}$$)$($$) {\$displaystyle (8m+61$,8$+m,3(m^{2$}-61$)\}\}$을(를) 사용하여 다음을 얻는다.

${\displaystyle \leftfr\frac {8m+61}{3},{\frac {8+m}{3},{\frac {m^{2}-61}{3}}\오른쪽).}$

For 3 to divide ${\displaystyle 8+m}$ and ${\displaystyle m^{2}-61 }$ to be minimal, we choose ${\displaystyle m=7}$, so that we have the triple ${\displaystyle (39,5,-4)}$. Now that k is −4, we can use Brahmagupta's idea: it can be scaled down to the rational solution ${\displaystyle (}$${\displaystyle (39/2,5/2,-1)\,}$, which composed with itself three times, with ${\displaystyle m={7,11,9}}$ respectively, when k becomes square and scaling can be applied, this gives ${\displaystyle (1523/2,195/2,1)\,}$. Finally, such procedure can be repea해결책이 발견될 때까지 테드(자체 합성법 9개${\displaystyle ,}$ 정사각형 표본 4개 추가 필요):${\displaystyle }$(${\displaystyle 1766319049}$, ${\displaystyle 226153980,1\mathrm{}}$ ) ${\displaystyle(1766319049,\, 226153980,\,1$ 이것은 최소 정수 솔루션이다.

n = 67

x와 y에 대해$$ $x{\displaystyle {}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$- ${\displaystyle 67}$ y ${\displaystyle 2{}^{}}$= 1 ${\displaystyle x^{2}-67y^{2}=1}$을(^[12]를) 해결한다고 가정합시다.

We start with a solution ${\displaystyle a^{2}-67b^{2}=k}$ for any k found by any means; in this case we can let b be 1, thus producing ${\displaystyle 8^{2}-67\cdot 1^{2}=-3}$. At each step, we find an m > 0 such that k divides a + bm, and m² − 67 is minimal. 그런 다음 a, b, k를 ${\displaystyle \frac{\mathrm{각각}}{}}$$$ m${\displaystyle \frac{}{}}$+ N ${\displaystyle \frac{b}{}}$ ${\displaystyle \frac{k,}{}}$ a${\displaystyle \frac{}{}}$+ ${\displaystyle \frac{b}{}}$ ${\displaystyle \frac{k}{}}$ $m$ k ${\frac$ {$am+Nb}{{k}}},{\frac {a+bm}{k}}},$ ${\displaystyle \frac{m^{}}{}}$ 2${\displaystyle \frac{{}^{}}{}}$- ${\displaystyle \frac{N}{}}$ ${\displaystyle \frac{}{}}$ ${\$로 업데이트한다.

첫 번째 반복

우리는 (${\displaystyle a}$, ${\displaystyle b}$, k${\displaystyle }$)${\displaystyle }$=${\displaystyle }$( ${\displaystyle 8}$, ${\displaystyle 1}$,${\displaystyle }$- 3${\displaystyle }$) ${\displaystyle (a,b,k)=(8,1,-3)}$을 가지고 있다$.$ 우리는 k가 a + bm, 즉 3 나누기 8 + m, m² - 67을 최소로 나누는 양의 정수 m을 원한다. The first condition implies that m is of the form 3t + 1 (i.e. 1, 4, 7, 10,… etc.), and among such m, the minimal value is attained for m = 7. Replacing (a, b, k) with ${\displaystyle \left({\frac {am+Nb}{ k }},{\frac {a+bm}{ k }},{\frac {m^{2}-N}{k}}\right)$$}$, we get the new values ${\displaystyle a=(8\cdot 7+67\cdot 1)/3=41,b=(8+1\cdot 7)/3=5,k=(7^{2}-67)/(-3)=6}$. That is, we have the new solution:

${\displaystyle 41^{2}-67\cdot (5)^{2}=6.}$

이때 순환 알고리즘의 한 라운드가 완성된다.

두 번째 반복

우리는 이제 그 과정을 반복한다. 우리는 (${\displaystyle a}$, ${\displaystyle b}$, k${\displaystyle }$)${\displaystyle }$= ${\displaystyle (}$ ${\displaystyle 41,}$ ${\displaystyle 5}$,${\displaystyle }$6${\displaystyle }$) ${\displaystyle (a,b,k)=$ ($41,5$,6$)}$을 가지고 있다$.$ 우리는 k가 a + bm, 즉 6이 41 + 5m를 나누고 m² - 67이 최소인 m > 0을 원한다. 첫 번째 조건은 m이 6t + 5 형태(즉, 5, 11, 17,… 등)라는 것을 의미하며, 이러한² m 중 m - 67은 m = 5에 대해 최소값이다. 이는 새로운 솔루션 a = (41415 + 67⋅5)/6 등으로 이어진다.

${\displaystyle 90^{2}-67\cdot 11^{2}=-7.}$

제3회 반복

7이 90 + 11m를 나누려면 m = 2 + 7t(즉, 2, 9, 16, 등)이 있어야 하며, 이러한 m 중에서 m = 9를 선택한다.

${\displaystyle 221^{2}-67\cdot 27^{2}=-2.}$

최종 솔루션

이 시점에서는 순환법을 계속할 수 있지만(그리고 그것은 7회 반복 후에 끝날 것이다), 오른쪽이 ±1, ±2, ±4에 속하므로 브라만굽타의 관찰도 직접 사용할 수 있다. 스스로 삼단(221, 27, -2)을 구성하면, 우리는 그것을 얻는다.

${\displaystyle \left({\frac {n2}+67\cdot 27^{2}}:\오른쪽)^{2}-67\cdot (cdot 27)^{2}=1,}$

즉, 다음과 같은 정수 솔루션을 사용할 수 있다.

${\displaystyle 48842^{2}-67\cdot 5967^{2}=1.}$

이 방정식은 약 ${\$을(를) ${\displaystyle \frac{48842}{}}$ ${\displaystyle \frac{5967}{}}$ ${\$과(와) 같으며$$ 약 $2{\displaystyle \mathrm{}\times }$ ${\displaystyle {10}^{}}$- ${\displaystyle 9^{}}$ ${\$}}}의 여백 9$}$에 해당한다$.$

메모들

참조

• 플로리안 카조리(1918), 이름의 유래 "수학적 유도", The American Mathematical Monthly 25 (5) 페이지 197-201.
• 조지 게베르헤스 요셉, 공작의 산마루: 수학의 비유럽적 뿌리 (1975년)
• G. R. 케이, "인도 수학", 이시스 2:2 (1919), 페이지 326–356.
• Class-Olaf Selenius, "Jayadeva와 Bhaskara II의 차크라발라 과정의 Rationale", Historyia Mathematica 2(1975), 페이지 167–184.
• 클라스-올라프 셀레니우스, "케텐브루크테오레티슈 에르클라룽 데르 지클리스첸 마데" 주르 뢰성 데르 바스카라-펠-글리청", 액타 아카데미. 아보. 수학. 물리 23 (10) (1963), 페이지 1-44.
• 호이베르크, 데일 & 람찬다니, 인두(2000년) 학생들의 브리태니카 인도. 뭄바이: 인기 있는 프라카산. ISBN 0-85229-760-2
• 고나틸레이크, 수잔타(1998년). 글로벌 과학을 향해: 문명 지식 채굴. 인디애나: 인디애나 대학교 출판부 ISBN 0-253-3388-1.
• 쿠마르, 나렌드라(2004) 고대 인도의 과학. 델리: 안몰 출판사 Pvt Ltd. ISBN 81-261-2056-8
• 플로커, 김(2007) "인도에서의 수학" 이집트, 메소포타미아, 중국, 인도, 이슬람의 수학: 뉴저지 소스북: 프린스턴 대학교 출판부. ISBN 0-691-11485-4
• Edwards, Harold (1977). Fermat's Last Theorem. New York: Springer. ISBN 0-387-90230-9.

외부 링크

• Chakravala