Pellova enačba
Pellova enáčba [pélova ~] (tudi Fermat-Pellova enáčba [fermá ~] ali Fermatova enačba[1] [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.[2] 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 A000037 |
x A033313 |
y 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 < −1. Za n = −1 je enačba:
in obstajajo le štiri rešitve: (±1, 0) in (0, ±1).[2] V splošnem za n < 0 končno mnogo rešitev izhaja iz korena enote za kvadratni obseg .[3] Č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.[1] 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.[1]
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
urediDo 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.[4] Č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.[4] 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.[2] Č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.[5]
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.[5]
Splošno teorijo Pellovih enačb na podlagi verižnih ulomkov in algebrske obravnave števil oblike je razvil Lagrange med letoma 1766 in 1769.[6] Dirichlet je kasneje pokazal na način ugotavljanja neskončno mnogo rešitev Pellove enačbe brez verižnih ulomkov.[1]
Rešitve
urediOsnovna rešitev prek verižnih ulomkov
urediNaj 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).[7] 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.[7]
Dodatne rešitve iz osnovne rešitve
urediKo 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
urediČ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.[7]
Kvantni algoritmi
urediHallgren je pokazal, da lahko kvantni računalnik najde reprezentacijo s produktom, opisano zgoraj, za rešitev Pellove enačbe v polinomskem času.[8] 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.[9]
Zgled
urediZgled je Pellova enačba za n = 7:
Zaporedje konvergentov za kvadratni koren iz 7 je:
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
urediPellova enačba je povezana z več drugimi pomembnimi matematičnimi področji.
Algebrska teorija števil
urediPellova 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
urediDemeyer je omenil povezavo med Pellovo enačbo in polinomi Čebišova:[10] Č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).[11]
Verižni ulomki
urediObstaja 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:
matrika enotske 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 pk−1/qk−1 in pk/qk dva zaporedna konvergenta verižnega ulomka, je determinata matrike:
enaka (−1)k.
Størmerjev izrek s Pellovimi enačbami išče pare zaporednih gladkih števil. Kot del te teorije je 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 n.
Kot je opisal Lenstra, se lahko s pomočjo Pellove enačbe reši Arhimedov problem goveda.[7]
Negativna Pellova enačba
urediNegativna Pellova enačba ima obliko:
- (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 4m + 3. Tako na primer enačba:
ni nikoli rešljiva, enačba:
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 4m + 1 za katera je negativna Pellova enačba rešljiva, vsaj 40 %.[12] Č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:
kar da:
Ker iz enačbe 1 sledi:
je potem:
kar kaže, da so osnovne rešitve za pozitivni primer večje od rešitev za negativni primer.
Transformacije
uredi1. Sorodna enačba:
- (2)
se lahko uporabi za iskanje rešitev pozitivne Pellove enačbe za nekatere d. Legendre je dokazal, da vsa praštevila oblike d = 4m + 3 rešijo en primer enačbe 2, oblike 8m + 3 rešijo negativni primer, 8m + 7 pa pozitivnega. Njihova osnovna rešitev potem vodi do rešitve za:
To se pokaže s kvadriranjem obeh strani enačbe 2:
kar da:
Ker iz enačbe 2 sledi , je potem:
ali preprosto:
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:
je {u,v} = {1,1}, tako, da je rešitev enačbe:
enaka {x,y} = {2,1}. Na drugi strani je rešitev enačbe:
enaka {u,v} = {3,1}, tako, da je rešitev enačbe:
enaka {x,y} = {8,3}.
2. Tudi druga sorodna enačba;
- (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 sodi, potem rešitev vodi do osnovne rešitve {x,y}.[13]
- Če je in {x,y} = {(u2 + 3)u/2, (u2 + 1)v/2}, potem je x2 − dy2 = −1.
Zgled: Naj je d = 13, potem je {u,v} = {3, 1} in {x,y} = {18, 5}. - Če je in {x,y} = {(u2 − 3)u/2, (u2 − 1)v/2}, potem je x2 − dy2 = 1.
Zgled: Naj je d = 13, potem je {u,v} = {11, 3} in {x,y} = {649, 180}. - Če je in {x,y} = {(u4 + 4u2 + 1)(u2 + 2)/2, (u2 + 3)(u2 + 1)uv/2}, potem je x2 − dy2 = 1.
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 polinoma šeste in pete stopnje izražena z u.
Sklici
uredi- ↑ 1,0 1,1 1,2 1,3 1,4 Hočevar (2012).
- ↑ 2,0 2,1 2,2 2,3 2,4 Whitford (1912).
- ↑ Barbeau (2010).
- ↑ 4,0 4,1 4,2 Knorr (1976).
- ↑ 5,0 5,1 Stillwell (2002), str. 72–76.
- ↑ Serret (1867).
- ↑ 7,0 7,1 7,2 7,3 7,4 Lenstra (2002).
- ↑ Hallgren (2007).
- ↑ Schmidt; Völlmer (2005).
- ↑ Demeyer (2007).
- ↑ Barbeau (2003), § 3.
- ↑ Cremona; Odoni (1989).
- ↑ »A Collection of Algebraic Identities: Pell Equations« (v angleščini). Arhivirano iz prvotnega spletišča dne 15. marca 2014.
Viri
uredi- Barbeau, Edward Joseph (2003), Pell's Equation, Problem Books in Mathematics, Springer-Verlag, ISBN 0-387-95529-1, MR 1949691
- Barbeau, Edward Joseph (5. januar 2010), Chapter Ten, Diophantine Equations (PDF)
- Cremona, John E.; Odoni, R. W. K. (1989), »Some density results for negative Pell equations; an application of graph theory«, Journal of the London Mathematical Society. Second Series, 39 (1): 16–28, doi:10.1112/jlms/s2-39.1.16, ISSN 0024-6107
- Demeyer, Jeroen (2007), Diophantine Sets over Polynomial Rings and Hilbert’s Tenth Problem for Function Fields (PDF), doktorska disertacija, Univerza v Gentu, str. 70, arhivirano iz prvotnega spletišča (PDF) dne 2. julija 2007, pridobljeno 6. februarja 2014
- Edwards, Harold Mortimer (1996), Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory, Graduate Texts in Mathematics, zv. 50, Springer-Verlag, ISBN 0-387-90230-9, MR 0616635. Izvirno objavljeno leta 1977.
- Hallgren, Sean (2007), »Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem«, Journal of the ACM, 54 (1): Art. No. 4, doi:10.1145/1206035.1206039.
- Hočevar, Katja (2012), »Pitagorejske trojice in Pellova enačba«, Diplomsko delo, Univerza v Ljubljani, Pedagoška fakulteta, Fakulteta za matematiko in fiziko, COBISS 9304649, arhivirano iz prvotnega spletišča dne 24. februarja 2014, pridobljeno 6. februarja 2014
- Knorr, Wilbur Richard (1976), »Archimedes and the measurement of the circle: a new interpretation«, Archive for History of Exact Sciences, 15 (2): 115–140, doi:10.1007/bf00348496, JSTOR 41133444, MR 0497462
- Lenstra, Hendrik Willem mlajši (2002), »Solving the Pell Equation« (PDF), Notices of the American Mathematical Society, 49 (2): 182–192, MR 1875156.
- Pinch, R. G. E. (1988), »Simultaneous Pellian equations«, Math. Proc. Cambridge Philos. Soc., 103 (1): 35–46, doi:10.1017/S0305004100064598
- Schmidt, A.; Vollmer, U. (2005), »Polynomial time quantum algorithm for the computation of the unit group of a number field«, Proc. 37th Annual ACM Symposium on Theory of Computing, New York: ACM, str. 475–480, doi:10.1145/1060590.1060661
- Serret, J.-A., ur. (1867), »Solution d'un Problème d'Arithmétique«, Oeuvres de Lagrange, vol. 1, str. 671–731
- Stillwell, John (2002), Mathematics and its history (2. izd.), Springer, ISBN 978-0-387-95336-6
- Whitford, Edward Everett (1912), The Pell equation, doktorska disertacija, Univerza Columbia
- Wildberger, N. J. (2005), Divine Proportions : Rational Trigonometry to Universal Geometry, Sydney: Wild Egg Books
Nadaljnje branje
uredi- Williams, H. C. (2002), »Solving the Pell equation«, v Bennett, M. A.; Berndt, Bruce Carl; Boston, Nigel; Diamond, H. G.; Hildebrand, A. J.; Philipp, W. (ur.), Surveys in number theory: Papers from the millennial conference on number theory, Natick, MA: A K Peters, str. 325–363, ISBN 1-56881-162-4, Zbl 1043.11027
Zunanje povezave
uredi- Pellova enačba (angleško)
- Weisstein, Eric Wolfgang. »Pell Equation«. MathWorld.