Diofantoszi egyenlet

A matematikában a diofantoszi egyenlet vagy diofantikus egyenlet olyan egész együtthatós, általában többismeretlenes algebrai egyenlet, amelynek megoldásait az egész, ritkábban a természetes számok, illetve racionális számok körében keressük. A 3. században élt görög matematikusról, Diophantoszról kapta nevét.

Legegyszerűbb az elsőfokú, kétismeretlenes diofantoszi egyenlet, amelyet ax + by = c alakban szokás felírni. Ennek az egyenletnek akkor és csakis akkor van egész számokból álló megoldása, ha az ismeretlenek együtthatóinak legnagyobb közös osztója a jobb oldalra írt állandónak is osztója. Az elsőfokú diofantoszi egyenlet megoldására ismeretesek különböző eljárások, de a magasabb fokúakra alig ismerünk általános megoldási módszereket.

Példák

• $x^{2}-y=0$ megoldásai ezek az $(x,y)$ számpárok: …, (−3, 9), (−2, 4), (−1, 1), (0, 0), (1, 1), (2, 4), (3, 9), …; általában: $(x,y)=\left(n,n^{2}\right)$, ahol $n\in \mathbb {Z} .$
• $x^{4}+y^{2}+z^{20}=-7$ nem oldható meg, mivel a baloldal sosem negatív, lévén négyzetszámok összege.
• $3x=4$ nem oldható meg, mivel a 4 nem osztható 3-mal, így nincs olyan egész szám, melynek háromszorosa négy.

Lineáris egyenletek

Az $ax+by=m$ egyenlet egész számokban akkor és csak akkor oldható meg, ha $(a,b)|m$. Ha kikötjük, hogy a,b,m pozitív egész legyen és $(a,b)=1$, akkor pontosan $(a-1)(b-1)/2$ olyan m szám van, ami nem állítható elő nemnegatív x-szel és y-nal $ax+by$ alakban, a legnagyobb közülük $(a-1)(b-1)-1$. Általában az $a_{1}x_{1}+\cdots +a_{n}x_{n}=m$ egyenlet pontosan akkor oldható meg egészekben,ha $(a_{1},\dots ,a_{n})|m$.

Pell-egyenlet

A Pell-egyenlet az $x^{2}-dy^{2}=1$ diofantoszi egyenlet, ahol $d>0$ nem négyzetszám. Az $x=\pm 1$, $y=0$ megoldás triviális, tehát a nemtriviális megoldásokat keressük. Minden Pell-egyenletnek végtelen sok megoldása van és ezek $(\pm x_{n},\pm y_{n})$ alakban írhatók, ahol $x_{n}+{\sqrt {d}}y_{n}=(x_{1}+{\sqrt {d}}y_{1})^{n}$ teljesül ($(x_{1},y_{1})$ az alapmegoldás). Ha $d$ négyzetszám, akkor a megoldás triviális: $(x,y)=(\pm 1,0)$, és nincs több.

A Pell-egyenlet megoldása egyenértékű azzal, hogy megtaláljuk az egységeket a $\mathbb {Q} ({\sqrt {d}})$ kvadratikus számtest algebrai egészeinek gyűrűjében. Ez a test a racionális számokból kapható $d$ négyzetgyökével bővítve.

Pitagoraszi számhármasok

A pitagoraszi számhármasok az $x^{2}+y^{2}=z^{2}$ diofantoszi egyenlet megoldásai. A megoldások általános alakja $x=t2uv$, $y=t(u^{2}-v^{2})$, $z=t(u^{2}+v^{2})$.

A pitagoraszi számhármasok általánosításaként Fermat azt állította 1637-ben, hogy ha 2 helyett nagyobb egész kitevős hatványt veszünk, akkor az egyenletnek nem lesznek pozitív egészekből álló megoldásai. Ennek igazolása több, mint 350 évbe telt, és nagy hatással volt az algebra fejlődésére a test- és gyűrűelmélet terén. 1994-ben Andrew Wiles bizonyított egy tételt, amiről már tudták korábban, hogy következik belőle a nagy Fermat-tétel.

Két négyzetszám összege

A kétnégyzetszám-tétel szerint, ha n természetes szám, akkor az $x^{2}+y^{2}=n$ diofantoszi egyenlet pontosan akkor oldható meg, ha n prímhatvány-felbontásában minden 4k-1 alakú prím páros kitevővel szerepel. A megoldások száma is pontosan meghatározható.

Gyökös diofantoszi egyenletek

A gyökös diofantoszi egyenletek alakja

$a_{1}{\sqrt[{p_{1}}]{q_{1}}}\pm a_{2}{\sqrt[{p_{2}}]{q_{2}}}...\pm a_{s}{\sqrt[{p_{s}}]{q_{s}}}=0$

ahol

$a_{1},a_{2},...,a_{s},q_{1},q_{2},...,q_{s},p_{1},p_{2},...,p_{s},s$

mind egészek.

Ezekre az egyenletekre a lineáris egyenletekhez hasonlóan van általános algoritmus.

Exponenciális diofantoszi egyenletek

Ha egy diofantoszi egyenletben további ismeretlen(ek) vannak, amely(ek) kitevőként szerepel(nek), akkor ez exponenciális diofantoszi egyenlet. Egy példa ilyenre a Ramanujan-Nagell egyenlet, $2^{n}-7=x^{2}$. Ilyen egyenletekre nem létezik általános elmélet. Speciális esetekre, mint a Catalan-sejtés, van megoldás; azonban a többségüket ad hoc módon oldják meg, akár a Størmer-módszerrel, vagy próbálgatással.

Elemzésük

A diofantoszi egyenletek megoldásainak keresésében segítenek ezek a kérdések:

• Megoldható az adott egyenlet?
• Vannak-e még más megoldások is az ismerteken kívül?
• Véges, vagy végtelen megoldás van-e?
• Tényleg létezik-e minden, elméletben létező megoldás?
• Kiszámítható-e az összes megoldás?

Ezek sokszor évszázadokig nyitott kérdések voltak. Fermat sejtését csak a 20. század végén tudta bizonyítani Andrew Wiles az algebrai geometria eszközeivel. Az 1922-ben felvetett Mordell-sejtést, ami szerint az 1-nél nagyobb nemszámú görbéknek csak véges sok racionális pontja lehet, 1983-ban látta be Gerd Faltings. Ez a Faltings-tétel.

Hilbert tizedik problémája

A diofantoszi egyenletek megoldhatósága a David Hilbert által 1900-ban kitűzött problémák közé tartozott. Ez volt a nevezetes tizedik probléma. 1970-ben Jurij Vlagyimirovics Matijasevics oldotta meg azzal, hogy a probléma eldönthetetlen, vagyis nincs közös algoritmus az összes diofantoszi egyenletre. Az eredményhez felhasználta Martin Davis, Hilary Putnam és Julia Robinson munkáit. Davis (1953) átfogalmazta a problémát diofantoszi halmazokra, továbbá ő állította fel azt a sejtést is, hogy ezek identikusak a rekurzívan felsorolható halmazokkal. Ennek megoldásával Hilbert tizedik problémája is megoldódott.

Az $M$ halmaz diofantikus, ha pozitív egészek $n$-eseiből áll úgy, hogy ha $x=(x_{1},\dotsc ,x_{n})$, akkor

$P(x_{1},\dotsc ,x_{n},a_{1},\dotsc ,a_{m})=0$

teljesül az $a_{1},\dotsc ,a_{m}$ pozitív egész paraméterekkel:

$M=\{x\mid \exists a_{1},\dotsc ,a_{m}\colon P(x,a_{1},\dotsc ,a_{m})=0\}$

Megmutatható, hogy a pozitív egész feltétel nem korlátozza az általánosságot.

Például az összetett számok diofantoszi halmazt alkotnak. Ehhez egy megfelelő polinom $x-(a+1)\,(b+1)$, az $a,b$ paraméterekkel. Hasonlóan, a pozitív páros számok halmaza is diofantoszi, a $x-2\cdot a$ polinommal. A definíció alkalmazható $P_{i}=0$ polinomhalmazokra, mivel ezek visszavezethető egyetlen polinomra, ami $\sum _{i}P_{i}^{2}=0$. Ennek megfelelően az $y=f(x_{1},\dotsc ,x_{n})$ diofantoszi függvények megadhatók az $M=\{y,x_{1},\dotsc ,x_{n}\}$ diofantoszi halmazzal. Putnam 1960-ban belátta, hogy a természetes számok minden diofantoszi halmaza előáll egész együtthatós polinom megoldáshalmazaként a természetes számokon.

Néha nehéz megmutatni, hogy egy halmaz diofantoszi. Ilyen például a prímszámok halmaza, szemben az összetett számokkal, 2 hatványaival és az $n!$ faktoriális számokkal. Julia Robinson ezután nem tudta belátni, hogy $\{(a,b,c)\mid a=b^{c}\}$ diofantoszi. Viszont megmutatta, hogy ez következik abból, hogy van diofantoszi halmaz, ami exponenciálisan nő. Ez azt jelenti, hogy a definiáló egyenletben a változók egyike megjelenik a kitevőben. Pontosabban:

Létezik egy $D$ diofantoszi halmaz úgy, hogy:

• Ha $u,v\in D$, akkor $v\leq u^{u}$.
• Tetszőleges pozitív $k$ esetén van $u,v\in D$ úgy, hogy $v>u^{k}$.

A diofantoszi halmazok definíció szerint rekurzívan felsorolhatók, azaz van algoritmus, ami pontosan ezekre az elemekre áll le. Davis és Putnam közreműködésével Robinson megmutatta, hogy a rekurzív felsorolható halmazok pontosan az exponenciális diofantoszi halmazok; továbbá, hogy az:

„Minden rekurzív felsorolható halmaz diofantoszi”

állítás következne az exponenciálisan növekvő diofantoszi halmazok létéből. 1970-ben Matijasevics ezt bizonyította a Fibonacci-sorozat segítségével. Példája tíz polinomiális egyenletet tartalmazott 15 ismeretlennel.

Mivel a kiszámíthatósági tétel szerint vannak rekurzív felsorolható halmazok (Cantor-féle átlós eljárással), melyek nem dönthetők el, következik, hogy Hilbert tizedik problémája sem oldható meg.

Mivel a prímszámok rekurzívan felsorolhatók, következik, hogy van egy diofantoszi egyenlet, aminek ezek, és csak ezek a megoldásai.

Thoralf Skolem óta ismert, hogy a diofantoszi egyenletek visszavezethetők legfeljebb negyedfokú egyenletekre. Matijasevics azt is megmutatta, hogy az egyenleteknek vannak olyan reprezentációi, melyek legfeljebb kilenc ismeretlent tartalmaznak.

Gödel nemteljességi tétele szerint az aritmetika bármely axiómarendszerében vannak megoldhatatlan diofantoszi egyenletek, melyek megoldhatatlansága nem bizonyítható.

A diofantoszi egyenletek elmélete

Az ismertebb általános módszerek a végtelen leszállás és a Hasse-elv. Ezek inkább a megoldhatatlanság bizonyítására, mint a megoldások keresésére valók. A végtelen leszállás alkalmazásakor egy feltételezett legkisebb megoldásból még kisebb megoldásokat gyártanak, ezzel kimutatják, hogy az egyenlet nem oldható meg a pozitív egészek halmazán. A Hasse-elv a kínai maradéktétel felhasználásával mutatja ki az egyenlet megoldhatatlanságát.

Axel Thue 1908-ban megmutatta, hogy az $f(x,y)=c$ alakú egyenletek esetén, ha $f(x,y)$ kétváltozós, irreducibilis, és legalább harmadfokú, és $c$ egész, csak véges számú megoldás lehetséges. Azóta ezeket az egyenleteket Thue-egyenleteknek nevezik. A bizonyítás nem konstruktív; becsléseken alapul, melyek az algebrai számokat racionálisokkal közelítik. Másodfokra a tétel nem teljesül, ezt a Pell-egyenletek mutatják.

Alan Baker 1968-ban effektív becslést adott a Thue-egyenletek megoldászámaira az algebrai számok logaritmusának lineáris formáival. 1989-ban De Weger és Tzanakis hatékony megoldási módszert adott rájuk.

1929-ben Carl Ludwig Siegel bizonyította, hogy azok az egyenletek, melyek $g>0$ topologikus nemű algebrai görbéket írnak le, véges megoldásszámúak. A bizonyítás nem konstruktív; diofantoszi approximáción alapul. Az egész számok helyett racionálisokat tekintve a Mordell-sejtéshez jutunk.

1938-ban Thoralf Skolem megoldási módszert talált az $P(x_{1},\dotsc ,x_{n})=0$ alakú diofantoszi egyenletekre, ahol $P$ irreducibilis polinom, ami a racionális számok egy testbővítésében $m>n$ tényezőre bomlik, és még egy további feltételt is teljesít. Ide tartoznak a Thue-egyenletek is, mégpedig ha $f(x,1)=0$ nem minden gyöke valós. Módszere a p-adikus analízis volt ((lokális módszer).

További információk

• Alice és Bob - 20. rész: Alice, Bob, Euler és Fermat
• Alice és Bob - 21. rész: Alice és Bob titkosít

Források

• Matiyasevich, Yuri Vladimirovich. Hilbert's Tenth Problem. Kiadó: Foundations of Computing, MIT Press. Cambridge, Massachusetts and London, England, 1993. ISBN 0-262-13295-8.
• Martin Davis, Reuben Hersh: Hilbert’s tenth problem. Scientific American, Band 229, November 1973.
• Martin Davis: Hilbert’s tenth problem is unsolvable. American Mathematical Monthly, Band 80, 1973, S. 233–269.
• Martin Davis, Yuri Matiyasevich, Julia Robinson: Hilbert’s tenth problem, Diophantine equations, positive aspects of a negative solution. In: F. Browder: Mathematical developments arising from Hilbert’s problems. AMS, Teil 2, 1976, S. 323–378.
• Alexandra Shlapentokh: Hilbert’s tenth problem: Diophantine classes and extensions to global fields. Cambridge UP, 2006.
• Mordell, L. J.. Diophantine Equations. Academic Press (1969). ISBN 0-12-506250-8 
• Schmidt, Wolfgang M.. Diophantine Approximations and Diophantine Equations, Lecture Notes in Mathematics. Springer-Verlag (2000) 
• Exponential Diophantine Equations, Cambridge Tracts in Mathematics. Cambridge University Press (1986). ISBN 0-521-26826-5 
• Smart, N. P.. The Algorithmic Resolution of Diophantine Equations, London Mathematical Society Student Texts. Cambridge University Press (1998). ISBN 0-521-64156-X 
• Stillwell, John. Mathematics and its History, Second Edition, Springer Science + Business Media Inc. (2004). ISBN 0387953361 
• Tóth Árpád: Diofantosz és a diofantikus egyenletek (magyar nyelven). Érintő (Bolyai János Matematikai Társulat), 2017. június 1.
• G. H. Hardy, E. M. Wright: An Introduction to the Theory of Numbers. 5th ed., Clarendon Press, Oxford, England 1979.

Fordítás

• Ez a szócikk részben vagy egészben a Diophantine equation című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
• Ez a szócikk részben vagy egészben a Diophantische Gleichung című német Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.