チャクラヴァラ法

Cyclic algorithm to solve indeterminate quadratic equations

チャクラヴァラ法（サンスクリット語：चक्रवाल विधि ）は、ペル方程式を含む不定二次方程式を解く巡回アルゴリズムである。一般的にはバースカラ2世（西暦1114年頃 – 1185年）^{[1] [2]の作とされているが、}ジャヤデーヴァ（西暦950年頃 ~ 1000年）の作とする説もある。 ^{[3]ジャヤデーヴァは、この種の方程式を解く}ブラフマグプタの手法は一般化できると指摘し、この一般化手法について説明し、その後バースカラ2世が著書『ビジャガニタ』でこれを改良した。彼はこれをチャクラヴァラ法と呼んだ。チャクラはサンスクリット語で「車輪」を意味し、アルゴリズムの巡回的な性質を指している。^[4] C.-O.セレニウスは、バースカラの時代もその後も、ヨーロッパのどの演奏もその驚異的な数学的複雑さの頂点を越えることはなかったと主張した。^{[1] [4]}

この方法は巡回法としても知られており、数学的帰納法の痕跡が含まれています。^[5]

歴史

サンスクリット語でチャクラは循環を意味します。一般的な伝説によると、チャクラヴァラは光と闇に制限されずに地球の周りを壁のように周回する神話上の山脈を指します。^[6]

628年にブラフマグプタはペル方程式を含む不定二次方程式を研究した。

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

最小の整数xとyについて。Brahmagupta はいくつかのNについてこれを解くことができましたが、すべてではありませんでした。

ジャヤデーヴァとバースカラは、チャクラヴァラ法を用いてこの方程式の最初の完全な解を提示した。 ${\displaystyle \,x^{2}=61y^{2}+1,}$

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

この問題は難解であることで有名で、ヨーロッパでは1657年から1658年にかけて、フェルマーの挑戦を受けてブラウンカーが連分数を用いて初めて解決しました。この問題の一般解法は、1766年にラグランジュによって初めて完全に厳密に記述されました^{。[7]しかし、ラグランジュの方法で61の平方根を求めるには、}単純連分数の収束式を10回（よく主張される21回ではなく、10回の反復で解が得られ、それを2乗することで残りの11回の反復を省くことができるため）計算する必要があります。一方、チャクラヴァラ法ははるかに簡単です。セレニウスはチャクラヴァラ法の評価の中で次のように述べています。 ${\displaystyle \,29718^{2}=61*3805^{2}-1,}$

この方法は、いくつかの最小化特性により、最小限の労力で、大きな数値を回避しながら、方程式の最良の解を自動的に生成する、最小長の最良近似アルゴリズムである。チャクラヴァラ法は、ヨーロッパの方法を1000年以上も先取りしていた。しかし、バースカラよりずっと後の時代、いや、現代に至るまで、代数学の分野全体において、チャクラヴァラの驚異的な複雑さと独創性に匹敵するヨーロッパの業績はなかった。^{[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})}$

方程式の場合、2つの解のトリプルとを新しいトリプルに「合成」（サマサ）することができます。 ${\displaystyle x^{2}-Ny^{2}=k}$ ${\displaystyle (x_{1},y_{1},k_{1})}$ ${\displaystyle (x_{2},y_{2},k_{2})}$

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

一般的な手法では、任意の3つ組（つまり、 を満たすもの）を自明な3つ組と合成することで、任意のmに対する新しい3つ組が得られるという考え方です。 を満たす3つ組から始めたと仮定すると、これはkだけ縮小できます（これはバースカラの補題です）。 ${\displaystyle (a,b,k)}$ ${\displaystyle a^{2}-Nb^{2}=k}$ ${\displaystyle (m,1,m^{2}-N)}$ ${\displaystyle (am+Nb,a+bm,k(m^{2}-N))}$ ${\displaystyle \gcd(a,b)=1}$

${\displaystyle a^{2}-Nb^{2}=k\Rightarrow \left({\frac {am+Nb}{k}}\right)^{2}-N\left({\frac {a+bm}{k}}\right)^{2}={\frac {m^{2}-N}{k}}}$

四角の中の符号は重要ではないので、次のような置き換えが可能です。

${\displaystyle a\leftarrow {\frac {am+Nb}{|k|}},b\leftarrow {\frac {a+bm}{|k|}},k\leftarrow {\frac {m^{2}-N}{k}}}$

正の整数m を選択して ( a  +  bm )/ kが整数になると、組の中の他の2つの数も整数になります。そのようなmの中から、この方法ではm ²  −  Nの絶対値を最小化し、したがって ( m ²  −  N )/ kの絶対値を最小化するものが選ばれます。次に、選ばれた値に等しいmに対して置換関係が適用されます。これにより、新しい組 ( a , b , k ) が得られます。このプロセスは、次の式を満たす組が見つかるまで繰り返されます。この方法は常に解で終了し、これは1768年にラグランジュによって証明されています。^{[9]オプションとして、} kが ±1、±2、または ±4 の場合に Brahmagupta のアプローチが解を与えるため、その場合に停止することもできます。 ^[要出典] ${\displaystyle k=1}$

ブラフマグプタの作曲法

西暦628年、ブラフマグプタは、kが±1、±2、または±4のときに、が与えられたときのとを求める一般的な方法を発見しました。 ^[10] ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x^{2}=Ny^{2}+1,}$ ${\displaystyle a^{2}=Nb^{2}+k}$

k= ±1

Brahmagupta の恒等式を使用して、三つ組をそれ自身と合成します。 ${\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 (2a^{2}-k,2ab,k^{2})}$

代入すると解が得られます: ${\displaystyle k=-1}$

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

については、元の解はすでに解でした。代入すると2番目の解が得られます。 ${\displaystyle k=1}$ ${\displaystyle (a,b)}$ ${\displaystyle k=1}$

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

k= ±2

再びこの式を使って、 ${\displaystyle (2a^{2}-k)^{2}-N(2ab)^{2}=k^{2}}$ ${\displaystyle \Rightarrow }$ ${\displaystyle \left({\frac {2a^{2}-k}{k}}\right)^{2}-N\left({\frac {2ab}{k}}\right)^{2}=1}$

代入すると、 ${\displaystyle k=2}$

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

代入すると、 ${\displaystyle k=-2}$

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

k= 4

式に代入すると、3つの ${\displaystyle k=4}$ ${\displaystyle \left({\frac {2a^{2}-k}{k}}\right)^{2}-N\left({\frac {2ab}{k}}\right)^{2}=1}$ ${\displaystyle \left({\frac {a^{2}-2}{2}},{\frac {ab}{2}},1\right),}$

が偶数の場合、これは解です。 ${\displaystyle a}$

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

aが奇数の場合は、方程式とから始めます。 ${\displaystyle \left({\frac {a}{2}}\right)^{2}-N\left({\frac {b}{2}}\right)^{2}=1}$ ${\displaystyle \left({\frac {2a^{2}-4}{4}})^{2}-N({\frac {2ab}{4}}\right)^{2}=1}$

三つ組と に至る。三つ組を合成すると ${\displaystyle \left({\frac {a}{2}},{\frac {b}{2}},1\right)}$ ${\displaystyle \left({\frac {a^{2}-2}{2}},{\frac {ab}{2}},1\right)}$ ${\displaystyle \left({\frac {a}{2}}(a^{2}-3)\right)^{2}-N\left({\frac {b}{2}}(a^{2}-1)\right)^{2}=1}$

奇数の場合は、 ${\displaystyle a}$

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

k= −4

のとき、 。それ自身と合成すると となる ${\displaystyle k=-4}$ ${\displaystyle \left({\frac {a}{2}}\right)^{2}-N\left({\frac {b}{2}}\right)^{2}=-1}$ ${\displaystyle \left({\frac {a^{2}+Nb^{2}}{4}}\right)^{2}-N\left({\frac {ab}{2}}\right)^{2}=1}$ ${\displaystyle \Rightarrow }$ ${\displaystyle \left({\frac {a^{2}+2}{2}}\right)^{2}-N\left({\frac {ab}{2}}\right)^{2}=1}$

再び構成すると ${\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}+2)}{2}})^{2}=1}$

最後に、前の式から、三つ組とを合成して、 ${\displaystyle ({\frac {a^{2}+2}{2}},{\frac {ab}{2}},1)}$ ${\displaystyle ({\frac {a^{4}+4a^{2}+2}{2}},{\frac {ab(a^{2}+2)}{2}},1)}$

${\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}=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)(a^{2}+3)-2]}{2}},\qquad y={\frac {ab(a^{2}+3)(a^{2}+1)}{2}}}$^[11]

(注意:はペル方程式 の解を求めるのに役立ちますが、常に最小の整数ペアになるわけではありません。例: 。方程式 は を与え、これをペル方程式に代入すると となり、これは有効ですが、 の場合も同様に有効です。 ${\displaystyle k=-4}$ ${\displaystyle 36^{2}-52\cdot 5^{2}=-4}$ ${\displaystyle x=1093435849,y=151632270}$ ${\displaystyle 1195601955878350801-1195601955878350800=1}$ ${\displaystyle x=649,y=90}$ ${\displaystyle N=52}$

例

n= 61

何世紀も後にフェルマーが挑戦状を叩きつけたn = 61の場合 （を満たす整数解を求める）は、バースカラによって例として示されました。^[9] ${\displaystyle a^{2}-61b^{2}=1}$

あらゆる手段で得られた任意のkに対する解から始めます。この場合、b を1 とすることができるので、 なので、3 つの が得られます。これを と合成すると3 つの が得られ、これを縮小（またはBhaskara の補題を直接適用）すると、次のようになります。 ${\displaystyle a^{2}-61b^{2}=k}$ ${\displaystyle 8^{2}-61\cdot 1^{2}=3}$ ${\displaystyle (a,b,k)=(8,1,3)}$ ${\displaystyle (m,1,m^{2}-61)}$ ${\displaystyle (8m+61,8+m,3(m^{2}-61))}$

${\displaystyle \left({\frac {8m+61}{3}},{\frac {8+m}{3}},{\frac {m^{2}-61}{3}}\right).}$

3 を割り切って最小値にするには、を選択して3 重 を得る。k が −4 になったので、Brahmagupta の考え方を使うことができる。つまり、は有理解 にスケールダウンでき、これはそれぞれ と 3 回自身を合成する。k が平方になり、スケーリングを適用できる場合、 が得られる。最終的に、この手順を解が見つかるまで繰り返すことができる（さらに 9 回の自己合成と 4 回の平方スケーリングが必要）。これが最小の整数解である。 ${\displaystyle 8+m}$ ${\displaystyle |m^{2}-61|}$ ${\displaystyle m=7}$ ${\displaystyle (39,5,-4)}$ ${\displaystyle (39/2,5/2,-1)\,}$ ${\displaystyle m={7,11,9}}$ ${\displaystyle (1523/2,195/2,1)\,}$ ${\displaystyle (1766319049,\,226153980,\,1)}$

n= 67

xとyについて解くとします。^[12] ${\displaystyle x^{2}-67y^{2}=1}$

任意のkに対する解を何らかの方法で求め、そこから始めます。この場合、 b を1 とすることでが得られます。各ステップにおいて、 k がa  +  bmを割り切り、| m ² − 67| が最小となる ようなm > 0を見つけます。次に、 a、b、k をそれぞれとに 更新します。 ${\displaystyle a^{2}-67b^{2}=k}$ ${\displaystyle 8^{2}-67\cdot 1^{2}=-3}$ ${\displaystyle {\frac {am+Nb}{|k|}},{\frac {a+bm}{|k|}}}$ ${\displaystyle {\frac {m^{2}-N}{k}}}$

最初の反復

となります。kがa  +  bmを割り切る、つまり 3 が 8 + m を割り切り、| m ² − 67| が最小となるような正の整数mを求めます 。最初の条件は、mが 3 t + 1 （つまり 1、4、7、10、… など）の形であることを意味し、そのようなmの中で、最小値はm = 7 で達成されます。( a ,  b ,  k ) を に置き換えると、新しい値が得られます。つまり、新しい解は次のようになります ${\displaystyle (a,b,k)=(8,1,-3)}$ ${\displaystyle \left({\frac {am+Nb}{|k|}},{\frac {a+bm}{|k|}},{\frac {m^{2}-N}{k}}\right)}$ ${\displaystyle a=(8\cdot 7+67\cdot 1)/3=41,b=(8+1\cdot 7)/3=5,k=(7^{2}-67)/(-3)=6}$

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

この時点で、巡回アルゴリズムの 1 ラウンドが完了します。

2回目の反復

この手順を繰り返します。kがa  +  bmを割り切る、つまり6が41 + 5 mを割り切り、| m ² − 67|が最小となる ようなm > 0を求めます 。最初の条件は、mが6 t  + 5（つまり5、11、17、…など）の形であることを意味し、そのようなmの中で、| m ²  − 67|はm  = 5に対して最小です。これにより、新しい解が導き出されます ${\displaystyle (a,b,k)=(41,5,6)}$ ${\displaystyle {\frac {41\cdot 5+61\cdot 5}{6}}}$

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

3回目の繰り返し

7で90 + 11 mを割り切るには、 m = 2 + 7 t（つまり、2、9、16、…など）でなければなりません。そのようなmの中から、m = 9を 選びます

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

最終解

この時点で巡回法を続けることもできます（7回の反復で終了します）。しかし、右辺は±1、±2、±4のいずれかであるため、Brahmaguptaの観察を直接使用することもできます。3つの数（221、27、-2）をそれ自身と合成すると、次のようになります

${\displaystyle \left({\frac {221^{2}+67\cdot 27^{2}}{2}}\right)^{2}-67\cdot (221\cdot 27)^{2}=1,}$

つまり、整数解が得られます。

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

この式は、約 の範囲内で を と 近似します。 ${\displaystyle {\sqrt {67}}}$ ${\displaystyle {\frac {48842}{5967}}}$ ${\displaystyle 2\times 10^{-9}}$

注釈

1. ホイバーグ＆ラムチャンダニ – 学生向けブリタニカ・インド版：バースカラチャリヤ II、200ページ
2. クマール、23ページ
3. プロフカー、474ページ
4. Goonatilake、127～128ページ
5. カジョリ（1918年）、197ページ

   「数学的帰納法」と呼ばれる推論法は、いくつかの独立した起源を持っています。その起源は、スイスのヤコブ（ジェームズ）・ベルヌーイ、フランスのB・パスカルとP・フェルマー、そしてイタリアのF・マウロリュクスにまで遡ります。[...] 少し行間を読むと、数学的帰納法の痕跡は、さらに古く、ヒンドゥー教徒やギリシャ人の著作の中に見出すことができます。例えば、バースカラの「巡回法」や、ユークリッドによる素数の無限数の証明などです。

6. ゴパル・マダン（1990年）KS・ゴータム編『インドの変遷』インド政府情報放送省出版局、79頁。
7. オコナー、ジョン・J.、ロバートソン、エドマンド・F.、「ペルの方程式」、MacTutor数学史アーカイブ、セントアンドリュース大学
8. ケイ（1919）、337ページ。
9. ジョン・スティルウェル(2002)、『数学とその歴史』（第2版）、シュプリンガー、pp.  72– 76、ISBN 978-0-387-95336-6
10. 「ペルの方程式」。数学史。2021年6月14日閲覧
11. Datta and Singh (1962). 『ヒンドゥー数学の歴史：資料集 パートIとパートII』アジア出版社. pp.  157– 160. ISBN 8180903907。 {{cite book}}: ISBN / Date incompatibility (help)
12. このセクションの例は、（k、mなどの表記とともに） Michael J. Jacobson、Hugh C. Williams (2009)『Solving the Pell equation』Springer、31ページ、ISBNに掲載されています ${\displaystyle Q_{n}}$ ${\displaystyle P_{n}}$ 978-0-387-84922-5

参考文献

• フロリアン・カジョリ（1918）、「数学的帰納法」という名前の由来、アメリカ数学月刊誌 25（5）、pp.197-201。
• ジョージ・ゲヴェルゲーズ・ジョセフ『孔雀の紋章：数学の非ヨーロッパ的ルーツ』（1975 年）。
• GR Kaye、「インドの数学」、Isis 2 :2（1919）、pp.326–356。
• Clas-Olaf Selenius、「JayadevaとBhaskara IIのチャクラヴァラ過程の理論的根拠」Wayback Machineに2021年11月30日アーカイブ、Historia Mathematica 2（1975）、pp. 167–184。
• Clas-Olaf Selenius、「Kettenbruchtheoretische Erklärung der zyklischen Methode zur Lösung der Bhaskara-Pell-Gleichung」、Acta Acad。阿保。数学。物理学。 23 (10) (1963)、1 ～ 44 ページ。
• ホイバーグ、デール、ラムチャンダニ、インドゥ (2000)。学生のブリタニカ・インド。ムンバイ：人気のプラカシャン。ISBN 0-85229-760-2
• グーナティレイク、スザンサ（1998年）『グローバル科学に向けて：文明の知識の発掘』インディアナ州：インディアナ大学出版局、ISBN 0-253-33388-1。
• クマール、ナレンドラ（2004年）『古代インドの科学』デリー：アンモル出版ISBN 81-261-2056-8
• プローカー、キム（2007）「インドの数学」『エジプト、メソポタミア、中国、インド、イスラムの数学：資料集』ニュージャージー州：プリンストン大学出版局、ISBN 0-691-11485-4
• エドワーズ、ハロルド (1977).フェルマーの最終定理. ニューヨーク:シュプリンガー. ISBN 0-387-90230-9。

外部リンク

• チャクラヴァラ入門

Retrieved from "https://en.wikipedia.org/w/index.php?title=Chakravala_method&oldid=1320441480"