Ugrás a tartalomhoz

Számelmélet

dr. Freud Róbert kandidátus, dr. Gyarmati Edit PhD. (2014)

Nemzedékek Tudása Tankönyvkiadó Zrt.

7. fejezet - DIOFANTIKUS EGYENLETEK

7. fejezet - DIOFANTIKUS EGYENLETEK

Diofantikus (vagy diofantoszi) 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. Diophantosz görög matematikus az i.sz. III. században élt Alexandriában, és sokféle ilyen egyenlettel foglalkozott. (Akkoriban teljesen természetes volt, hogy egész, illetve racionális megoldásokat kerestek, hiszen az irracionális számok annak ellenére sem nyertek igazán polgárjogot, hogy a görögök bebizonyították ezek létezését.) A diofantikus egyenletek története egyébként még ennél is sokkal régebbre nyúlik vissza; közel négyezer éves kőtáblák tanúsága szerint már a babiloniaiak is ismerték az ún. pitagoraszi számhármasok előállítási módját.

A diofantikus egyenletek megoldása igen változatos módszereket igényel, univerzális megoldási módszer nem létezik (sőt, mint az 5.1 pontban már említettük, annak az egyszerűbb kérdésnek a megválaszolására sem létezik általános algoritmus, hogy egy tetszőlegesen adott diofantikus egyenletnek egyáltalán van-e megoldása vagy sem). Egy-egy konkrét egyenlet esetén is gyakran igen nehéz eldönteni a megoldhatóságot, a megoldásszámról, illetve az összes megoldás meghatározásáról nem is beszélve. Ez a témakör is bővelkedik híres megoldatlan problémákban.

A már az 1. fejezetben is szerepelt lineáris diofantikus egyenletek részletes tárgyalása után a pitagoraszi számhármasokkal foglalkozunk, majd néhány jól használható elemi módszert mutatunk be diofantikus egyenletek megoldására. A továbbiakban olyan diofantikus problémák következnek, amelyek kezeléséhez látszólag egészen más jellegű matematikai eszközöket érdemes bevetni: a két négyzetszám összegéből történő előállíthatósághoz a Gauss-egészeket, a Fermat-sejtés köbszámokra vonatkozó speciális eseténél az Euler-egészeket és a Pell-egyenletnél a diofantikus approximációt. Ezeknek a „segédeszközöknek” a kialakulását és önálló elméletté terebélyesedését éppen a diofantikus egyenleteknél való alkalmazhatóságuk segítette elő. Az ezekből kifejlődött területeknek a részletes bemutatására a 811. fejezetekben kerül majd sor. Végül, a jelen fejezet utolsó pontjában a fentiektől mind a probléma jellegében, mind pedig a megoldási módszerekben alapvetően eltérő partíciós kérdéseket tárgyalunk.

7.1 Lineáris diofantikus egyenlet

Először az ax+by=c kétismeretlenes lineáris diofantikus egyenlettel foglalkozunk. Itt a,b,c rögzített egész számok, ahol az a=b=0 esetet eleve kizárjuk, és megoldáson x,y egész számokból álló számpárt értünk.

A megoldhatóság szükséges és elégséges feltételét az T 1.3.6 Tételben, az egyenletnek a lineáris kongruenciákkal való kapcsolatát a T 2.5.3 Tétel bizonyítása során tárgyaltuk. Az T 1.3.6 Tétel bizonyításából azt is leolvastuk, hogy az egyenlet egy megoldását az euklideszi algoritmus segítségével kaphatjuk meg. Ebből az T 5.7.1 Tétel szerint következett, hogy az egyenlet egy megoldását nagy számok esetén is „gyorsan” meg tudjuk határozni; ezt a tényt az RSA-sémában (T 5.8.1 Tétel) is felhasználtuk.

Most megadjuk a megoldásszámot és az összes megoldás leírását. A teljesség kedvéért a tétel állításában a megoldhatóságról és a megoldási módszerről korábban bizonyított állításokat is összefoglaljuk.

7.1.1 Tétel . T 7.1.1

Legyenek a, b és c rögzített egész számok, ahol a és b közül legalább az egyik nem nulla, és tekintsük az ax+by=c diofantikus egyenletet.

(i) Az egyenlet akkor és csak akkor oldható meg, ha (a,b)c.

(ii) Megoldhatóság esetén végtelen sok megoldás van. Ha x0, y0 (egy rögzített) megoldás, akkor az összes x,y megoldást az alábbi képlet szolgáltatja:

(iii) Az egyenlet egy megoldását az euklideszi algoritmus segítségével kaphatjuk meg.

Bizonyítás: Mint már említettük, (i)-et és (iii)-at az T 1.3.6 Tételben igazoltuk.

Rátérve (ii)-re, először azt mutatjuk meg, hogy az (1)-ben megadott x, y számok valóban az egyenlet egy megoldását szolgáltatják. Mivel x0, y0 megoldás, azaz ax0+by0=c, így

A megfordításhoz tegyük fel, hogy x, y egy tetszőleges megoldás, és belátjuk, hogy x és y a kívánt alakú.

A feltétel szerint

A két egyenlőséget egymásból kivonva

adódik. Rendezés és (a,b)-vel történő osztás után azt kapjuk, hogy

Mivel

ezért (2)-ből

azaz alkalmas t egésszel

következik. A (3)-at (2)-be visszahelyettesítve kapjuk, hogy

Ezzel megmutattuk, hogy x és y valóban az (1)-ben előírt alakú. ∎

A diofantikus egyenletek tényleges megoldásakor az euklideszi algoritmusnak egy olyan variánsát érdemes alkalmazni, amelynek segítségével (nemcsak egy megoldáshoz jutunk el, hanem) egyszerre tudjuk az összes megoldást (paraméteres alakban) előállítani. Ezt az eljárást egy konkrét példán keresztül mutatjuk be.

Példa: Oldjuk meg a 43x+25y=98 diofantikus egyenletet.

Fejezzük ki az egyenletből azt az ismeretlent, amelynek az együtthatója kisebb abszolút értékű, és a törtből válasszunk le olyan részeket, amelyek biztosan egész értékűek:

Ekkor az (A1) jobb oldalán álló (7x2)25 tört is egész szám kell hogy legyen, jelöljük ezt u-val. Innen 7x2=25u. Ez egy hasonló diofantikus egyenlet, mint az eredeti, csak itt az x együtthatójának kisebb az abszolút értéke, mint az eredeti egyenletben y együtthatójáé volt.

Ismételjük meg most az előző eljárást a 7x2=25u egyenletre, fejezzük ki x-et, és válasszuk le a garantáltan egész értékű kifejezéseket:

Az (A2) jobb oldalán szereplő (23u)7 tört egész szám kell hogy legyen, jelöljük v-vel, ekkor 23u=7v. Hasonlóan tovább haladva kapjuk, hogy

A (2v)3 egész számot w-vel jelölve 2v=3w, azaz

Mivel (A4)-ben már nem szerepel tört, most elindulunk „visszafelé”, és rendre (A3), (A2) és (A1) felhasználásával u, x és y értékét kifejezzük a w paraméter segítségével:

A módszerből világos, hogy a (B2)–(B1) képletpár szolgáltatja a 43x+25y=98 diofantikus egyenlet összes megoldását, ahol a w paraméter tetszőleges egész szám. Ugyanis egyrészt, ha egy x,y egész számpár megoldás, akkor az (A1)–(A3) lépéseken végighaladva eljutunk w-hez, majd ennek segítségével x-re és y-ra a (B2)–(B1) képletpár adódik, másrészt tetszőleges egész w-re az így képzett x és y számok egészek lesznek és kielégítik az egyenletet.

Megjegyzések: 1. Nézzük az eljárás lépései során keletkező együtthatópárokat:

Ezek rendre úgy keletkeztek, hogy a 43-at a 25-tel osztva 7 volt a (legkisebb abszolút értékű) maradék, a 25-öt a 7-tel osztva 3 stb. Ez azt jelenti, hogy itt valóban az euklideszi algoritmus egy variánsáról van szó, és ebből az is következik, hogy a diofantikus egyenlet megoldásait ily módon „gyorsan” meg tudjuk határozni.

2. A fenti módszer lényege, hogy az ismeretlenek együtthatóinak az abszolút értékeit megfelelően csökkentve végül a törteket teljesen kiküszöböljük. Ebből a szempontból mellékes, hogy a „konstans” tag abszolút értékét csökkentjük-e vagy sem. Akár végrehajtunk ilyen átalakítást (mint a fenti példában), akár nem, ez az eljárás lépésszámát nem befolyásolja, legfeljebb „kényelmesebb”, ha kisebb számokkal dolgozunk.

3. Nem szükséges a megoldhatóság feltételét előre külön ellenőrizni, az eljárásból is automatikusan kiderül, ha nincs megoldás: ekkor egy olyan törthöz jutunk, amelyben már nem szerepel ismeretlen, azonban a tört értéke nem egész szám.

4. A (B2)–(B1) képlet összhangban van a T 7.1.1 Tételnek az összes megoldást leíró (1) előállításával: most x0=14, y0=28, és a t szerepét w játssza. Ez az észrevétel esetleges számolási hibák kiszűrésére is alkalmas: a végeredményként kapott képletet mindig érdemes ilyen szempontból (1)-gyel összevetni.

Kettőnél több ismeretlenes lineáris diofantikus egyenletekre is a kétismeretlenes esethez hasonló állítások érvényesek. Ezeket az alábbi tételben foglaljuk össze, a bizonyításokat a 7.1.8 feladatban tűztük ki.

7.1.2 Tétel . T 7.1.2

Legyen k2, a1,,ak nem csupa 0 egész számok, c tetszőleges egész, és tekintsük az

diofantikus egyenletet (azaz megoldáson egy egészekből álló x1,,xk szám-k-ast értünk).

(i) Az egyenlet akkor és csak akkor oldható meg, ha (a1,,ak)c.

(ii) Megoldhatóság esetén végtelen sok megoldás van. Az összes megoldás k1 egész paraméter segítségével adható meg. A megoldások meghatározása a két ismeretlen esetén látott módszer értelemszerű általánosításával történik.

Feladatok

7.1.1  Bolondóciában csak 47 és 79 forintos bankjegyek léteznek. Hányféleképpen lehet pontosan 10000 forintot kifizetni?

7.1.2  Egy szigeten 7- és 11-fejű sárkányok élnek. Hány sárkány él a szigeten, ha összesen 118 fejük van?

7.1.3  Egy üzletben háromféle csokoládé kapható, 70, 130, illetve 150 forintos egységárban. Hányféleképpen lehet (pontosan) 5000 forintért (pontosan) 50 darab csokoládét vásárolni?

7.1.4  (M) Valamikor a huszadik században a 99 évnél nem idősebb és különböző korú Alexander és Bernát mindketten éppen annyi idősek, mint amennyi a születési évszámukban a számjegyek összege. Hány év közöttük a korkülönbség?

7.1.5  Mutassuk meg, hogy a T 7.1.1 Tétel (ii) állítása a T 2.5.4 Tételből (illetve az arra adott bizonyításból) is következik.

7.1.6  A síkon hány rácspontot tartalmazhat egy

(a) racionális;

(b) irracionális

meredekségű egyenes?

7.1.7  Adjuk meg a 6x+10y+15z=7 diofantikus egyenlet összes megoldását.

7.1.8  Igazoljuk a T 7.1.2 Tétel állításait.

7.1.9  Bizonyítsuk be, hogy az a1x1++akxk=c diofantikus egyenletnek akkor és csak akkor létezik megoldása, ha minden m pozitív egész esetén megoldható az a1x1++akxkc(modm) kongruencia.

7.1.10  (*) Mely a1,,ak egészek esetén igaz, hogy az a1x1++akxk=c diofantikus egyenletnek minden elég nagy c esetén létezik pozitív egészekben megoldása?

7.1.11  (*) Legyenek a és b rögzített, relatív prím, 1-nél nagyobb egészek. Nevezzünk (házi használatra) egy c pozitív egészt (a-ból és b-ből) „összerakhatónak”, ha c felírható c=ax+by alakban, ahol x és ynemnegatív egészek.

(a) Mutassuk meg, hogy ha c>abab, akkor c összerakható, azonban c=abab nem összerakható.

(b) Hány nem összerakható pozitív egész létezik?

Megjegyzés: A feladat (a) részét több változóra a következőképpen általánosíthatjuk. Legyenek a1,,ak relatív prím, 1-nél nagyobb egészek. Keressük azt a maximális F=F(a1,,ak) egészt, amelyre az a1x1++akxk=F diofantikus egyenlet nem oldható meg nemnegatív egészekben. Ezt a kérdést Frobenius-problémának nevezik. A k>2 eset vizsgálata igen nehéz.

7.1.12  (*) (a) Mutassuk meg, hogy minden elég nagy n esetén létezik n darab olyan (nem feltétlenül egybevágó) kocka, amelyekből (mindegyiket egyszer felhasználva) összeállítható egy (nagyobb) kocka.

(b) Igazoljuk ugyanezt minden n48-ra.

Megjegyzés: Megoldatlan probléma, hogy az állítás igaz-e n=47-tel is.