Ogled vira Pellova enačba

[[Slika:Pell's equation.svg|thumb|right|250px|Pellova enačba za ''n''&nbsp;=&nbsp;2 in šest njenih celoštevilskih rešitev]]

'''Pellova enáčba''' [pélova ~] (tudi '''Fermat-Pellova enáčba''' [fermá ~] ali '''Fermatova enačba'''<ref name="hocevar_2012" /> [fermájeva ~]) je [[nedoločena enačba|nedoločena]] [[kvadratna enačba|kvadratna]] [[diofantska enačba]] oblike:

: <math> x^{2}-ny^{2}=1, \qquad  ( n > 0 ), \!\, </math>

kjer je ''n'' poljubno [[pozitivno število|pozitivno]] [[celo število]], ki ni [[popolni kvadrat|popolni]] [[kvadratno število|kvadrat]] kakšnega [[število|š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.<ref name="whitford_1912">{{sktxt|Whitford|1912}}.</ref> V [[kartezični koordinatni sistem|kartezičnih koordinatah]] ima enačba obliko [[hiperbola|hiperbole]]. Rešitve obstajajo tam kjer krivulja poteka skozi [[točka|točke]] katerih koordinati ''x'' in ''y'' sta obe celi števili, kot je na primer [[trivialnost (matematika)|trivialna]] rešitev ''x''&nbsp;=&nbsp;1 in ''y''&nbsp;=&nbsp;0. [[Joseph Louis Lagrange]] je [[matematični dokaz|dokazal]], da ima za pozitivni ''n'', ki ni popolni kvadrat, Pellova enačba [[neskončnost|neskončno]] mnogo različnih celoštevilskih rešitev. S temi rešitvami se lahko dobijo dovolj točni [[teorija diofantskih približkov|približki]] [[kvadratni koren|kvadratnega korena]] iz ''n'' z [[racionalno število|racionalnimi števili]] v obliki [[ulomek|ulomka]]&nbsp;''x/y''.
{{-}}
{| class="wikitable collapsible" align="right" style="text-align: right; width:200px;"
! colspan="3" | Prve osnovne rešitve Pellove enačbe <math> x^{2}-ny^{2}=1, \quad n \le 110 \!\, </math>
|-
! ''n'' <br /> {{OEIS2|id=A000037}}
! ''x'' <br /> {{OEIS2|id=A033313}}
! ''y'' <br /> {{OEIS2|id=A033317}}
|-
| 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'' < &minus;1. Za ''n'' = &minus;1 je enačba:

: <math> x^{2}+y^{2}=1 \!\, </math>

in obstajajo le štiri rešitve: (±1, 0) in (0, ±1).<ref name="whitford_1912" /> V splošnem za ''n'' < 0 končno mnogo rešitev izhaja iz korena enote za [[kvadratni obseg]] <math>\mathbb{Q}\left( \sqrt{-1}\right) \, </math>.<ref>{{sktxt|Barbeau|2010}}.</ref> Če je ''n'' = 0, ima enačba le eno spremenljivko: 

: <math> x^{2}=1 \!\, , </math>

rešitve pa lahko zapišemo kot (±1, ''k'').

Ime Pellova enačba izhaja od [[Leonhard Euler|Eulerjevega]] [[Stiglerjev zakon eponimnosti|napačnega poimenovanja]] raziskovanj enačbe po [[John Pell|Johnu Pellu]]. Euler je poznal delo [[William Brouncker|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 [[Pierre de Fermat|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.<ref name="hocevar_2012" /> 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]].<ref name="hocevar_2012" />

Enačbo so prvič obsežno raziskovali v [[indijska matematika|antični Indiji]]. [[Brahmagupta]] je razvil [[metoda čakravala|metodo čakravala]] za reševanje Pellove enačbe in drugih nedoločenih kvadratnih enačb v svojem delu ''Pregled brahmanskih sestavov'' ([[Brahmasputasidanta|''Brahma-sputa sidanta'']]) iz leta 628, približno tisoč let pred Pellovim časom. Njegovo delo so leta 773 prevedli v [[arabščina|arabščino]], leta 1126 pa v [[latinščina|latinščino]]. [[Bhaskara|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 [[Pellovo število|Pellova števila]], ki izhajajo iz enačbe za ''n'' = 2, so bile znane še dlje od časa [[Pitagora|Pitagore]] v [[grška matematika|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''&nbsp;=&nbsp;2:

: <math> x^{2} - 2y^{2} = 1 \!\, </math>

in iz zelo sorodne enačbe:

: <math> x^{2} - 2y^{2} = -1 \!\, . </math>

Enačbi sta povezani s [[kvadratni koren števila 2|kvadratnim korenom iz 2]].<ref name="knorr76"/> Č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 [[Pellovo število|stranična in premerska števila]], so bila znana [[pitagorejstvo|pitagorejcem]]. [[Prokl]] je opazil, da za ta števila v nasprotni smeri velja ena od zgornjih dveh enačb.<ref name="knorr76"/> 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, [[Apastamba|Apastambe]] in [[Katjajana|Katjajane]] za [[dolžina|dolžino]] [[diagonala|diagonale]] [[kvadrat (geometrija)|kvadrata]] v današnji pisavi:

: <math> \sqrt{2} \approx 1 + \frac{1}{3} + \frac{1}{3\cdot 4} - \frac{1}{3\cdot 4\cdot 34} = \frac{577}{408} = 1,414\overline{2156862745098039} \!\, . </math><ref name="whitford_1912" />

Baudhajana je včasih za [[kvadratni koren števila 3|kvadratni koren iz 3]] uporabljal peti racionalni približek 26/15. Poznal je tudi enajsti racionalni približek:

: <math> \sqrt{3} \approx 1 + \frac{2}{3} + \frac{1}{3\cdot 5} - \frac{1}{3\cdot 5\cdot 52} = \frac{1351}{780} = 1,73\overline{205128} \!\, . </math><ref name="whitford_1912" />

Tudi [[Arhimed]] je kasneje aproksimiral √3 z racionalnim številom 1351/780 in postavil mejo:

:<math> \frac{265}{153} < \sqrt{3} < \frac{1351}{780} \!\, , </math>

kjer je 265/153 osmi racionalni približek za √3.<ref name="whitford_1912" /> Čeprav svojih metod ni pojasnil, se lahko približka dobita na enak način kot rešitev Pellove enačbe za ''n''&nbsp;=&nbsp;3:

: <math> x^{2} - 3y^{2}=1 \!\, . </math><ref name="knorr76">{{sktxt|Knorr|1976}}.</ref>

Okoli leta 250 je [[Diofant]] obravnaval enačbo:

: <math> a^{2} x^{2}+c=y^{2} \!\, , </math>

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,&minus;1), (1,12) in (3,9). [[Al-Karadži]] je v 10. stoletju obravnaval podobne probleme kot Diofant.

Brahmagupta je odkril izraz:

: <math>\begin{align} (x_1^2 - Ny_1^2)(x_2^2 - Ny_2^2) &= (x_1x_2 + Ny_1y_2)^2 - N(x_1y_2 + x_2y_1)^2 \\ &= (x_1x_2 - Ny_1y_2)^2 - N(x_1y_2 - x_2y_1)^2 \!\, \end{align} </math>

(glej [[Brahmaguptova enakost]]). S pomočjo izraza je lahko »sestavil« trojice <math>(x_1, y_1, k_1)</math> in <math>(x_2, y_2, k_2)</math>, ki so rešitve enačbe <math>x^2 - Ny^2 = k</math>, kar da novo trojico:

: <math> (x_1x_2 + Ny_1y_2 \,,\, x_1y_2 + x_2y_1 \,,\, k_1k_2)</math> in <math>(x_1x_2 - Ny_1y_2 \,,\, x_1y_2 - x_2y_1 \,,\, k_1k_2) \!\, . </math>

Na ta način se z eno rešitvijo dobi neskončno mnogo rešitev enačbe <math>x^2 - Ny^2 = 1</math>. Z delitvijo te sestave rešitev s <math>k_1k_2</math>, se lahko velikokrat dobijo celoštevilske ali »skoraj celoštevilske rešitve«. Za <math>N=92</math> je na primer Brahmagupta sestavil trojico <math>(10, 1, 8)</math> (ker je <math>10^2 - 92(1^2) = 8</math>) s samo seboj in dobil novo trojico <math>(192, 20, 64)</math>. Deljenje z 64 da trojico <math>(24, 5/2, 1)</math>, ki sestavljena sama s seboj da iskano celoštevilsko rešitev <math>(1151, 120, 1)</math>. 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 <math>x^2 - Ny^2 = k</math> za ''k''&nbsp;=&nbsp;±1, ±2 ali ±4.<ref name=stillwell>{{sktxt|Stillwell|2002|pp=72–76}}.</ref>

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 <math>(a,b,k)</math> (tiste za katero velja enačba <math>a^2 - Nb^2 = k</math>) s trivialno trojico <math>(m, 1, m^2 - N)</math>, kar da trojico <math>(am + Nb, a+bm, k(m^2-N))</math>, ki jo lahko prevedemo na:

: <math> \left( \frac{am+Nb}{k} \,,\, \frac{a+bm}{k} \,,\, \frac{m^2-N}{k} \right) \!\, . </math>

Č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.<ref name=stillwell/>

Splošno teorijo Pellovih enačb na podlagi [[verižni ulomek|verižnih ulomkov]] in algebrske obravnave števil oblike <math>P+Q\sqrt{a},</math> je razvil Lagrange med letoma 1766 in 1769.<ref>{{sktxt|Serret|1867}}.</ref> [[Johann Peter Gustav Lejeune Dirichlet|Dirichlet]] je kasneje pokazal na način ugotavljanja neskončno mnogo rešitev Pellove enačbe brez verižnih ulomkov.<ref name="hocevar_2012" />

== Rešitve ==

=== Osnovna rešitev prek verižnih ulomkov ===

Naj <math>h_{i}/k_{i}</math> označuje zaporedje konvergentov verižnega ulomka za <math>\sqrt{n}</math>. Potem za [[urejeni par]] (''x''<sub>1</sub>,''y''<sub>1</sub>), za keterega velja Pellova enačba in za katerega je ''x'' najmanjši, velja ''x''<sub>1</sub> = ''h<sub>i</sub>'' in ''y''<sub>1</sub> = ''k<sub>i</sub>'' 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 [[Hendrik Lenstra|Lenstra]] je čas za iskanje osnovne rešitve s pomočjo metode verižnih ulomkov in [[Schönhage-Strassen algoritem|Schönhage-Strassenovega algoritma]] za hitro množenje celih števil znotraj logaritemskega faktorja velikosti rešitve, števila števk v paru (''x''<sub>1</sub>,''y''<sub>1</sub>).<ref name="lenstra_2002">{{sktxt|Lenstra|2002}}.</ref> Vendar to ni [[časovna kompleksnost|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''.<ref name="lenstra_2002" />

=== Dodatne rešitve iz osnovne rešitve ===

Ko je osnovna rešitev najdena, se lahko preostale rešitve izračunajo algebrsko kot:

: <math> x_k + y_k\sqrt n = (x_1 + y_1\sqrt n)^k \!\, . </math>

Naslednje rešitve se lahko enakovredno izračunajo z [[rekurenčna enačba|rekurenčnima enačbama]]:

: <math> \displaystyle x_{k+1} = x_1 x_k + n y_1 y_k \!\, , </math>
: <math> \displaystyle y_{k+1} = x_1 y_k + y_1 x_k \!\, . </math>

Ko se najde prva netrivialna rešitev, se lahko v drugi metodi reševanja vzame izvirna enačba <math>x^2 - ny^2 = 1</math> in se faktorizira leva stran kot razlika kvadratov, kar vede do <math>(x + y\sqrt n)(x - y\sqrt n) = 1.</math> V tej obliki se lahko obe strani preprosto dvigneta na ''k''-to potenco, faktorska oblika pa se znova prevede na enočlenik. Rešitev <math>s</math> bo imela obliko <math>(x-s)^k + n (y-s)^k = 1.</math>

=== Zgoščena reprezentacija in hitrejši algoritmi ===

Čeprav zapis osnovne rešitve (''x''<sub>1</sub>,''y''<sub>1</sub>) kot par [[dvojiški številski sistem|dvojiških]] števil zahteva večje število [[bit]]ov, se lahko v mnogih primerih predstavi bolj zgoščeno v obliki:

: <math> x_1+y_1\sqrt n = \prod_{i=1}^t (a_i + b_i\sqrt n)^{c_i} \!\, , </math>
kjer so koeficienti ''a''<sub>''i''</sub>, ''b''<sub>''i''</sub> in ''c''<sub>''i''</sub> veliko manjši.

[[Arhimedov problem goveda]] se na primer lahko reši s pomočjo Pellove enačbe:

: <math> u^{2} - 609 \cdot 7766 v^{2} = 1 \!\, . </math>

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:

: <math> x_1+y_1\sqrt n=u^{2329} \!\, , </math>

kjer je:

: <math> u = x'_1+y'_1\sqrt{4729494} \!\, , </math>

<math>\scriptstyle x'_1</math> in <math>\scriptstyle y'_1</math> pa imata le 45 in 41 desetiških števk:

: <math> x'_{1} = 109931986732829734979866232821433543901088049 \!\, , </math>
: <math> y'_{1} = 50549485234315033074477819735540408986340 \!\, . </math> <ref name="hocevar_2012">{{sktxt|Hočevar|2012}}.</ref>

Rešitev se lahko zapiše še bolj zgoščeno:

:<math> u = (300426607914281713365\sqrt{609}+84129507677858393258\sqrt{7766})^2 \!\, . </math><ref name="lenstra_2002" />

Metode povezane z reševanjem s pomočjo [[kvadratno sito|kvadratnega sita]] za [[praštevilski razcep]] se lahko uporabijo za zbiranje povezav med [[praštevilo|praštevili]] v [[obseg algebrskih števil|š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šena Riemannova domneva|posplošene Riemannove domneve]] se lahko pokaže, da je algoritemski čas enak:

: <math> \exp O(\sqrt{\log N\log\log N}) \!\, , </math>

kjer je ''N''&nbsp;=&nbsp;log&nbsp;''n'' velikost vnosa, in je podoben času kvadratnega sita.<ref name="lenstra_2002" />

=== 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.<ref>{{sktxt|Hallgren|2007}}.</ref> Hallgrenov algoritem, ki se lahko tolmači kot algoritem za iskanje grupe enot realnega [[kvadratni obseg|kvadratnega številskega obsega]], sta na splošnejše obsege razširila Schmidt in Völlmer.<ref>{{sktxt|Schmidt|Völlmer|2005}}.</ref>

== Zgled ==

Zgled je Pellova enačba za ''n'' = 7:

: <math> x^{2} - 7 y^{2} = 1 \!\, . </math>
Zaporedje konvergentov za kvadratni koren iz 7 je:
:{| class="wikitable" style="text-align:center;"
|-
! ''h''&nbsp;/&nbsp;''k'' (konvergent)
! ''h''<sup>2</sup>&nbsp;&minus;7''k''<sup>2</sup> (približek Pellove vrste)
|-
| 2&nbsp;/&nbsp;1
| &minus;3
|-
| 3&nbsp;/&nbsp;1
| +2
|-
| 5&nbsp;/&nbsp;2
| &minus;3
|-
| 8&nbsp;/&nbsp;3
| +1
|}
Osnovno rešitev tako da par (8,&nbsp;3). Z rekurenčno enačbo izhaja neskončno zaporedje rešitev:

: (8,&nbsp;3), (127,&nbsp;48), (2024,&nbsp;765), (32257,&nbsp;12192), (514088,&nbsp;194307), (8193151,&nbsp;3096720), (130576328,&nbsp;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 [[algebrsko število|algebrskih števil]], ker je formula:

: <math> x^{2} - n y^{2} = (x + y\sqrt n)(x - y\sqrt n) \!\, </math>

[[norma (teorija obsegov)|norma]] [[kolobar (algebra)|kolobarja]] <math>\mathbb{Z}[\sqrt{n}]</math> in zelo sorodnega kvadratnega obsega <math>\mathbb{Q}(\sqrt{n})</math>. Tako celoštevilski urejeni par <math>(x, y)</math> reši Pellovo enačbo, [[če in samo če]] je <math>x + y \sqrt{n}</math> [[enota (teorija kolobarjev)|enota]] z normo 1 v <math>\mathbb{Z}[\sqrt{n}]</math>. [[Dirichletov izrek o enotah]], po katerem lahko vse enote <math>\mathbb{Z}[\sqrt{n}]</math> izrazimo kot potence ene [[osnovna enota (teorija števil)|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]]:<ref>{{sktxt|Demeyer|2007}}.</ref> Če sta ''T<sub>i</sub>''&nbsp;(''x'') in ''U<sub>i</sub>''&nbsp;(''x'') polinoma Čebišova prve in druge vrste, potem zanju velja oblika Pellove enačbe v poljubnem [[polinomski kolobar|polinomskem kolobarju]] ''R''[''x''] z ''n'' = ''x''<sup>2</sup>&nbsp;&minus;&nbsp;1:

: <math> T_{i}^{2} - (x^{2}-1) U_{i-1}^{2} = 1 \!\, . </math>

Na ta način se lahko tvori takšne polinome s standardno tehniko za Pellove enačbe s potencami osnovne rešitve:

: <math> T_{i} + U_{i-1} \sqrt{x^{2}-1} = (x + \sqrt{x^{2}-1})^{i} \!\, . </math>

Lahko se vidi, da če so (''x<sub>i</sub>'',''y<sub>i</sub>'') rešitve kakšne celoštevilske Pellove enačbe, velja ''x<sub>i</sub>'' = ''T<sub>i</sub>'' (''x''<sub>1</sub>) in ''y<sub>i</sub>'' = ''y''<sub>1</sub>''U''<sub>''i''&nbsp;&minus;&nbsp;1</sub>(''x''<sub>1</sub>).<ref>{{sktxt|Barbeau|2003|loc=§ 3}}.</ref>

=== Verižni ulomki ===

Obstaja splošni razvoj rešitev Pellove enačbe z [[verižni ulomek|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 [[kvadratno iracionalno število|kvadratnih iracionalnih števil]] z verižnimi ulomki.

Povezava z verižnimi ulomki kaže, da rešitve Pellove enačbe tvorijo [[polgrupa|polgrupno]] [[podmnožica|podmnožico]] [[modularna grupa|modularne grupe]]. Takom če na primer za ''p'' in ''q'' velja Pellova enačba, je:

: <math> \begin{pmatrix} p & q \\ nq & p \!\, \end{pmatrix} </math>

[[matrika]] enotske [[determinanta|determinante]]. Produkti takšnih matrik imajo točno enako obliko, in zato takšni produkti dajo rešitve Pellove enačbe. To se lahko razume deloma, ker izhaja iz dejstva, da imajo zaporedni konvergenti verižnega ulomka enako značilnost: če sta ''p''<sub>''k''&minus;1</sub>/''q''<sub>''k''&minus;1</sub> in ''p''<sub>''k''</sub>/''q''<sub>''k''</sub> dva zaporedna konvergenta verižnega ulomka, je determinata matrike:

: <math> \begin{pmatrix} p_{k-1} & p_{k} \\ q_{k-1} & q_{k} \end{pmatrix} </math>

enaka (&minus;1)<sup>''k''</sup>.

[[Størmerjev izrek]] s Pellovimi enačbami išče pare zaporednih [[gladko število|gladkih števil]]. Kot del te teorije je [[Carl Størmer|Størmer]] raziskoval tudi zveze deljivosti med rešitvami Pellove enačbe, še posebej je pokazal, da ima vsaka rešitev, različna od osnovne, [[prafaktor]], ki ne deli&nbsp;''n''.

Kot je opisal Lenstra, se lahko s pomočjo Pellove enačbe reši [[Arhimedov problem goveda]].<ref name="lenstra_2002" />

== Negativna Pellova enačba ==

Negativna Pellova enačba ima obliko:

: <math> x^{2} - ny^{2} = -1. \!\, </math>   (1)

Tudi to obliko so veliko raziskovali. Lahko se jo reši z enako metodo z verižnimi ulomki, in bo imela rešitve, če je dolžina periode verižnega ulomka liha. Vendar pred tem ni znano katere rešitve imajo lihe dolžine period, tako da se vnaprej ne ve kdaj je negativna Pellova enačba rešljiva. Lahko pa se izloči določen ''n'', ker je nujni, vendar ne zadostni pogoj za rešljivost, da ''n'' ni deljiv s praštevilom oblike 4''m'' + 3. Tako na primer enačba:

: <math> x^ {2} - 3py^{2} = -1 \!\, </math>

ni nikoli rešljiva, enačba:

: <math> x^{2} - 5py^{2} = -1 \!\, </math>

pa je lahko, kadar je ''p'' = 1 ali 13, in ne, kadar je ''p'' = 41.

Cremona in Odoni sta pokazala, da je delež števil ''n'' deljivih brez kvadrata in deljivih s ''k'' praštevili oblike 4''m'' + 1 za katera je negativna Pellova enačba rešljiva, vsaj 40 %.<ref>{{sktxt|Cremona|Odoni|1989}}.</ref> Če ima enačba rešitev, njena osnovna rešitev vodi k osnovni rešitvi za pozitivni primer, če se kvadrira obe strani enačbe 1:

: <math> (x^{2} - ny^{2})^{2} = (-1)^{2} \!\, , </math>

kar da:

: <math> (x^{2} + ny^{2})^{2} - n(2xy)^{2} = 1 \!\, . </math>

Ker iz enačbe 1 sledi:

: <math> ny^{2} = x^{2}+1 \!\, , </math>

je potem:

: <math> (2x^{2} + 1)^{2} - n(2xy)^{2} = 1 \!\, , </math>

kar kaže, da so osnovne rešitve za pozitivni primer večje od rešitev za negativni primer.

== Transformacije ==

1. Sorodna enačba:

: <math> u^{2} - dv^{2} = \pm 2 \!\, </math>  (2)

se lahko uporabi za iskanje rešitev pozitivne Pellove enačbe za nekatere&nbsp;''d''. [[Adrien-Marie Legendre|Legendre]] je dokazal, da vsa praštevila oblike ''d''&nbsp;=&nbsp;4''m''&nbsp;+&nbsp;3 rešijo en primer enačbe 2, oblike 8''m''&nbsp;+&nbsp;3 rešijo negativni primer, 8''m''&nbsp;+&nbsp;7 pa pozitivnega. Njihova osnovna rešitev potem vodi do rešitve za:

: <math> x^{2} - dy^{2} =  1 \!\, . </math>

To se pokaže s kvadriranjem obeh strani enačbe 2:

: <math> (u^{2} - dv^{2})^{2} = (\pm 2)^{2} \!\, , </math>

kar da:

: <math> (u^{2} + dv^{2})^{2} - d(2uv)^{2} = 4 \!\, . </math>

Ker iz enačbe 2 sledi <math> dv^{2} = u^{2} \mp 2 </math>, je potem:

: <math> (2u^{2} \mp 2)^{2} - d(2uv)^{2} = 4 \!\, , </math>

ali preprosto:

: <math> (u^{2} \mp 1)^{2} - d(uv)^{2} = 1 \!\, , </math>

kar kaže, da so osnovne rešitve enačbe 2 manjše od rešitev enačbe 1. Na primer rešitev enačbe:

: <math> u^{2} - 3v^{2} = -2 \!\, </math>

je {''u'',''v''} = {1,1}, tako, da je rešitev enačbe:

: <math> x^{2} - 3y^{2} = 1 \!\, </math>

enaka {''x'',''y''} = {2,1}. Na drugi strani je rešitev enačbe:

: <math> u^{2} -7v^{2} = 2 \!\, </math>

enaka {''u'',''v''} = {3,1}, tako, da je rešitev enačbe:

: <math> x^{2} - 7y^{2} = 1 \!\, </math>

enaka {''x'',''y''}&nbsp;=&nbsp;{8,3}.

2. Tudi druga sorodna enačba;

: <math> u^{2} - dv^{2} = \pm 4 \!\, </math>  (3)

se lahko uporabi za iskanje rešitev Pellovih enačb za določen ''d'', v tem primeru za pozitivni in negativni primer. Če sta za naslednje transformacije v osnovni rešitvi {''u'',''v''} obe števili [[sodo število|sodi]], potem rešitev vodi do osnovne rešitve {x,y}.<ref>{{navedi splet|url= http://sites.google.com/site/tpiezas/008|title= A Collection of Algebraic Identities: Pell Equations|accessdate= |language=en}}</ref>

# Če je <math> u^{2} - dv^{2} = -4 \!\, </math> in {x,y} = {(''u''<SUP>2</SUP>&nbsp;+&nbsp;3)''u''/2, (''u''<SUP>2</SUP>&nbsp;+&nbsp;1)''v''/2}, potem je ''x''<SUP>2</SUP>&nbsp;&minus;&nbsp;''dy''<SUP>2</SUP>&nbsp;=&nbsp;&minus;1. <br /> Zgled: Naj je ''d'' = 13, potem je {''u'',''v''} = {3, 1} in {''x'',''y''} = {18, 5}.
# Če je <math> u^{2} - dv^{2} = 4 \!\, </math> in {''x'',''y''} = {(''u''<SUP>2</SUP>&nbsp;&minus;&nbsp;3)''u''/2, (''u''<SUP>2</SUP>&nbsp;&minus;&nbsp;1)''v''/2}, potem je ''x''<SUP>2</SUP>&nbsp;&minus;&nbsp;''dy''<SUP>2</SUP>&nbsp;=&nbsp;1. <br /> Zgled: Naj je ''d'' = 13, potem je {u,v} = {11, 3} in {x,y} = {649, 180}.
# Če je <math> u^{2} - dv^{2} = -4 \!\, </math> in {''x'',''y''} = {(''u''<SUP>4</SUP>&nbsp;+&nbsp;4''u''<SUP>2</SUP>&nbsp;+&nbsp;1)(''u''<SUP>2</SUP>&nbsp;+&nbsp;2)/2, (''u''<SUP>2</SUP>&nbsp;+&nbsp;3)(''u''<SUP>2</SUP>&nbsp;+&nbsp;1)''uv''/2}, potem je ''x''<SUP>2</SUP>&nbsp;&minus;&nbsp;''dy''<SUP>2</SUP>&nbsp;=&nbsp;1. <br /> Zgled: Naj je ''d'' = 61, potem je {''u'',''v''} = {39, 5} in {''x'',''y''} = {1766319049, 226153980}.

Še posebej za zadnjo transformacijo se lahko vidi, kako so rešitve za {''u'',''v''} 'veliko' manjše od {''x'',''y''}, ker sta zadnja dva [[polinom]]a šeste in pete stopnje izražena z&nbsp;''u''.

== Sklici ==

{{sklici|3}}

== Viri  ==

{{refbegin|2}}
* {{citat|last1= Barbeau|first1= Edward Joseph|authorlink1= Edward Joseph Barbeau|title= Pell's Equation|series= Problem Books in Mathematics|publisher= Springer-Verlag|year= 2003|mr= 1949691|isbn= 0-387-95529-1|ref= harv}}
* {{citat|last1= Barbeau|first1= Edward Joseph|title= Chapter Ten, Diophantine Equations|date=2010-01-05|format=PDF|url= http://www.math.toronto.edu/barbeau/hxpol10.pdf|ref= harv}}
* {{citat|last1= Cremona|first1= John E.|last2= Odoni|first2= R. W. K.|title= Some density results for negative Pell equations; an application of graph theory|doi= 10.1112/jlms/s2-39.1.16|year= 1989|journal= [[Journal of the London Mathematical Society]]. Second Series|issn= 0024-6107|volume= 39|issue= 1|pages= 16–28|ref= harv}}
* {{citat|last1= Demeyer|first1= Jeroen|title= Diophantine Sets over Polynomial Rings and Hilbert’s Tenth Problem for Function Fields|year= 2007|series= doktorska disertacija, [[Univerza v Gentu]]|url= http://cage.ugent.be/~jdemeyer/phd.pdf|page= 70|ref= harv}}
* {{citat|last1= Edwards|first1= Harold Mortimer|authorlink1= Harold Mortimer Edwards|title= Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory|year= 1996|series= [[Graduate Texts in Mathematics]]|volume= 50|publisher= [[Springer-Verlag]]|mr= 0616635|isbn= 0-387-90230-9|ref= harv}}. Izvirno objavljeno leta 1977.
* {{citat|last1= Hallgren|first1= Sean|title= Polynomial-time quantum algorithms for Pell’s equation and the principal ideal problem|doi= 10.1145/1206035.1206039|pages= Art. No. 4|year= 2007|journal= Journal of the ACM|volume= 54|issue= 1|postscript= .|ref= harv}}
* {{citat|last1= Hočevar|first1= Katja|title= Pitagorejske trojice in Pellova enačba|work=Diplomsko delo|publisher= Univerza v Ljubljani, Pedagoška fakulteta, Fakulteta za matematiko in fiziko|year= 2012|url= http://pefprints.pef.uni-lj.si/922|cobiss= 9304649|ref= harv}}
* {{citat|last1= Knorr|first1= Wilbur Richard|authorlink1= Wilbur Knorr|issue= 2|journal= Archive for History of Exact Sciences|jstor= 41133444|mr= 0497462|pages= 115–140|title= Archimedes and the measurement of the circle: a new interpretation|volume= 15|date= 1976|doi= 10.1007/bf00348496|ref= harv}}
* {{citat|last1= Lenstra|first1= Hendrik Willem mlajši|authorlink1= Hendrik Lenstra|title= Solving the Pell Equation|journal= [[Notices of the American Mathematical Society]]|volume= 49|issue= 2|pages= 182–192|year= 2002|mr= 1875156|url= http://www.ams.org/notices/200202/fea-lenstra.pdf|postscript= .|ref= harv}}
* {{citat|last1= Pinch|first1= R. G. E.|title= Simultaneous Pellian equations|journal= Math. Proc. Cambridge Philos. Soc.|volume= 103|year= 1988|issue= 1|pages= 35–46|doi= 10.1017/S0305004100064598|ref= harv}}
* {{citat|last1= Schmidt|first1= A.|last2= Vollmer|first2= U.|contribution= Polynomial time quantum algorithm for the computation of the unit group of a number field|doi= 10.1145/1060590.1060661|location= New York|pages= 475–480|publisher= ACM|title= [[Symposium on Theory of Computing|Proc. 37th Annual ACM Symposium on Theory of Computing]]|year= 2005|ref= harv}}
* {{citat|chapter= Solution d'un Problème d'Arithmétique|url= http://gdz.sub.uni-goettingen.de/no_cache/dms/load/img/?IDDOC=41029|title= Oeuvres de Lagrange, vol. 1|editor-last1= Serret|editor-first1= J.-A.|year= 1867|pages= 671–731|ref= harv}}
* {{citat|last1= Stillwell|first1= John|authorlink1= John Stillwell|year= 2002|title= Mathematics and its history|edition= 2.|publisher=Springer|isbn= 978-0-387-95336-6|url= http://books.google.com/?id=WNjRrqTm62QC&pg=PA72|ref= harv}}
* {{citat|last1= Whitford|first1= Edward Everett|date= 1912|url= http://name.umdl.umich.edu/ABV2773.0001.001|title= The Pell equation|series= doktorska disertacija|publisher= [[Univerza Columbia]]|ref= harv}}
* {{citat|last1= Wildberger|first1= N. J.|title= Divine Proportions : Rational Trigonometry to Universal Geometry|publisher= Wild Egg Books|location= Sydney|year= 2005|ref= harv}}
{{refend}}

== Nadaljnje branje ==

* {{citat|zbl= 1043.11027|last1= Williams|first1= H. C.|authorlink11= |chapter= Solving the Pell equation|pages= 325-363|editor1-last= Bennett|editor1-first= M. A.|editor2-last= Berndt|editor2-first= Bruce Carl|editor2-link= Bruce Carl Berndt|editor3-last= Boston|editor3-first= Nigel|editor3-link= Nigel Boston|editor4-last= Diamond|editor4-first= H. G.|editor5-last= Hildebrand|editor5-first= A. J.|editor6-last= Philipp|editor6-first= W.|title= Surveys in number theory: Papers from the millennial conference on number theory|location= Natick, MA|publisher= A K Peters|year= 2002|isbn= 1-56881-162-4}}

== Zunanje povezave ==

* [http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/Pell.html Pellova enačba] {{ikona en}}
* {{MathWorld|id=PellEquation|title=Pell Equation}}

{{normativna kontrola}}
{{DEFAULTSORT:Pellova enačba}}

[[Kategorija:Diofantske enačbe]]
[[Kategorija:Verižni ulomki]]