Eötvös Loránd Tudományegyetem Természettudományi Kar
A Pell-egyenlet és története Szakdolgozat
Papp Franciska Matematika Bsc., elemz® szakirány
Témavezet®k:
Szabó Csaba,
Algebra és Számelmélet Tanszék
Pongrácz András,
Budapest 2011.
CEU
Tartalomjegyzék
1. Bevezetés
2
2. Arkhimédesz és a marha-probléma
3
2.1. Arkhimédesz élete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Mese a Pell-egyenletr®l . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3. Marha-probléma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3. Pell-egyenlet
3 4 5
10
3.1. De níció, elnevezés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2. A Pell-egyenlet története . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4. A Pell-egyenlet és a lánctörtek kapcsolata
17
5. A Pell-egyenlet egy speciális esete
22
5.1. Lánctört-módszer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.2. Gy¶r¶elméleti módszer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1
1. fejezet Bevezetés A diophantoszi egyenletek megoldása igen változatos módszereket igényel, univerzális megoldási módszer nem létezik. Ez a témakör b®velkedik híres megoldatlan problémákban. Dolgozatom célja egy nevezetes diophantoszi egyenlet, a Pell-egyenlet részletesebb megismertetése, és történetének bemutatása. Már az ókori görögök is oldottak meg Pell-típusú egyenleteket. Arkhimédesz marhaproblémája is Pell-típusú egyenletre vezet, ezért el®ször a tudós életét, majd a marhaproblémát és annak megoldását ismertetem. Ezen megoldás matematikusok több száz éves munkája által vált ismertté. Ezek után de niálom a Pell-egyenletet és bevezetem a hozzá tartozó legfontosabb tételeket és de níciókat. Matematikusokon keresztül szemléltetem a Pell-egyenlet megoldási módszereinek fejl®dését, kialakulását. A Pell-egyenlet gyökeinek meghatározására számos módszer létezik: lánctörtekkel, absztrakt algebrai módszerekkel és kvantumszámítógéppel is kereshetjük a megoldásokat. A 4. fejezetben a lánctört fogalmát vezetem be, majd tételek segítségével mutatom meg, hogyan találjuk meg a Pell-típusú egyenletek megoldását a lánctört-módszer segítségével. Az utolsó fejezetben az x2 − 2y 2 = 1 Pell-egyenletnek keresem a megoldását a lánctört-módszer és a gy¶r¶elméleti módszer felhasználásával.
2
2. fejezet Arkhimédesz és a marha-probléma
2.1. Arkhimédesz élete Arkhimédesz (kb. i. e. 287., Szirakúza - i. e. 212., Szirakúza) természettudós, matematikus, lozófus, zikus, csillagász és mérnök volt. Életér®l nagyon kevés írásos dokumentum maradt fenn. Ezek a iratok sem tekinthet®k teljes érték¶eknek, mert sok bennük a bizonytalan tényez®. Arkhimédeszt minden id®k egyik legnagyobb matematikusaként tartják számon napjainkig is. Felfedezései, találmányai a mai technikával felszerelt világban is megdöbbentik az embert, és méltó csodálatot vívnak ki maguknak. Heracleides (i. e. 390. Hérakleia, - i. e. 322., görög lozófus, csillagász) megírta Arkhimédesz életét, de sajnálatos módon ez az írásos dokumentum nem maradt fenn. Arkhimédesz i. e. 287-ben született Szirakúzában, és ott is halt meg i. e. 212-ben. Fenn maradt dokumentumok szerint 75 éves korában érte a halál, csak ez alapján következtetünk születési dátumára. Édesapja Pheidiasz nagy csillagász volt, aki valószín¶leg már gyermekkorában bevezette Arkhimédeszt a természettudomány szépségeibe. Gyermekkorától kezdve jó kapcsolatot ápolt Hieron királlyal és ával, egyes feljegyzések szerint rokoni kapcsolatban is álltak. Fiatal korában Alexandriában, a kor szellemi központjában élt és tevékenykedett. Itt ismerkedett meg többek között Eratoszthenésszel (i. e. 276. Alexandria, i. e. 194., hellenisztikus matematikus, földrajztudós, csillagász, lozófus, költ®, zenész.), aki állítólag ezekben az években magánál Euklidesznél (i. e. 300. körül, görög matematikus, lozófus) lakott, és az ® tanítványa volt. Ezek alatt az évek alatt barátkozott össze Cononnal (i. e. 260.). Szirakúzába való hazatérése után a matematikai kutatásának és találmányai3
nak szentelte életét, közben levelezést folytatott Cononnal és Eratoszthenészszel ezekben a témákban. Leveleiben felfedezései publikálása el®tt mindig kikérte Conon véleményét. Eratoszthenésznek Módszer cím¶ híres írása mellett a marha-problémát is elküldte, amely szakdolgozatom alappillére. Az életér®l a római történészek is sok legendát ®riznek, melyek általában valamelyik találmányához köthet®ek. Életében híressé a zseniális mechanikai találmányai tették, ilyen például az arkhimédeszi csavar és a csigasor. Szirakúza az Arkhimédesz által szerkesztett hadigépekkel állt ellen a Marcellus (i. e. 268. - i. e. 208.) vezette római ostromnak, a II. pun háború idején. Arkihimédesz munkássága csak levelezések, elbeszélések útján maradt fenn. Felfedezeséit nem hagyta fenn az utókorra, egyetlen könyvet írt, Gömb készítése címmel. Halálának körülményeit ugyanolyan misztikum övezi, mint életét. Plutarkhosz (i. u. 45. , Khairóneia - i. u. 120.) a következ®képpen írta le a tudós halálát: A matematikus mértani idomokat tanulmányozott otthonában. Annyira elmerült ebben a munkában, hogy észre se vette amikor a rómaiak elfoglalták a várost. Egy római katona betört Arkhimédesz otthonába és felszólította, hogy azonnal kövesse ®t Marcellushoz. Arkhimédesz csak azzal a feltétellel egyezett ebbe bele, hogyha el®tte végiggondolhatja a vizsgált geometriai problémát. Ez a válasz annyira felb®szítette a katonát, hogy kardjával leszúrta a tudóst. Marcellus a gyilkos katonát megbüntette, Arkhimédeszt pedig a kívánsága szerint helyezte végs® nyugalomba. Eszerint végakaratában arra kérte rokonait, barátait, hogy legkedvesebb tételének ábráját véssék sírkövére: egy egyenl® oldalú hengerbe írt gömb és kúp körvonalait. A tétel szerint az egyenl® alapú és magasságú kúp, félgömb és henger térfogatának aránya: 1:2:3. Ebb®l arra lehet következtetni, hogy magának tulajdonította ezen arány felfedezését. Sok évvel kés®bb i. e. 75-ben a híres római szónok, Cicero megtalálta és helyreállíttatta a már elvesztettnek hitt síremléket. Kés®bb sajnos ismét elt¶nt, de 1965-ben egy hotel építkezésekor rábukkantak.
2.2. Mese a Pell-egyenletr®l A Pell-egyenlet eredetét Arkhimédesz nevéhez kapcsolják, pontosabban a tudós egyik feladványához. A feladatot marha-problémának nevezete el, és Eratoszthenésznek ajánlotta egyik levelében. Magyar nyelven Ponori Thewrewk Emil, Görög Anthólogiabeli Epigrammák cím¶ m¶vében olvashatjuk, amelyben ezen kívül, több matematikai témájú 4
epigrammát gy¶jtött össze. Érdekessége a történetnek, hogy a feladvány 8 ismeretlent tartalmaz, de csak 7 egyenletet tudunk hozzá felírni az egyenletrendszerben. Ezen kívül tartozik még hozzá 2 segédegyenlet is. Arkimédesz feltehet®leg ismerte a feladvány megoldását, ami azért csodálatraméltó, mert a fennmaradt feladványt csak a 17-18. században tudták matematikusok együttes er®vel megfejteni. A megfejtéshez a mai napig nagyon hosszas számolásra, vagy számítógépes programok segítségére van szükség. A feladvány keletkezésének körülményeit kétes körülmények övezik. A legenda szerint, Arkhimédesz egy olimpia játék alkalmával adta fel ezt a feladatot az egyik néz®társának, ezen beszélgetésnek Heiron király is tanúja volt. A néz® nehezményezte, hogy miért csak zikális olimpiát rendeznek, a tudást, az észt miért nem mérik össze hasonló keretek között. Arkhimédesznek erre az volt a válasza, hogy ez azért lehetetlen, mert a bírónak minden kérdésre tudnia kellene a választ, ezáltal nem a gy®ztest illetné meg a babérkoszorú, hanem magát a bírót. Azért, hogy az illet® megnyugodhasson, feladta neki a marha-problémát, ha azt meg tudja fejteni, akkor méltán indulhatna a szellemi olimpián. A király felajánlott díj fejében egy aranybika szobrot. Az említett versenyz® egy napot kért az eredmény kiszámolásához, Arkhimédesz nagyvonalúan két hetet adott probléma megoldásához. A történet szerint az úr sose jelentkezett a megoldással.
2.3. Marha-probléma A feladvány: A Napisten Thrinákia szigetén legeltette marháit. Négy csordája volt, az egyikben minden állat fehér, a másikban mind fekete, a harmadik csorda bikái és tehenei sárgásbarnák voltak, végül a negyedikben tarkák. Mindegyik csordában a bikák száma jóval meghaladta a tehenekét. A fehér bikák száma annyi, mint a fekete bikák fele meg egyharmada, meg valamennyi barna bika. A fekete bikáké annyi, mint a tarka bikák negyede meg ötöde meg valamennyi barna bika. Végül a tarka bika annyi van, mint a fehér bikák hatoda meg hetede meg valamennyi barna bika. A fehér tehenek száma annyi, mint az egész fekete csorda - tehát a bikák és a tehenek együtt - számának egyharmada meg egynegyede, a fekete tehenek száma annyi, mint a tarka csorda egynegyede meg egyötöde, tarka tehén annyi van, mint a barna csorda egyötöde meg egyhatoda, végül barna tehén annyi van, mint a fehér csorda egyhatodának meg egyhetedének az összege. Ha megfelel®en állítjuk fel valamennyi fehér és fekete bikát, akkor az állatok alakzata egy négyzet lesz, ha pedig 5
a barna és tarka bikákat állítjuk fel, akkor háromszöget kapunk. Az egyszer¶ség kedvéért, a következ® jelöléseket alkalmazom: x = fehér bikák,
x1 = fehér tehenek
y = fekete bikák,
y1 = fekete tenehek
z = barna bikák,
z1 = barna tehenek
t = tarka bikák,
t1 = tarka tehenek
A feladat matematikai formában: x=
y y + +z 2 3
t t + +z 4 5 x x t= + +z 6 7 y + y1 y + y1 x1 = + 3 4 t + t1 t + t1 + y1 = 4 5 z + z1 z + z1 t1 = + 5 6 z + z1 z + z1 + z1 = 6 7 y=
A fenti egyenletrendszerb®l fejezem ki az x-et, y -t és t-t. x=
742 z, 297
y=
178 z, 99
t=
1580 z 891
Mivel x, y , t ∈ N, és az együtthatójukban, a számlálójuk és a nevez®jük relatív prímszámok, ezért a z számról tudjuk, hogy oszthatónak kell lennie 297-tel, 99-cel és a 891-gyel. A három szám legnagyobb közös osztója a 891, tehát z = 891 · k , ahol k ∈ N. Ebb®l adódóan az egyenleteink: x= 2226k ,
y =1602k ,
6
t= 1580k .
Az így kapott eredményeket behelyettesítve az egyenletrendszerbe: x1 =
1896 7 y1 + k 12 2
9 t1 + 711k 20 11 3267 t1 = z1 + k 30 10 13 z1 = x1 + 689k. 42 y1 =
Ezekb®l az egyenletekb®l kifejezve x-et, y -t, z -t és t-t: x=
7206360 k, 4657
y=
4893246 k, 4657
z=
5439213 k, 4657
t=
3515820 k. 4657
egyenleteket kapjuk. Ahhoz, hogy x, y , z , t, x1 , y1 , z1 , t1 ∈ N feltételnek a megoldásaink eleget tudjanak tenni, az kell, hogy k = 4657n alakú legyen és n ∈ N. Így a 8 ismeretlenes 7 egyenletb®l álló egyenletrendszerünk megoldása: x = 10366482n,
x1 = 7206360n
y = 7460514n,
y1 = 4893246n
z = 4149387n,
z1 = 5439213n
t = 7358060n,
t1 = 3515820n.
Összesen 50389082k marha legelészik Trinákia mezején. Most felhasználom az utolsó két feltételt, amely a bikák alakzatára vonatkozik. Ha megfelel®en állítjuk fel valamennyi fehér és fekete bikát, akkor az állatok alakzata egy négyzet lesz: x + y = a2 = 17826996 = 22 ·3 29 · 4657} ·k | · 11 ·{z α
a2 = 2· α · k ⇒ k =
a2 22
·
1 α
=
a2 22 ·α2
·α
7
K=
a 2·α
,
K2 =
a2 22 ·α2
,
k = K2 · α
Ha a barna és tarka bikákat állítjuk fel megfelel®en, akkor háromszöget kapunk: t+z =
(b+1)·b 2
= 11507447 · t = |7 · 353{z· 4657} ·k β
(b+1)·b 2
= β · k , (2b + 1)2 = 8β · k + 1
(2b + 1)2 = 8 · β · k + 1 = 8 · α · β · K 2 + 1 | {z } L
L2 − 8 · α · K 2 = 1 L2 − 410286423278424 · K 2 = 1
Az egyenlet rövid megoldása: A megoldás megkönnyítése érdekében az L2 −410286423278424·K 2 = 1 egyenletet átírjuk a következ® alakba: 2 l2 − 4729494 | {z } k = 1, ahol l = L és k = 2 · 4657 · K ϕ
2 Az (l1 , k1 ) számpár az l2 − 4729494 | {z } k = 1 egyenlet minimális megoldása. (Minimális ϕ
megoldáson azt a számpárt értem, amely az egyenlet megoldásai közül a második változójában minimális.) √ l1 + k1 ϕ = 109931986732829734979866232821433543901088049+
√ 50549485234315033074477819735540408986340 ϕ =
300426607914281713365 ·
√
609 + 84129507677858393258 ·
2 √ 7766
Ezután megkeressük a minimális megoldást, amely eleget tesz a 2 · 4657|k oszthatóságnak: √ √ (l1 + k1 ϕ)2 329 = L1 + K1 410286423278424
8
ki =
(l1 + k1 ϕ)4 658i −
1 (l1 +k1 ϕ)
368238304
2 (i = 1, 2, . . .)
Hosszú számolások után kapjuk meg az összes marha számát, gyelembevéve az utolsó két feltételt. (Ha megfelel®en állítjuk fel valamennyi fehér és fekete bikát, akkor az állatok alakzata egy négyzet lesz, ha pedig a barna és tarka bikákat állítjuk fel, akkor háromszöget kapunk.) Az összes marha száma: 7, 7602714 . . . · 10206544 . A teljes megoldás 47 oldal terjedelm¶, ezért is egészen elképeszt®, ha Arkhimédesz valóban meg tudta oldani ezt a feladványt. Fontos kérdés lehet akár az is, hogy Arkhimédesz biztosan tudta-e, hogy a válasz létezik.
9
3. fejezet Pell-egyenlet
3.1. De níció, elnevezés Ebben a fejezetben bemutatom a dolgozatom f® témáját a Pell-egyenletet, és de niálok néhány fogalmat, amelyeket a kés®bbiek során felhasználok. De níció: Diophantoszi egyenletnek általában olyan egész együtthatós algebrai egyenletet nevezünk, melynek a megoldásait is az egész (esetenként a racionális) számok körében keressük. Az ax + by = c egyenletben a, b, c rögzített egész számok, és megoldáson, például egy (x, y) egész számpárt értünk. A Pell-egyenlet az egyik legegyszer¶bb diophantoszi egyenlet. De níció: Pell-egyenletnek nevezzük az x2 − dy2 = 1 alakú diophantoszi egyenletet, illetve általánosabb formában az x2 − dy 2 = b alakú egyenleteket, ahol d ∈ N, b ∈ Z és √ d∈ / Q. Az (x, y) megoldásokat tehát az egészek között keressük. Az x2 − dy 2 = 1 egyenletnek vannak triviális megoldásai: x = ±1, y = 0. Ha d < −1, akkor x2 − dy 2 > 1, kivéve, ha x = y = 0, így ez esetekben nincs megoldása az x2 − dy 2 = 1 egyenletnek. Ha pedig d = −1, akkor további két triviális megoldása van: x = 0, y = ±1. Végül, ha d = n2 esetben is csak triviális megoldásai vannak, hiszen az x2 − dy 2 = x2 − n2 y 2 = (x + ny) (x − ny) = 1
esetben x + ny = x − ny = ±1,
10
ami ismét csak az x = ±1, y = 0 esetekben áll fönn. Így csak azt az esetet kell vizsgálnunk, amikor d > 0, és nem négyzetszám. Nyilvánvaló, hogy elegend® a pozitív megoldásokat megkeresni, és ha x1 , y1 ∈ N megoldás, akkor ln.k.o.(x1 , y1 ) = 1. Pell-egyenletre vezetett a korábbiakban említett marha-probléma is.
A Pell-egyenlet elnevezése A Pell-egyenlet John Pell (1611-1685) angol matematikusról kapta a nevét, aki munkássága során algebrával és számelmélettel foglalkozott. F® munkája egy táblázat megalkotása volt, amelyet 1668-ban adott ki, amelyben az els® 100000 szám szorzatra bontása szerepelt. Sokat publikált, f®bb írásai: Idea of Mathematics (1638), Controversiae de vera circuli mensura (1647). Kés®bb jutott csak napvilágra, hogy Euler tévesen nevezte el a x2 − dy 2 = 1 típusú egyenleteket Pell-egyenletnek, az érdemi munka Lord Brouncker nevéhez f¶z®dik.
3.2. A Pell-egyenlet története A Pell-típusú egyenletek több évszázadon keresztül foglalkoztatták a matematikusokat. Az egyenletet el®ször Diophantosz nevéhez köthetjük, mivel a Pell-egyenlet egy diophantoszi egyenlet. Kés®bbiekben két indai matematikus, Aryabhata és Brahmagupta az euklideszi algoritmus felhasználásával közelítette meg a problémát. Ezek után Bhaskara, Brahmagupta módszerét továbbfejlesztve megoldásokat el®állító algoritmust adott meg az x2 − dy 2 = 1 típusú egyenletekre. Több száz évig a probléma feledésbe merült, amíg Fermát felhívására a 17-18. században él® matematikusok újabb megoldási módszereket nem kerestek. A 17. században Lord Brouncker a lánctört-módszerével általános eljárást adott a Pell-típusú egyenletek megoldására, amely helyességét kés®bb Lagrange bizonyította. Ebben a fejezetben err®l a fejl®désr®l írok részletesebben. Diophantoszt (kb. i. e. 250.) az egyenletekkel kapcsolatos munkája emelte ki a görög matematikusok közül. Szakított a görög geometrikus hagyományokkal, és szinte kizárólag algebrai és számelméleti feladatokkal foglalkozott. Diophantoszt tekintik az algebrai jelrendszer megalapítójának. Els® és másodfokú egyenleteket oldott meg, ezek megoldásait és együtthatóit az egész számok körében kereste. Minden feladatában speciális számértékeket használt, soha nem mondott ki általános tételeket. Többségében másodfokú egyen11
letekre vezet® feladatokat oldott meg. Munkája során több, mint 130 egyenlet megoldását vezette le, minden esetben csak egyetlen gyököt keresett meg. Nem dolgozott ki általános megoldási módszert, ahogyan ezen egyenleteket nem is osztályozta. A kapott eredményei helyességét csupán azzal igazolta, hogy azok a behelyettesítéskor kielégítették a feladat feltételeit. Munkásságánál meg kell még említenünk a diophantikus approximációt, amely a valós számok racionális számokkal való közelítését vizsgálja. Látható az, hogy Diophantosz munkássága lényegében kiindulópontját képezte számos algebrai és számelméleti kutatásnak, mint a Pell-típusú egyenleteknek is. Aryabhata (500.) és Brahmagupta (598-670) közös és egyéni felfedezései fontos szerepet játszottak az x2 −dy 2 = 1 típusú egyenletek megoldásainak megtalálásában. Munkásságuknak jellemz® vonása volt az aritmetikai algebrai jelleg, amely megmutatkozik abban, hogy szerettek egyenletekkel foglalkozni. Az x2 − dy 2 = 1 típusú egyenlet megoldását az euklideszi algoritmusra alapozták. Új egyedi jelölésrendszert vezettek be, amelyet a lánctört ®sének is tekinthetünk. Ez azért is fontos, mert a lánctörtek módszere a Pelltípusú egyenletek ma ismert megoldási lehet®ségeinek egyike. (A lánctörtekkel a kés®bbiekben még részletesebben foglalkozom.) Közös munkájuk során racionális megoldásokat találtak a Pell-egyenletre, mégpedig a következ® módon: Észrevették, hogy ha az ax21 − y12 = b1 és az ax22 − y22 = b2 egyenleteknek van megoldása, akkor a b1 b2 -nek is, ugyanis legyenek x1 , y1 és x2 , y2 , olyanok, hogy ax21 − y12 = b1 ,
ax22 − y22 = b2 .
Ekkor ezek felírhatóak √ √ b1 = x1 a − y1 · x1 a + y1 ,
√ √ b2 = x2 a − y2 · x2 a + y2
alakban, és a szorzatuk: b1 b2 = (ax1 x2 ± y1 y2 )2 − a (x1 y2 ± x2 y1 )2
kiadja a kívánt megoldást. Brahmagupta ennek alapján felfedezte a kompozíciós módszert az ax21 − y12 = b1 egyenletre, amely az (a, b) és (c, d) megoldáspárok segítségével további megoldást eredményezett. A módszer a következ®: Ha (a, b) és (c, d) megoldása az egyenletnek, akkor 12
(ac + Dbd, ad + bc) is. Ugyanis 1
1
}| { z }| { a2 − Db2 · c2 − Dd2 = (ac + Dbd)2 − D (ad + bc)2 . | {z }
z
1
Azt az esetet is vizsgálta, mikor az a=c és b=d, ekkor az (a2 + Db2 , 2ab) is megoldása lesz az egyenletnek. Bhaskara (1114-1185) továbbfejlesztette Brahmagupta és Aryabhata munkáját, a következ® módszerrel adott megoldást az x2 − dy 2 = 1 egyenletre. Els® lépésben próbálgatással keresett olyan x1 , y1 , b1 számokat, amelyek kielégítették az x2 − dy 2 = b1 egyenletet, emellett az (y1 , b1 ) = 1 feltételnek is megfeleltek. Következ® lépésben keresett olyan y2 , 1 z ∈ Z számokat, hogy y1 z+x = y2 , vagyis y1 z + x1 = b1 y2 és z 2 − d a lehet® legkisebb b1 2 = b2 ∈ Z, dy22 + b2 pedig négyzetszám, amelyet x22 -tel jelölünk, vagyis legyen. Ekkor z b−d 1 dy22 + b2 =x22 . Az eljárás megismétlésével kapott az egész számoknak egy sorozatát: b1 , b2 , . . . , bk , így végül bk = 1 azaz dyk2 + 1 = x2k . Ekkor az (xk , yk ) lesz az x2 − dy 2 = 1 eredeti egyenletünk megoldása. A 17. században több neves matematikus is foglalkozott az x2 − dy 2 = 1 egyenlettel. Ennek a valószín¶síthet® oka az lehetett, hogy Fermat (1601-1665) felhívta angol, francia, német tudóstársainak gyelmét ezen és az ilyen típusú egyenletek megoldásának problémájára. maga is sokat foglalkozott a diophantoszi határozatlan analízissel, amely a racionális számok között keresi a megoldást a határozatlan egyenletekre és egyenletrendszerekre. Lord Brouncker-t (1605-1675) az els® európai tudósként tartják számon, aki általános megoldást adott az x2 − dy 2 = 1 egyenletre, felfedezte a lánctört módszerét. A lánctört segítségével az egyenlet általános megoldási módszere: √ √ x+y d · x−y d =1 | {z } | {z }
nagy
Ekkor
kicsi
√ x √ x − y d ≈ 0 ⇒ ≈ d. y
√
A d lánctört alakjának valamely kezd® szelete lesz az (x, y) megoldáspár. Brouncker ezt a megoldási módszert nem bizonyította. Megoldott több x2 − dy 2 = 1 típusú 13
egyenletet, például az x2 − 313y 2 = 1-et. Az egyenlet legkisebb megoldása az (x, y) = (32188120829134848, 1819380158564160) számpár. Állítása szerint a megoldáson csupán néhány órát dolgozott. Frenicle de Bessy (1605-1675) csak kedvtelésb®l foglalkozott ezen problémával, munkája mégsem elhanyagolható. Táblázatba gy¶jtötte a minimális megoldáspárokat D ≤ 150-ig. (De níció: Minimális megoldáson azt a számpárt értem, amely az egyenlet megoldásai közül a második változójában minimális.) Wallis, John (1616-1703) volt az, aki publikálta ezen matematikusok 1657-58-ban folytatott levelezéseit, eredményeit és igazolta Brahmagupta módszerének helyességét. Rahn (1622-1676) könyvében megjelenik az x2 − dy 2 = 1 egyenlet általános megoldása, amely megírásában Pell segédkezett. Ez az egyedüli biztos kapcsolat Pell és az x2 − dy 2 = 1 típusú egyenletek között. Leonhard Euler (1707-1783) több szempontból is fontos szerepet játszott az egyenlet történetében. Eulert®l származik a "Pell-egyenlet" elnevezése (összekeverte Lord Brouncker munkáját John Pell eredményeivel). A diophantikus problémák megoldásának segédeszközeként kidolgozta és szigorú alapokra helyezte a lánctört fogalmát. A lánctört módszert használta fel a megoldások megtalálásához, ezen módszerét kés®bb Lagrange nomította. Hasonlóan nagy eredményeket ért el a diophantoszi analízis területén. Lagrange (1736-1813) - Legendre (1752-1833) közösen dolgozták ki a következ® tételt: Tétel: Az x2 − dy2 = 1 egyenletnek végtelen sok megoldása van. Minden (x, y) pozitív megoldás, a legkisebb pozitív (x1 , y1 ) megoldásokból származtatható, valemely k ∈ N segítségével az alábbi módon: √ √ k x + y D = x1 + y 1 D .
(3.1)
√
Ekkor x1 + y1 d minimális. Az összes megoldást az √
√ n x + y d = ± x1 + y 1 d .
n = 0, ±1, ±2, . . .
(3.2)
képlettel meghatározott x, y egész számok adják. A x2 − dy 2 = 1 egyenlet felírható:
√ √ x+y d x−y d =1
(3.3)
alakban. A 3.3 -as egyenl®ségb®l látszik, hogy:
√ (−n) √ n x1 + y 1 d = x1 − y1 d .
14
(3.4)
Ezért 3.2 az
√ √ n x + y d = ± x1 ± y1 d
n = 0, 1, 2, . . .
(3.5)
formában is megadható.
Bizonyítás: A bizonyítás során többször is fel fogjuk használni, hogy ha (x1 , y1 ), illetve (x2 , y2 ) egyegy megoldása az x2 − dy 2 = 1 egyenletnek, akkor a megoldások alábbi értelemben vett szorzata is megoldás lesz: √ √ x1 x2 + dy1 y2 + (x1 y2 + y1 x2 ) d x1 x2 + dy1 y2 − (x1 y2 + y1 x2 ) d = 1.
Ebb®l adódik, hogy x3 = x1 x2 + dy1 y2 , y3 = x1 y2 + y1 x2 is megoldása lesz a x2 − dy 2 = 1 egyenletnek. A fentiekb®l és a 3.4 -b®l nyilvánvalóan következik, hogy a 3.2 képlettel megadott (x, y) számpárok kielégítik a x2 −dy 2 = 1 egyenletet. Most belátjuk, hogy ez az összes megoldás. Tegyük fel indirekt módon, hogy létezik egy (x, y) megoldás, amely nem ilyen alakú. Ekkor nyilván (−x, −y) is megoldás és ez sem szerepel a fentiekben de niált megoldások között. √ Ezért feltehet®, hogy x + y d > 0. Ekkor létezik olyan t egész szám, melyre:
√ t √ (t+1) √ x1 + y1 d < x + y d < x1 + y1 d .
(3.6)
√ t
A 3.6 -at x1 + y1 d -nal beszorozva √ √ t √ 1 < x + y d x1 + y1 d < x1 + y1 d
adódik. Itt
(3.7)
√ t √ √ x + y d x1 + y 1 d = x0 + y 0 d
a megoldások összeszorzásával keletkezett, tehát (x0 , y 0 ) is megoldás, azaz
√ √ x0 + y 0 d x0 + y 0 d = 1.
(3.8)
A 3.7 -beli els® egyenl®tlenség szerint √ x0 + y 0 d > 1.
15
(3.9)
Így a 3.8 miatt
√ 0 < x0 − y 0 d < 1.
(3.10)
A 3.10 miatt nem lehetségesek az y 0 = 0, az x0 < 0, y 0 > 0 valamint az x0 > 0 és a y 0 < 0 esetek, a 3.9 miatt pedig nem fordulhat el® az x0 < 0, y 0 < 0. Ezért x0 > 0, y 0 > 0, ez √ azonban 3.7 szerint ellentmond x1 + y1 d minimalitásának. Lagrange bizonyította be els®ként Euler és Brouncker azon felfedezését, hogy bármely szóba jöhet® d-re végtelen sok megoldása van az x2 − dy 2 = 1 egyenletnek. Ginatempo (1969) nevéhez f¶z®d® "Brute force" algoritmus a minimális (x, y) számpár megtalálásában segít. Ez az algoritmus az összes x2 − dy 2 = 1 egyenletre alkalmazható, viszont hasznossága igen mivel problémája, hogy nagyok a korlátok. h√ csekély, i Tétel: Legyen d = D . Az x2 − dy2 = 1 egyenlet minimális megoldására teljesül, hogy: y1 ≤ 2 (d + 1)
2 d+1 3
2
d.
x1 ≤ (d + 1) d.
A következ® példán keresztül jól látható, miért is nem hasznosítható ez igazán. Példa: D=61 Ekkor az y1 ≤ 563257931412,
x1 ≤ 4506053451300.
Az egyenlet tényleges alapmegoldása ebben az esetben: 17663190492 − 61 · 2261539802 = 1.
Vagyis x1 = 1766319049, y2 = 226153980.
Ebb®l jól látható, hogy a korlátok nem pontosak, a korlátok túl nagyok.
16
4. fejezet A Pell-egyenlet és a lánctörtek kapcsolata Lánctörtek Tetsz®leges α valós szám esetén tekintsük a következ® algoritmust. Legyen c0 = bαc
és γ1 = {α} ,
ekkor (4.1)
α = c0 + γ1 .
Ha γ1 6= 0, akkor legyen c1 =
j k 1 γ1
és γ2 =
n o 1 γ1
1 , ekkor α = c0 + γ1 = c0 + c1 +γ . 2
Ha γ2 6= 0, akkor γ12 egész- és tört részét képezzük stb. Általában ha a c0 , c1 , . . . , cn és γ1 , . . . , γn+1 értékeket már meghatároztuk, és γn+1 6= 0, akkor legyen cn+1 =
és
γn+1
γn+2 =
1
1 γn+1
17
.
(4.2)
Ekkor α = c0 +
1 c1 +
.
1 c2 +
...
(4.3)
1 1 cn + c n+1 +γn+2
A 4.3 jobb oldalán álló sok emeletes törtet (véges) lánctörtnek nevezzük, és az egyszer¶bb írásmód kedvéért bevezetjük rá az L [c0 , c1 , . . . , cn , cn+1 + γn+2 ] jelölést. Ha γn+1 = 0, akkor az eljárás véget ér. Az ily módon kapott c0 , c1 , . . ., egész számokat az α lánctörtjegyeinek nevezzük. De níció: Egy α valós szám lánctörtjegyein a 4.1 és a 4.2 képletekkel de niált (véges vagy végtelen) c0 , c1 , . . . számsorozatot értjük. Megjegyzés: A de níció alapján világos, hogy a lánctörtjegyek egyértelm¶en meghatározott egész számok, és ci > 0, ha i ≥ 1. Példa 1: Legyen α = 201 . Ekkor 65 201 6 =3+ , 65 65 5 65 = 10 + , 6 6 6 1 =1+ , 5 5 5 = 5 + 0, 1
A
201 65
c0 = 3, c1 = 10, c0 = 1, c0 = 5.
lánctört jegyei tehát: 3, 10, 1, 5. Ez egyúttal azt is jelenti, hogy: 201 = L [3, 10, 1, 5] = 65
3 1 10+
1 1+ 1 5
. Abban az esetben, ha az α irracionális, akkor a γn is irracionális, ekkor a lánctörtbe fejtés algoritmusa sohasem áll le. Ebben az esetben a kifejezés így néz ki: α = c0 +
1 c1 +
1 c2 +
18
...
1 cn +γn+1 .
√
Példa 2: Legyen α = 2. Ekkor: √
2=1+
√ 2−1 ,
c0 = 1,
√ √ 1 = 2+1=2+ 2−1 , 2−1 √ √ 1 √ = 2+1=2+ 2−1 , 2−1 √
c1 = 2, c1 = 2,
.. . √
√
A 2 lánctörtjegyei tehát: 1, 2, 2, 2, . . .. Erre bevezetjük a 2 = L [1, 2, 2, 2, . . .] jelölést és a "végtelen lánctört" elnevezést. Az algoritmus során kapott véges lánctörteket nevezzük a végtelen lánctört csonkításainak. Mivel ezek racionális számok, így ezek a csonkítások α egy racionális közelítését adják meg.
Jelölése: L [c0 , c1 , . . . , cn ] =
an bn
.
A Pell-egyenlet és a lánctört kapcsolata A lánctörtek elméletéb®l tudjuk a következ®t. Lemma: Legyen α irracionális, n ∈ N, továbbá αn = Ha p, q ∈ Z és 1 ≤ q < bn+1 , akkor
an bn
a lánctört n-edik kezd®szelete.
|bn α − an | ≤ |qα − p| .
Ez mutatja, hogy a lánctörtek adják valamilyen értelemben az irracionális számok legjobb racionális közelítését. Lord Brouncker felfedezte, hogy az x2 − dy 2 = 1 egyenlet megoldásainak hányadosa √ √ kapcsolatban van a d racionális közelítésével, ugyanis nemcsak az igaz, hogy xy ≈ d, hanem az alábbi er®s állítás is.
Tétel: Legyen α irracionális szám. Ha a és
α −
p q
(p ≥ 1, és (p, q) = 1) racionális szám,
p 1 < 2, q 2q
19
akkor valamely n ∈ N-re
p an = αn = , q bn
ahol αn az α lánctört alakjának n-edik kezd®szelete. Bizonyítás: Tegyük föl, hogy pq -ra teljesülnek a tétel feltételei, de nem egyezik meg egyetlen kezd®szelettel sem. Mivel a bk sorozat szigorúan monoton növekv®, pontosan egy olyan n ∈ N van, amelyre bn ≤ q < bn+1 . Ezen n-re teljesül, hogy: |bn α − an | ≤ |qα − p| = q α −
p 1 < . q 2q
Ebb®l az egyenlet bn -nel való leosztásával egyszer¶en kapható, hogy: a n α − < 1 . bn 2qbn
Mivel feltevésünk szerint
p q
6=
an bn
, így a qan − pbn különbség nem lehet 0, így 1 ≤ |qan − pbn | .
Ebb®l azonban következik, hogy: qan − pbn an p an 1 = − ≤ − α + α − ≤ qbn qbn bn q bn
A kapott:
p 1 1 < + 2. q 2qbn 2q
1 1 1 < + 2 qbn 2qbn 2q
egyenl®tlenségb®l q < bn adódik, amely ellentmond n választásának. Vagyis pq az α n-edik kezd®szelete. √ A következ® tétel megmutatja, hogy a d szám lánctört alakjából, a lánctört csonkításával hogyan tudjuk meghatározni a x2 − dy 2 = 1 Pell-egyenlet megoldásait. √ Tétel: Ha a, b pozitív, és megoldása az x2 −dy2 = 1 egyenletnek, akkor az ab a d lánctört alakjának valamely kezd®szelete. 20
√ √ a + db = 1. Eszerint
Bizonyítás: Tegyük föl, hogy a2 − db2 = 1, azaz a − db
√ a > b d.
Átalakítva az egyenletet azt kapjuk, hogy: a b
−
√
d=
1√ b(a+b d)
.
√
Alkalmazva az a > b d becslést a következ® adódik: √ √ a √ 1 d d 1 < √ = √ = 2. 0< − d= √ √ b 2b 2b2 d b a+b d b b d+b d
Ezzel az egyenl®tlenséggel és az el®z® tételben szerepl® bizonyítás segítségével bebizonyítottuk a tételt. √ Példa: Az el®z® tételek felhasználásával, és a d lánctört alakja segítségével meghatározzuk az x2 − 7y 2 = 1 egyenlet minimális (x0 , y0 ) megoldáspárját. √ A 7 lánctört alakja: L 2, 1, 1, 1, 4 . √ Elkezdem vizsgálni a 7 lánctört alakjának kezd®szeleteit: n = 0.
n = 3.
2 1
22 − 7 · 12 = (−3) 6= 1
1 =3 1 1 5 2+ 1 = 2 1+ 1
n = 1. n = 2.
2= 2+
2+
32 − 7 · 12 = 2 6= 1 52 − 7 · 22 = (−3) 6= 1
1 8 = 1 3 1 + 1+ 1
82 − 7 · 32 = 1
1
A negyedik lépésben az egyenletbe való visszahelyettesítéskor mindkét oldalon 1-et kap√ tunk eredményül, tehát megtaláltuk az x2 − 7y 2 = 1 egyenlet minimális megoldását, a 7 lánctört alakjának segítségével. Eszerint a (8, 3) a minimális megoldás.
21
5. fejezet A Pell-egyenlet egy speciális esete Ebben a fejezetben az x2 − 2y 2 = 1 egyenlet összes megoldását adjuk meg.
5.1. Lánctört-módszer √
Az el®z® fejezetben leírtak szerint jártunk el. Már kiszámoltuk, hogy a 2 lánctört alakja √ 2 = L [1, 2, 2, . . .] (4.f ejezet). Ennek a csonkításával a következ® törtek kaphatók meg: L [1] = 11 . Ez nem ad megoldást: 12 − 2 · 12 = (−1). L [1, 2] = 23 . Ebb®l a (3, 2) minimális megoldás adódik: 32 − 2 · 22 = 1. A 3.2. fejezetben szerepl® tétel alapján a megoldások így adhatók meg: √ √ n x + y 2 = ± 3 + 2 2 , n ∈ Z.
5.2. Gy¶r¶elméleti módszer Az x2 − 2y 2 = 1 egyenlet egész megoldásait keressük. Ehhez el®ször egy nagyságrendi feltételt állapítunk meg x-re és y -ra. Állítás: Ha x2 − 2y2 = 1, akkor |y| < |x| < 2 |y| kivéve, ha y = 0 és x = ±1. Bizonyítás: Indirekte tegyük fel, hogy |x| ≤ |y|. Ekkor x2 ≤ y2 . A feltétel szerint tehát 2y 2 + 1 ≤ y 2 , azaz y 2 + 1 ≤ 0, ami ellentmondás. A másik egyenl®tlenség bizonyításához tegyük fel, hogy |x| ≥ 2 |y|. Négyzetre emelés után ebb®l azt kapjuk, hogy x2 ≥ 4y 2 . Kifejezve az x2 -et ebb®l 2y 2 + 1 ≥ 4y 2 adódik, ami 1 ≥ 2y 2 -re vezet. Ennek csak az y = 0 lehet megoldása. Azt az egyenletbe beírva x = ±1-et kapunk. 22
Az egyenlet bal oldala szorzattá alakítható: √ √ x2 − 2y 2 = x + 2y x − 2y . √
Ennek a lépésnek az a hátránya, hogy az x + 2y alakú kifejezések általában nem egész számok. Ezért egy, az egészeknél b®vebb gy¶r¶ben kell dolgoznunk, ha az egyenletet meg szeretnénk oldani. √ √ De níció: Z 2 = a + b 2|a, b ∈ N . Ez a halmaz a szokásos (valós számokon értelmezett) összeadás és szorzás m¶veletekkel egy kommutatív, egységelemes, nullosztómentes gy¶r¶t alkot. √ A Pell-egyenlet megoldásában segítségünkre lesz a Z 2 gy¶r¶ számelmélete. Épp ezért most összefoglaljuk a legfontosabb de níciókat és tételeket, amik a megoldáshoz szüksé√ gesek lesznek. Számelméleti szempontból vizsgálva Z 2 egy euklideszi gy¶r¶, hiszen √ √ megadható rajta egy euklideszi norma. Egy a + b 2 alakú szám normája N a + b 2 = √ √ a2 − 2b2 . Ez a szám a + b 2 ∈ Z 2 esetén egy egész szám. √ √ √ A Z 2 gy¶r¶ben de niálható a konjugálás is: a + b 2 = a − b 2. Vegyük észre, hogy N (z) = zz . Mivel a konjugálás szorzattartó, így a fenti összefüggés miatt ugyanez igaz a normára is: N (z1 z2 ) = N (z1 ) N (z2 ) . √
Ez számunkra azért lesz fontos, mert így a z = a + b 2 szám normája megegyezik a Pell-egyenletünk bal oldalával. Ezért azokat a számokat keressük, amelyek normája 1. √ Állítás: z ∈ Z 2 egység akkor és csak akkor, ha N (z) = ±1. Bizonyítás: ⇐ Ha N (z) = ±1, akkor zz = ±1, így ±z inverze z -nek. √ ⇒ Ha z egység, akkor létezik r ∈ Z 2 , amire rz = 1. Alkalmazzuk a normát: N (r) N (z) = N (1). Itt N (r) és N (z) egész számok. A szorzatuk csak úgy lehet 1, ha mindkett® ±1. √ A Pell-egyenlet bal oldalára most úgy tekintünk, hogy az az x + y 2 elem normája √ Z 2 -ben. Ez alapján az (x, y) számpár pontosan akkor megoldása a Pell-egyenletnek, √ ha N x + y 2 = 1. Mivel a norma szorzattartó, így ha N (z) = 1, akkor N z k = 1 minden k ∈ Z -re. ( Itt z −1 a z egység egyértelm¶ inverzét jelöli.) √ Állítás: Z 2 -ben végtelen sok 1-normájú elem van. √ Bizonyítás: Észrevesszük, hogy N 3 + 2 2 = 1, hiszen 32 − 2 · 22 = 1. √ k A korábbi meg gyelések szerint N 3 + 2 2 = 1 minden k ∈ N-re. 23
√
Ezek a hatványok mind különböz®ek, hiszen 2 együtthatója k növelésével szigorúan monoton n®. √ Célunk az összes megoldást megtalálni, vagyis Z 2 összes 1-normájú elemét meghatározni. Ebben éppen az el®z® állítás gondolatmenete ad ötletet. √ √ Tétel: Legyen x + y 2 ∈ Z 2 egy 1-normájú elem, amelyre x, y > 0. √ √ n Ekkor x + y 2 = ± 3 + 2 2 , n ∈ Z. Bizonyítás: |y| szerinti teljes indukcióval. √ |y| = 0, ekkor x2 = 1, tehát x = ±1. Ez az 1, (−1) ∈ Z 2 elemeket adja meg, amelyek valóban felírhatóak a fenti alakban (n = 0). Tegyük fel, hogy |y| ≤ (k − 1) esetén igaz az állítás. Legyen most |y| = k , és tegyük fel, √ hogy N x + y 2 = 1. 1. eset: y > 0. Vegyük észre, hogy: √ √ √ √ x+y 2 3−2 2 =N x+y 2 N 3−2 2 =1·1=1 √ √ √ Tehát x + y 2 3 − 2 2 egy 1-normájú elem Z 2 -ben. Ha kibontjuk a zárójeleket: √ √ √ x + y 2 3 − 2 2 = (3x − 4y) + (3y − 2x) 2. N
A
√
2 együtthatójának abszolútértéke ennek során csökkent 3y − 2x < y,
/ − y, +2x
2y < 2x,
/:2
y < x.
√
Az indukciós feltétel szerint tehát készen vagyunk, hiszen ha x + y d
√ 3−2 2 =
√ n √ √ n+1 ± 3 + 2 d , akkor x + y 2 = ± 3 + 2 2 .
2. eset: y < 0.
√
Az el®z® eset mintájára történik a bizonyítás. Most 3 + 2 2 -vel szorzunk: N
A
√ √ √ √ x + y 2 3 + 2 2 = N x + y 2 N 3 + 2 2 = 1 · 1 = 1.
√ 2 együtthatója itt a 3y +2x. Vizsgáljuk meg, hogy ez abszolútértékben tényleg kisebb
24
|y|-nál. Ehhez két egyenl®tlenségre van szükségünk: y < 3y + 2x < −y . y < 3y + 2x: y < 3y + 2x
/−y
0 < 2y + 2x
/:2
0 < y + x, mert |y| < |x| . 3y + 2x < −y : 3y + 2x < −y 2x < −4y
/ − 3y /:2
x < −2y = 2 |y| .
A tétel alapján ismét világos, hogy a minimális megoldás a (3, 2) számpár.
25
Irodalomjegyzék [1]
: Solving the Pell Equation, Sprin-
Michael J. Jacobson, Jr., Hugh C. Williams
ger,
2000
[2]
T. L. Heath
: The works of Archimedes, London
[3]
Sir Thomas Heath
[4]
Nelson H. L.
[5]
Freud Róbert, Gyarmati Edit
: A history of Greek matematics, Oxford, 1921
: A solution to Archimedes' cattle problem, 1980 : Számelmélet, Nemzeti Tankönyvkiadó, Budapest,
2000 [6]
K. A. Ribnyikov
[7]
Dirk J. Struik
[8]
Sain Márton
: A matematika története,
Tankönyvkiadó,
: A matematika rövid története, Gondolat
: Matematikatörténeti ABC,
26
Budapest, 1974
Kiadó,
Tankönyvkiadó,
1958
Budapest, 1974
Nyilatkozat
Név: Papp Franciska ELTE TTK, Matematika B.Sc. szak, Matematikai elemz® szakirány ETR azonosító: PAFPAAT.ELTE Szakdolgozat címe: A Pell-egyenlet és története
A szakdolgozat szerz®jeként fegyelmi felel®sségem tudatában kijelentem, hogy a dolgozatom önálló munkám eredménye, saját szellemi termékem, abban a hivatkozások és idézések standard szabályait következetesen alkalmaztam, mások által írt részeket a megfelel® idézés nélkül nem használtam fel.
Budapest, 2011. január 4.
Papp Franciska
27
