thumb|right|250px|Pellova enačba za n = 2 in šest njenih celoštevilskih rešitev
Pellova enáčba [pélova ~] (tudi Fermat-Pellova enáčba [fermá ~] ali Fermatova enačba [fermájeva ~]) je nedoločena kvadratna diofantska enačba oblike:
kjer je n poljubno pozitivno celo število, ki ni popolni kvadrat kakšnega števila, za rešitve v x in y pa veljajo cela števila. Na splošnosti se ne izgubi, če za rešitve v x in y veljajo samo pozitivna cela števila.. V kartezičnih koordinatah ima enačba obliko hiperbole. Rešitve obstajajo tam kjer krivulja poteka skozi točke, katerih koordinati x in y sta obe celi števili, kot je na primer trivialna rešitev x = 1 in y = 0. Joseph Louis Lagrange je dokazal, da ima za pozitivni n, ki ni popolni kvadrat, Pellova enačba neskončno mnogo različnih celoštevilskih rešitev. S temi rešitvami se lahko dobijo dovolj točni približki kvadratnega korena iz n z racionalnimi števili v obliki ulomka x/y.
Prve osnovne rešitve Pellove enačbe n x y 2 3 2 3 2 1 5 9 4 6 5 2 7 8 3 8 3 1 10 19 6 11 10 3 12 7 2 13 649 180 14 15 4 15 4 1 17 33 8 18 17 4 19 170 39 20 9 2 21 55 12 22 197 42 23 24 5 24 5 1 26 51 10 27 26 5 28 127 24 29 9801 1820 30 11 2 31 1520 273 32 17 3 33 23 4 34 35 6 35 6 1 37 73 12 38 37 6 39 25 4 40 19 3 41 2049 320 42 13 2 43 3482 531 44 199 30 45 161 24 46 24335 3588 47 48 7 48 7 1 50 99 14 51 50 7 52 649 90 53 66249 9100 54 485 66 55 89 12 56 15 2 57 151 20 58 19603 2574 59 530 69 60 31 4 61 1766319049 226153980 62 63 8 63 8 1 65 129 16 66 65 8 67 48842 5967 68 33 4 69 7775 936 70 251 30 71 3480 413 72 17 2 73 2281249 267000 74 3699 430 75 26 3 76 57799 6630 77 351 40 78 53 6 79 80 9 80 9 1 82 163 18 83 82 9 84 55 6 85 285769 30996 86 10405 1122 87 28 3 88 197 21 89 500001 53000 90 19 2 91 1574 165 92 1151 120 93 12151 1260 94 2143295 221064 95 39 4 96 49 5 97 62809633 6377352 98 99 10 99 10 1 101 201 20 102 101 10 103 227528 22419 104 51 5 105 41 4 106 32080051 3115890 107 962 93 108 1351 130 109 158070671986249 15140424455100 110 21 2 Če je tako n popolni kvadrat, ima enačba le trivialni celoštevilski rešitvi (±1, 0). Enačba ima le dve celoštevilski rešitvi (±1, 0) tudi, kadar je n < −1. Za n = −1 je enačba:
in obstajajo le štiri rešitve: (±1, 0) in (0, ±1). V splošnem za n < 0 končno mnogo rešitev izhaja iz korena enote za kvadratni obseg .. Če je n = 0, ima enačba le eno spremenljivko:
rešitve pa lahko zapišemo kot (±1, k).
Ime Pellova enačba izhaja od Eulerjevega napačnega poimenovanja raziskovanj enačbe po Johnu Pellu. Euler je poznal delo Williama Brounckerja, prvega evropskega matematika, ki je našel splošno rešitev enačbe, vendar je očitno zamešal Brounckerja s Pellom. Problem reševanja enačbe je postavil de Fermat leta 1657 in trdil, da ima Pellova enačba neskončno mnogo celoštevilskih rešitev, česar pa ni dokazal. Poznal pa je način reševanja. Brouncker je med dopisovanjem z de Fermatom med letoma 1657-58 odkril postopek reševanja Pellove enačbe. Z reševanjem Pellove enačbe se je istega leta kot de Fermat ukvarjal tudi John Wallis.
Enačbo so prvič obsežno raziskovali v antični Indiji. Brahmagupta je razvil metodo čakravala za reševanje Pellove enačbe in drugih nedoločenih kvadratnih enačb v svojem delu Pregled brahmanskih sestavov (Brahma-sputa sidanta) iz leta 628, približno tisoč let pred Pellovim časom. Njegovo delo so leta 773 prevedli v arabščino, leta 1126 pa v latinščino. Bhaskara II. v 12. in Narajana Pandit v 14. stoletju sta našla splošne rešitve Pellove enačbe in drugih nedoločenih kvadratnih enačb. Rešitve posebnih primerov Pellove enačbe, kot so na primer Pellova števila, ki izhajajo iz enačbe za n = 2, so bile znane še dlje od časa Pitagore v stari Grčiji in istočasno v Indiji.
Zgodovina
Do leta 400 pr. n. št. so matematiki v Indiji in stari Grčiji raziskovali števila, ki izhajajo iz Pellove enačbe za n = 2:
in iz zelo sorodne enačbe:
Enačbi sta povezani s kvadratnim korenom iz 2. Če sta x in y pozitivni celi števili za kateri velja enačba, potem je ulomek x/y racionalni približek √2. Števila x in y, ki se pojavljajo v teh približkih, imenovana stranična in premerska števila, so bila znana pitagorejcem. Prokl je opazil, da za ta števila v nasprotni smeri velja ena od zgornjih dveh enačb. Podobno je Baudhajana odkril, da sta x = 17, y = 12 in x = 577, y = 408 dve rešitvi Pellove enačbe, in da sta 17/12 in 577/408 zelo dobra približka za √2. 577/408 je sedmi racionalni približek za √2 in izhaja iz pravila Baudhajane, Apastambe in Katjajane za dolžino diagonale kvadrata v današnji pisavi:
Baudhajana je včasih za kvadratni koren iz 3 uporabljal peti racionalni približek 26/15. Poznal je tudi enajsti racionalni približek:
Tudi Arhimed je kasneje aproksimiral √3 z racionalnim številom 1351/780 in postavil mejo:
kjer je 265/153 osmi racionalni približek za √3. Čeprav svojih metod ni pojasnil, se lahko približka dobita na enak način kot rešitev Pellove enačbe za n = 3:
.
Okoli leta 250 je Diofant obravnaval enačbo:
kjer sta a in c dani števili, x in y pa spremenljivki, za kateri velja enačba. Ta enačba je drugačne oblike kot Pellova, vendar je enakovredna. Diofant je rešil enačbo za (a,c): (1,1), (1,−1), (1,12) in (3,9). Al-Karadži je v 10. stoletju obravnaval podobne probleme kot Diofant.
Brahmagupta je odkril izraz:
(glej Brahmaguptova enakost). S pomočjo izraza je lahko »sestavil« trojice in , ki so rešitve enačbe , kar da novo trojico:
in
Na ta način se z eno rešitvijo dobi neskončno mnogo rešitev enačbe . Z delitvijo te sestave rešitev s , se lahko velikokrat dobijo celoštevilske ali »skoraj celoštevilske rešitve«. Za je na primer Brahmagupta sestavil trojico (ker je ) s samo seboj in dobil novo trojico . Deljenje z 64 da trojico , ki sestavljena sama s seboj da iskano celoštevilsko rešitev . Brahmagupta je s to metodo rešil veliko Pellovih enačb. Še posebej je pokazal kako se dobijo rešitve iz začetne celoštevilske rešitve za k = ±1, ±2 ali ±4..
Prvo splošno metodo za reševanje Pellove enačbe (za vse N) je dal Bhaskara II. leta 1150 in razširil Brahmaguptove metode. Metoda se imenuje (ciklična) metoda čakravala in se začne s sestavo poljubne trojice (tiste za katero velja enačba ) s trivialno trojico , kar da trojico , ki jo lahko prevedemo na:
Če se izbere tak m, da je (a+bm)/k celo število, sta celi števili tudi drugi dve v trojici. Med takšnimi m metoda izbere takšno število, za katero je (m²-N)/k najmanjši, in ponovi korak. Metoda se vedno konča z rešitvijo, kar je dokazal Lagrange leta 1768. Bhaskara je z metodo dobil rešitev x = 1766319049, y = 226153980 za razvpiti primer N = 61.
Splošno teorijo Pellovih enačb na podlagi verižnih ulomkov in algebrske obravnave števil oblike je razvil Lagrange med letoma 1766 in 1769.. Dirichlet je kasneje pokazal na način ugotavljanja neskončno mnogo rešitev Pellove enačbe brez verižnih ulomkov.
Rešitve
Osnovna rešitev prek verižnih ulomkov
Naj označuje zaporedje konvergentov verižnega ulomka za . Potem za urejeni par (x1,y1), za keterega velja Pellova enačba in za katerega je x najmanjši, velja x1 = hi in y1 = ki za poljubni i. Par se imenuje osnovna rešitev. Tako se lahko osnovna rešitev dobi z razvojem v verižni ulomek in preskušanjem vsakega zaporednega konvergenta dokler se ne najde rešitev Pellove enačbe.
Kot je opisal Lenstra je čas za iskanje osnovne rešitve s pomočjo metode verižnih ulomkov in Schönhage-Strassenovega algoritma za hitro množenje celih števil znotraj logaritemskega faktorja velikosti rešitve, števila števk v paru (x1,y1).. Vendar to ni algoritem v polinomskem času, ker je lahko število števk v rešitvi veliko do √n, kar je veliko več kot polinom v številu števk vhodne vrednosti n.
Dodatne rešitve iz osnovne rešitve
Ko je osnovna rešitev najdena, se lahko preostale rešitve izračunajo algebrsko kot:
Naslednje rešitve se lahko enakovredno izračunajo z rekurenčnima enačbama:
Ko se najde prva netrivialna rešitev, se lahko v drugi metodi reševanja vzame izvirna enačba in se faktorizira leva stran kot razlika kvadratov, kar vede do V tej obliki se lahko obe strani preprosto dvigneta na k-to potenco, faktorska oblika pa se znova prevede na enočlenik. Rešitev bo imela obliko
Zgoščena reprezentacija in hitrejši algoritmi
Čeprav zapis osnovne rešitve (x1,y1) kot par dvojiških števil zahteva večje število bitov, se lahko v mnogih primerih predstavi bolj zgoščeno v obliki:
kjer so koeficienti ai, bi in ci veliko manjši.
Arhimedov problem goveda se na primer lahko reši s pomočjo Pellove enačbe:
Njena osnovna rešitev ima 206545 števk, če se jo zapiše eksplicitno. Namesto, da se rešitev zapiše kot par števil, se lahko uporabi formula:
kjer je:
in pa imata le 45 in 41 desetiških števk:
.
Rešitev se lahko zapiše še bolj zgoščeno:
Metode povezane z reševanjem s pomočjo kvadratnega sita za praštevilski razcep se lahko uporabijo za zbiranje povezav med praštevili v številskem obsegu, ki ga tvori √n, in za sestavljanje teh povezav pri iskanju reprezentacije s produktom te vrste. Takšen algoritem za reševanje Pellove enačbe je bolj učinkovit od metode z verižnimi ulomki, čeprav še vedno ni v polinomskem času. S privzetkom posplošene Riemannove domneve se lahko pokaže, da je algoritemski čas enak:
kjer je N = log n velikost vnosa, in je podoben času kvadratnega sita.
Kvantni algoritmi
Hallgren je pokazal, da lahko kvantni računalnik najde reprezentacijo s produktom, opisano zgoraj, za rešitev Pellove enačbe v polinomskem času.. Hallgrenov algoritem, ki se lahko tolmači kot algoritem za iskanje grupe enot realnega kvadratnega številskega obsega, sta na splošnejše obsege razširila Schmidt in Völlmer..
Zgled
Zgled je Pellova enačba za n = 7:
Zaporedje konvergentov za kvadratni koren iz 7 je: {| class="wikitable" style="text-align:center;" |- ! h / k (konvergent) ! h2 −7k2 (približek Pellove vrste) |- | 2 / 1 | −3 |- | 3 / 1 | +2 |- | 5 / 2 | −3 |- | 8 / 3 | +1 |} Osnovno rešitev tako da par (8, 3). Z rekurenčno enačbo izhaja neskončno zaporedje rešitev:
(8, 3), (127, 48), (2024, 765), (32257, 12192), (514088, 194307), (8193151, 3096720), (130576328, 49353213), ...
Povezave
Pellova enačba je povezana z več drugimi pomembnimi matematičnimi področji.
Algebrska teorija števil
Pellova enačba je tesno povezana s teorijo algebrskih števil, ker je formula:
norma kolobarja in zelo sorodnega kvadratnega obsega . Tako celoštevilski urejeni par reši Pellovo enačbo, če in samo če je enota z normo 1 v . Dirichletov izrek o enotah, po katerem lahko vse enote izrazimo kot potence ene osnovne enote (in množenja s predznakom), je algebrska ugotovitev, da vse rešitve Pellove enačbe izhajajo iz osnovne rešitve. Osnovno enoto se lahko v splošnem najde z reševanjem enačbe Pellove vrste, vendar ta vedno ne odgovarja neposredno osnovni rešitvi Pellove enačbe same.
Polinomi Čebišova
Demeyer je omenil povezavo med Pellovo enačbo in polinomi Čebišova:. Če sta Ti (x) in Ui (x) polinoma Čebišova prve in druge vrste, potem zanju velja oblika Pellove enačbe v poljubnem polinomskem kolobarju R[x] z n = x2 − 1:
Na ta način se lahko tvori takšne polinome s standardno tehniko za Pellove enačbe s potencami osnovne rešitve:
Lahko se vidi, da če so (xi,yi) rešitve kakšne celoštevilske Pellove enačbe, velja xi = Ti (x1) in yi = y1Ui − 1(x1)..
Verižni ulomki
Obstaja splošni razvoj rešitev Pellove enačbe z verižnimi ulomki, saj sta rešitvi x in y približka kvadratnega korena iz n in na ta način posebni primer približkov kvadratnih iracionalnih števil z verižnimi ulomki.
Povezava z verižnimi ulomki kaže, da rešitve Pellove enačbe tvorijo polgrupno podmnožico modularne grupe. Takom če na primer za p in q velja Pellova enačba, je: