معادلة بيل

في وقت مبكر يعود إلى عام 400 قبل الميلاد في الهند واليونان ، درس علماء الرياضيات الأعداد الناتجة عن حالة n  =  2 من معادلة بيل، $${\displaystyle x^{2}-2y^{2}=1,}$$ ومن المعادلة ذات الصلة الوثيقة $${\displaystyle x^{2}-2y^{2}=-1}$$ بسبب ارتباط هذه المعادلات بالجذر التربيعي للعدد 2. [ ^{5 ] في} الواقع، إذا كان x و y عددين صحيحين موجبين يحققان هذه المعادلة، فإن x / y هو تقريب للجذر التربيعي للعدد 2. كان العددان x و y اللذان يظهران في هذه التقريبات، واللذان يُطلق عليهما عددا الضلع والقطر ، معروفين لدى الفيثاغوريين ، ولاحظ بروكلس أنه في الاتجاه المعاكس، يخضع هذان العددان لإحدى هاتين المعادلتين. ^{[ 5 ]} وبالمثل، اكتشف بودايانا أن x = 17، y = 12 و x = 577، y = 408 هما حلان لمعادلة بيل، وأن 17/12 و 577/408 هما تقريبان دقيقان جدًا للجذر التربيعي للعدد 2. ^{[ 6 ]}

لاحقًا، قدّر أرخميدس الجذر التربيعي للعدد 3 بالعدد النسبي 1351/780. ورغم أنه لم يشرح طريقته، إلا أنه يمكن الحصول على هذا التقريب بنفس الطريقة، كحل لمعادلة بيل. ^{[ 5 ]} وبالمثل، يمكن حل مسألة أبقار أرخميدس - وهي مسألة كلامية قديمة تتعلق بإيجاد عدد الأبقار التابعة لإله الشمس هيليوس - بإعادة صياغتها كمعادلة بيل. تشير المخطوطة التي تحتوي على المسألة إلى أن أرخميدس هو من ابتكرها وسجلها في رسالة إلى إراتوستينس ، ^{[ 7 ]} ويُعتبر نسبها إلى أرخميدس مقبولًا على نطاق واسع اليوم. ^{[ 8 ] [ 9 ]}

حوالي عام 250 م، نظر ديوفانتوس في المعادلة $${\displaystyle a^{2}x^{2}+c=y^{2},}$$ حيث a و c عددان ثابتان، و x و y المتغيران المطلوب إيجاد قيمهما. تختلف هذه المعادلة في شكلها عن معادلة بيل، لكنها مكافئة لها. حلّ ديوفانتوس المعادلة لإيجاد قيم ( a , c ) التي تساوي (1, 1)، (1, -1)، (1, 12)، و (3, 9). وقد عمل الكرجي ، وهو عالم رياضيات فارسي من القرن العاشر، على مسائل مشابهة لتلك التي تناولها ديوفانتوس. ^{[ 10 ]}     

في الرياضيات الهندية، اكتشف براهماجوبتا أن$${\displaystyle (x_{1}^{2}-Ny_{1}^{2})(x_{2}^{2}-Ny_{2}^{2})=(x_{1}x_{2}+Ny_{1}y_{2})^{2}-N(x_{1}y_{2}+x_{2}y_{1})^{2},}$$ شكلٌ مما يُعرف الآن بهوية براهمغوبتا . وباستخدام هذا، تمكن من "تأليف" ثلاثيات.${\displaystyle (x_{1},y_{1},k_{1})}$و${\displaystyle (x_{2},y_{2},k_{2})}$تلك كانت حلولاً لـ${\displaystyle x^{2}-Ny^{2}=k}$، لتوليد الثلاثيات الجديدة

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

لم يقتصر الأمر على توفير طريقة لتوليد عدد لا نهائي من الحلول لـ${\displaystyle x^{2}-Ny^{2}=1}$بدءًا من حل واحد، ولكن أيضًا، عن طريق قسمة هذا التركيب على${\displaystyle k_{1}k_{2}}$في كثير من الأحيان، يمكن الحصول على حلول صحيحة أو "شبه صحيحة". على سبيل المثال، بالنسبة لـ${\displaystyle N=92}$قام براهماجوبتا بتأليف الثلاثية (10،  1،  8) (منذ${\displaystyle 10^{2}-92(1^{2})=8}$) مع نفسها للحصول على الثلاثية الجديدة (192،  20،  64). القسمة على 64 ("8" لـ${\displaystyle x}$و${\displaystyle y}$أعطت هذه الطريقة الثلاثية (24،  5/2،  1)، والتي عند تركيبها مع نفسها أعطت الحل الصحيح المطلوب (1151،  120،  1). وقد حلّ براهمغوبتا العديد من معادلات بيل بهذه الطريقة، مُثبتًا أنها تُعطي حلولًا بدءًا من حل صحيح لـ${\displaystyle x^{2}-Ny^{2}=k}$لـ k = ±1، ±2، أو ±4. ^{[ 11 ]}

أول طريقة عامة لحل معادلة بيل (لجميع قيم N ) قدمها بهاسكارا الثاني عام 1150، موسعًا بذلك طرق براهمغوبتا. تُسمى هذه الطريقة طريقة تشاكرافالا (الدورية) ، وتبدأ باختيار عددين صحيحين أوليين نسبيًا.${\displaystyle a}$و${\displaystyle b}$ثم تأليف الثلاثية${\displaystyle (a,b,k)}$(أي الذي يرضي${\displaystyle a^{2}-Nb^{2}=k}$) مع الثلاثية التافهة${\displaystyle (m,1,m^{2}-N)}$للحصول على الثلاثية${\displaystyle {\big (}am+Nb,a+bm,k(m^{2}-N){\big )}}$والتي يمكن تقليصها إلى $${\displaystyle \left({\frac {am+Nb}{k}},{\frac {a+bm}{k}},{\frac {m^{2}-N}{k}}\right).}$$

متى${\displaystyle m}$يتم اختيارها بحيث${\displaystyle {\frac {a+bm}{k}}}$إذا كان عددًا صحيحًا، فإن العددين الآخرين في الثلاثية هما عددان صحيحان أيضًا. من بين هذه الأعداد${\displaystyle m}$تختار الطريقة القيمة التي تقلل من${\displaystyle {\frac {m^{2}-N}{k}}}$ويكرر العملية. تنتهي هذه الطريقة دائمًا بحل. استخدمها بهاسكارا لإيجاد الحل x  = 1 766 319 049 ، ص  = 226 153 980 إلى حالة N  =  61. ^{[ 11 ]}

Several European mathematicians rediscovered how to solve Pell's equation in the 17th century. Pierre de Fermat found how to solve the equation and in a 1657 letter issued it as a challenge to English mathematicians.^[12] In a letter to Kenelm Digby, Bernard Frénicle de Bessy said that Fermat found the smallest solution for N up to 150 and challenged John Wallis to solve the cases N = 151 or 313. Both Wallis and William Brouncker gave solutions to these problems, though Wallis suggests in a letter that the solution was due to Brouncker.^[13]

John Pell's connection with the equation is that he revised Thomas Branker's translation^[14] of Johann Rahn's 1659 book Teutsche Algebra^{[note 2]} into English, with a discussion of Brouncker's solution of the equation. Leonhard Euler mistakenly thought that this solution was due to Pell, as a result of which he named the equation after Pell.^[4]

The general theory of Pell's equation, based on continued fractions and algebraic manipulations with numbers of the form ${\displaystyle P+Q{\sqrt {a}},}$ was developed by Lagrange in 1766–1769.^[15] In particular, Lagrange gave a proof that the Brouncker–Wallis algorithm always terminates.

Let ${\displaystyle h_{i}/k_{i}}$ denote the unique sequence of convergents of the regular continued fraction for ${\displaystyle {\sqrt {n}}}$. Then the pair of positive integers ${\displaystyle (x_{1},y_{1})}$ solving Pell's equation and minimizing x satisfies x₁ = h_i and y₁ = k_i for some i. This pair is called the fundamental solution. The sequence of integers ${\displaystyle [a_{0};a_{1},a_{2},\ldots ]}$ in the regular continued fraction of ${\displaystyle {\sqrt {n}}}$ is always eventually periodic. It can be written in the form ${\displaystyle \left[\lfloor {\sqrt {n}}\rfloor$ ;\;{\overline {a_{1},a_{2},\ldots ,a_{r-1},2\lfloor {\sqrt {n}}\rfloor }}\right]} , where ${\displaystyle \lfloor \,\cdot \,\rfloor }$ denotes integer floor, and the sequence ${\displaystyle a_{1},a_{2},\ldots ,a_{r-1},2\lfloor {\sqrt {n}}\rfloor }$ repeats infinitely. Moreover, the tuple${\displaystyle (a_{1},a_{2},\ldots ,a_{r-1})}$ is palindromic, the same left-to-right or right-to-left.^[16]

The fundamental solution is $${\displaystyle (x_{1},y_{1})={\begin{cases}(h_{r-1},k_{r-1}),&{\text{ for }}r{\text{ even}}\\(h_{2r-1},k_{2r-1}),&{\text{ for }}r{\text{ odd}}\end{cases}}}$$

يستغرق حساب إيجاد الحل الأساسي باستخدام طريقة الكسور المستمرة، بمساعدة خوارزمية شونهاج-ستراسن للضرب السريع للأعداد الصحيحة، ما لا يتجاوز عاملًا لوغاريتميًا لحجم الحل، أي عدد الأرقام في الزوج.${\displaystyle (x_{1},y_{1})}$ومع ذلك، فإن هذه ليست خوارزمية ذات وقت متعدد الحدود لأن عدد الأرقام في الحل قد يكون كبيرًا جدًا${\displaystyle {\sqrt {n}}}$، أكبر بكثير من متعدد الحدود في عدد الأرقام في قيمة الإدخال n . ^{[ 17 ]}

بمجرد إيجاد الحل الأساسي، يمكن حساب جميع الحلول المتبقية جبريًا من ^{[ 17 ]}$${\displaystyle x_{k}+y_{k}{\sqrt {n}}=(x_{1}+y_{1}{\sqrt {n}})^{k},}$$ بتوسيع الجانب الأيمن، ومساواة معاملات${\displaystyle {\sqrt {n}}}$بمساواة الحدود الأخرى على كلا الجانبين، ينتج عن ذلك علاقات التكرار .$${\displaystyle x_{k+1}=x_{1}x_{k}+ny_{1}y_{k},}$$$${\displaystyle y_{k+1}=x_{1}y_{k}+y_{1}x_{k}.}$$

على الرغم من أن كتابة الحل الأساسي ( x1 , y1 ) كزوج من الأرقام الثنائية قد تتطلب عددًا كبيرًا من البتات، إلا أنه في كثير من الحالات يمكن تمثيله بشكل أكثر إيجازًا بالشكل _{التالي :}$${\displaystyle x_{1}+y_{1}{\sqrt {n}}=\prod _{i=1}^{t}\left(a_{i}+b_{i}{\sqrt {n}}\right)^{c_{i}}}$$ باستخدام أعداد صحيحة أصغر بكثير a _i و b _i و c _i .

فعلى سبيل المثال، مسألة أرخميدس عن الماشية تعادل معادلة بيل${\displaystyle x^{2}-410\,286\,423\,278\,424\ y^{2}=1}$الحل الأساسي لها206545 رقمًا إذا كُتبت صراحةً. ومع ذلك، فإن الحل يساوي أيضًا $${\displaystyle x_{1}+y_{1}{\sqrt {n}}=u^{2329},}$$ أين $${\displaystyle u=x'_{1}+y'_{1}{\sqrt {4\,729\,494}}=(300\,426\,607\,914\,281\,713\,365\ {\sqrt {609}}+84\,129\,507\,677\,858\,393\,258\ {\sqrt {7766}})^{2}}$$ و${\displaystyle x'_{1}}$و${\displaystyle y'_{1}}$يحتويان على 45 و41 رقمًا عشريًا على التوالي. ^{[ 17 ]}

يمكن استخدام الطرق المتعلقة بنهج الغربال التربيعي لتحليل الأعداد الصحيحة إلى عواملها الأولية لجمع العلاقات بين الأعداد الأولية في حقل الأعداد الناتج عن${\displaystyle {\sqrt {n}}}$ولدمج هذه العلاقات لإيجاد تمثيل ضربي من هذا النوع. تُعدّ الخوارزمية الناتجة لحل معادلة بيل أكثر كفاءة من طريقة الكسور المستمرة، على الرغم من أنها لا تزال تستغرق وقتًا أطول من وقت كثير الحدود. وبافتراض فرضية ريمان المعممة ، يمكن إثبات أنها تستغرق وقتًا $${\displaystyle \exp O\left({\sqrt {\log N\cdot \log \log N}}\right),}$$ حيث N  =  log n هو حجم المدخلات، على غرار المنخل التربيعي. ^{[ 17 ]} 

أثبت هالغريين أن الحاسوب الكمومي قادر على إيجاد تمثيل ضربي، كما هو موضح أعلاه، لحل معادلة بيل في زمن متعدد الحدود. ^{[ 18 ]} وقد وُسِّعت خوارزمية هالغريين، التي يمكن تفسيرها على أنها خوارزمية لإيجاد مجموعة الوحدات لحقل أعداد تربيعي حقيقي ، لتشمل حقولًا أكثر عمومية بواسطة شميدت وفولمر. ^{[ 19 ]}

ترتبط معادلة بيل ارتباطًا وثيقًا بنظرية الأعداد الجبرية ، حيث أن الصيغة $${\displaystyle x^{2}-ny^{2}=(x+y{\sqrt {n}})(x-y{\sqrt {n}})}$$هذا هو الوضع الطبيعي للخاتم${\displaystyle \mathbb {Z} [{\sqrt {n}}]}$وبالنسبة للحقل التربيعي ذي الصلة الوثيقة${\displaystyle \mathbb {Q} ({\sqrt {n}})}$وبالتالي، فإن زوجًا من الأعداد الصحيحة${\displaystyle (x,y)}$يحل معادلة بيل إذا وفقط إذا${\displaystyle x+y{\sqrt {n}}}$هي وحدة ذات معيار 1 في${\displaystyle \mathbb {Z} [{\sqrt {n}}]}$[ ^{21 ] تنص} نظرية ديريشليه للوحدات على أن جميع وحدات${\displaystyle \mathbb {Z} [{\sqrt {n}}]}$يمكن التعبير عن ذلك كقوى لوحدة أساسية واحدة (مع الضرب بإشارة)، وهو إعادة صياغة جبرية لحقيقة أن جميع حلول معادلة بيل يمكن توليدها من الحل الأساسي. ^{[ 22 ]} يمكن إيجاد الوحدة الأساسية عمومًا بحل معادلة شبيهة بمعادلة بيل، لكنها لا تتطابق دائمًا بشكل مباشر مع الحل الأساسي لمعادلة بيل نفسها، لأن معيار الوحدة الأساسية قد يكون -1 بدلًا من 1، وقد تكون معاملاتها أنصاف أعداد صحيحة بدلًا من أعداد صحيحة.

يذكر ديمير وجود صلة بين معادلة بيل ومتعددات حدود تشيبيشيف : إذا${\displaystyle T_{i}(x)}$و${\displaystyle U_{i}(x)}$إذا كانت كثيرات حدود تشيبيشيف من النوع الأول والثاني على التوالي، فإن هذه الكثيرات تحقق شكلاً من أشكال معادلة بيل في أي حلقة كثيرات حدود${\displaystyle R[x]}$، مع${\displaystyle n=x^{2}-1}$[ ^{23 ]​}$${\displaystyle T_{i}^{2}-(x^{2}-1)U_{i-1}^{2}=1.}$$ وبالتالي، يمكن توليد هذه كثيرات الحدود باستخدام التقنية القياسية لمعادلات بيل المتمثلة في أخذ قوى الحل الأساسي: $${\displaystyle T_{i}+U_{i-1}{\sqrt {x^{2}-1}}=(x+{\sqrt {x^{2}-1}})^{i}.}$$ ويمكن ملاحظة أنه إذا${\displaystyle (x_{i},y_{i})}$إذا كانت هذه هي حلول معادلة بيل لأي عدد صحيح،${\displaystyle x_{i}=T_{i}(x_{1})}$و${\displaystyle y_{i}=y_{1}U_{i-1}(x_{1})}$[ ^{24 ]​}

تطوير عام لحلول معادلة بيل${\displaystyle x^{2}-ny^{2}=1}$من حيث الكسور المستمرة من${\displaystyle {\sqrt {n}}}$يمكن تقديمها، حيث أن الحلول x و y هي تقريبات للجذر التربيعي لـ n وبالتالي فهي حالة خاصة من تقريبات الكسور المستمرة للأعداد غير النسبية التربيعية . ^{[ 16 ]}

تشير العلاقة بالكسور المستمرة إلى أن حلول معادلة بيل تُشكّل مجموعة جزئية شبه زمرة من الزمرة النمطية . وبالتالي، على سبيل المثال، إذا حقق كل من p و q معادلة بيل، فإن $${\displaystyle {\begin{pmatrix}p&q\\nq&p\end{pmatrix}}}$$ هي مصفوفة ذات محدد يساوي واحدًا . تأخذ نواتج ضرب هذه المصفوفات نفس الشكل تمامًا، وبالتالي فإن جميع هذه النواتج تُعطي حلولًا لمعادلة بيل. يمكن فهم ذلك جزئيًا على أنه ناتج عن حقيقة أن المتقاربات المتتالية لكسر مستمر تشترك في نفس الخاصية: إذا كان p_{_{k -1}} / q _{_{k -1}} و p_{_k} / q_{_k} متقاربين متتاليين لكسر مستمر، فإن المصفوفة $${\displaystyle {\begin{pmatrix}p_{k-1}&p_{k}\\q_{k-1}&q_{k}\end{pmatrix}}}$$

لها محدد (-1) ^k .

تُطبّق نظرية ستورمر معادلات بيل لإيجاد أزواج من الأعداد الملساء المتتالية ، وهي أعداد صحيحة موجبة جميع عواملها الأولية أصغر من قيمة مُعطاة. ^{[ 25 ] [ 26 ]} وكجزء من هذه النظرية، بحث ستورمر أيضًا علاقات قابلية القسمة بين حلول معادلة بيل؛ وعلى وجه الخصوص، بيّن أن لكل حل، باستثناء الحل الأساسي، عاملًا أوليًا لا يقسم n . ^{[ 25 ]}