A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre. 1. Bevezetés Tekintsük az számtani sorozatot, ahol . Ha és nem relatív prímek, akkor osztója a sorozat mindegyik tagjának, és így a sorozatban legföljebb egy prímszám szerepelhet (a kényelem kedvéért a prímszámokat pozitívnak tekintjük).
1.1. tétel [Dirichlet, 1837]. Ha és , relatív prím egész számok, akkor az számtani sorozatban végtelen sok prímszám található.
A tételnek csak olyan bizonyítása ismeretes, amely komplex analízist használ. Egy ilyen, középiskolások számára is érthetően leírt bizonyítás olvasható Szalay Mihály [6] középiskolás tagozatos tankönyvének függelékében. Ugyanakkor a tételnek vannak olyan speciális esetei, melyeket elemi úton is be tudunk bizonyítani. Ebben a kétrészes cikkben így igazoljuk a tételnek az , illetve az alakú számok sorozatára vonatkozó állítását. Az betű végig ezt a pozitív egészet jelöli majd. Az , , , , , , , , , és betűk is végig egész számokat jelölnek, melyek közül prímszám. Feltételezzük, hogy az Olvasó ismeri a számelmélet alapvető fogalmait és tételeit, valamint a komplex számok és a polinomok legfontosabb tulajdonságait. Ezeknek a [2], illetve a [3] tankönyvek első fejezeteiben nézhet utána. Mindkét könyv tartalmazza az eset bizonyítását is ([2], 5.3.4. tétel, illetve [3], 5.8.15. feladat, melynek megoldása az internetről letölthető). Az alább következő gondolatmenet kicsit elemibb. Ennek ismertetésével ér véget a cikk első része. Bauer Mihály 1900 táján talált elemi bizonyítást a tétel esetére. Erdős Pál és Surányi János [1] könyvükben megemlítik a két alapötletet (203. oldal). Cikkünk második részében, a már bevezetett fogalmakra alapozva, egy ehhez hasonló gondolatmenetet mutatunk be. Szerepel egy bizonyítás Schur [5] cikkében is. Felmerül a kérdés, hogy milyen számtani sorozatok esetében létezik még hasonló elemi bizonyítás. Erre Murty [4] eredménye ad választ: az számok sorozata akkor és csak akkor ilyen, ha . Érdekesség, hogy ennek igazolásához olyan mély tételt alkalmaz (Csebotarjov sűrűségi tételét 1922-ből), amely Dirichlet tételének általánosítása. Murty bizonyítása az algebrai számelmélet eszköztárát használja. Ebből az Olvasó kap majd kis ízelítőt, mert a Gauss-egészek fogalmát mi is bevezetjük a cikk második részében. Ugyanakkor cikkünk algebrai szempontból is elemi, a számelméleti elemrend és a körosztási polinomok fogalmát felhasználjuk majd, de testekről már nem beszélünk. A test fogalmának birtokában néhány számolás egyszerűsödött volna, de nem lényegesen. Az ilyen lehetőségre mindig utalunk a szövegben, biztatva az Olvasót, hogy az egyszerűsítést végezze el. A bizonyítást feladatsorozat formájában ismertetjük. A feladatok nem nehezek, érdemes velük önállóan próbálkozni. Mindegyik feladat után közvetlenül szerepel a megoldása.
2. Két elemi bizonyítás 2.1. feladat. Igazoljuk, hogy végtelen sok alakú prímszám van.
Megoldás. Tegyük föl indirekt, hogy csak véges sok ilyen prímszám van, legyenek ezek . Tekintsük az számot. Ez -nél nagyobb, ezért prímszámok szorzata. E prímtényezők mindegyike -től és mindegyik -től különbözik, és így -gyel osztva már csak maradékot adhat. Ekkor azonban a szorzatuk is -et ad maradékul, ami ellentmondás, mert . Megjegyezzük, hogy Dirichlet tételének analitikus bizonyítása már az egyszerű esetekben is többet ad, mint az elemi bizonyítások, mert segítségével meg lehet becsülni, hogy az adott számtani sorozatban ,,mennyi'' prímszám van. Például ha , akkor csak négy sorozat jön szóba: , , , . Ezekben egymáshoz képest ,,ugyanannyi'' prímszám van, a következő értelemben. Jelölje a alakú, -nél nem nagyobb prímek számát. Ekkor mindegyikére (a logaritmus természetes alapú). Vagyis a négy sorozat mindegyikébe a prímek körülbelül egynegyede esik. Ez az eredmény erősítése a Nagy Prímszámtételnek (mely szerint a prímek száma -ig körülbelül , lásd [2], 5.4.1. tétel). Ugyanakkor a 2.1. feladat megoldása nagyon ,,kevés'' alakú prímet szolgáltat. A kapott ,,új'' prímről ugyanis nem tudunk mást, mint hogy legföljebb . Ez a sorozat pedig nagyon gyorsan növekszik: a -ból kiindulva a kapott számok 11, 131, 17 291, 298 995 971. Az Olvasónak érdemes meggondolnia, hogy az eljárás -ig csak körülbelül darab alakú prímet biztosít. Ugyanakkor az -nél nem nagyobb alakú prímek számának nagyságrendje .
Elemien bizonyítható az is, hogy végtelen sok alakú prím van. Ehhez már egy segédállításra van szükségünk.
2.2. feladat. Igazoljuk, hogy ha a prímszám alakú, akkor -ből és következik. Speciálisan az alakú számok mindegyik páratlan prímosztója alakú.
Megoldás. Ha és valamelyike osztható -vel, akkor miatt a másik is. Ha egyik sem, akkor az kongruenciát -edik hatványra emelve az Euler‐Fermat-tétel miatt adódik. Mivel , ezért . Így , ami ellentmond annak, hogy páratlan. 2.3. feladat. Igazoljuk, hogy végtelen sok alakú prímszám van.
Megoldás. Tegyük föl indirekt, hogy csak véges sok ilyen prímszám van, legyenek ezek . Tekintsük az számot. Ez -nél nagyobb, ezért prímszámok szorzata. E tényezők mindegyike -től és mindegyik -től különbözik, és a 2.2. feladat miatt -gyel osztva maradékot ad. Ez az ellentmondás bizonyítja az állítást.
3. Körosztási polinomok A továbblépéshez érdemes másik megoldást adni a 2.2. feladat második állítására. Ez bonyolultabb lesz, mert felhasználja a számelméleti elemrend fogalmát, de lehetővé teszi az általánosítást. Emlékeztetőül összefoglaljuk a renddel kapcsolatos tudnivalókat (lásd [2], 3.2. szakasz).
3.1. feladat. Tegyük föl, hogy . Mutassuk meg, hogy van olyan pozitív egész, melyre .
Megoldás. Mivel véges sok modulo maradék van, léteznek olyan egészek, hogy . A modulushoz relatív prím -vel egyszerűsítve adódik. Ha a legkisebb olyan tulajdonságú pozitív szám, ami az előző feladatban szerepel, akkor hatványai egy hosszúságú periódus szerint ismétlődnek, és így különböző hatványainak száma . Ezt az számot rendjének nevezzük modulo , jele . A periodicitás miatt . Az Euler‐Fermat-tételből ezért következik, hogy .
3.2. gyakorlat. Számítsuk ki és rendjét modulo .
Megoldás. Mivel hatványai modulo rendre , , , ezért . Hasonlóan, első három hatványa modulo rendre , és . Tovább nem érdemes számolni a következő okból. Az eddigiek szerint rendje nagyobb, mint 3. De ez a rend osztója -nak, ezért csakis 6 lehet.
3.3. feladat. Legyen prímosztója az számnak. Igazoljuk, hogy vagy .
Megoldás. Mivel , ezért , azaz . Ha ez a rend nem , akkor vagy . Mindkét esetben . A feltétel szerint , ezért , azaz . Innen persze páratlan esetén , azaz megkaptuk a 2.2. feladat második állítását. Ez a megoldás azt sugallja, hogy ha a sorozat helyett az sorozatban keresünk prímeket, akkor helyett az kifejezés alkalmas tényezőjével célszerű dolgoznunk. Az polinom szorzatra bontását körosztási polinomok segítségével végezhetjük el. Az gyökei az komplex számok, ahol , vagyis az -edik komplex egységgyökök (lásd [3], 1.5. szakasz). Mivel egész együtthatós polinomokat szeretnénk kapni, ezért gyöktényezői közül bizonyosakat összevonunk. Legyen
| | E polinom gyökei a primitív -edik egységgyökök, maga pedig az -edik körosztási polinom. Az alábbi tétel kívánt szorzatra bontását szolgáltatja.
3.4. tétel. Ha , akkor a következők teljesülnek.
| Érvényes az azonosság. |
| egész együtthatós. |
Az előző tételt az Olvasó könnyen igazolhatja, vagy megtalálhatja a bizonyítást a [3] könyv 3.9. szakaszában. A (2) pont képletéből a körosztási polinomokat kiszámíthatjuk rekurzívan, egységgyökökre való hivatkozás nélkül is.
3.5. gyakorlat. Számítsuk ki a polinomokat, amikor .
Megoldás. Mivel a nevező esetén üres szorzat, (vagy a definícióból közvetlenül láthatjuk, hogy az az egyetlen primitív ,,-edik'' egységgyök). A képletből és . Mivel , ezért . Hasonlóan összevonva a nevezőben | | (hiszen ). A összefüggés alapján a 3.3. feladat állítása úgy is fogalmazható, hogy ha prímosztója a számnak, akkor vagy . Ezt általánosítja a következő tétel, amit az utána következő három feladatban látunk be.
3.6. tétel. Legyen prímosztója a számnak. Ekkor vagy .
Mivel , ezért és relatív prímek, tehát az rend értelmes.
3.7. feladat. Legyenek , , egész együtthatós polinomok, és tegyük föl, hogy és konstans tagja is osztható -vel. Ekkor az szorzatpolinomban a konstans tag is, az -es tag együtthatója is osztható -vel.
Megoldás. Legyen Ekkor a szorzatpolinomban a konstans tag , az -es tag együtthatója pedig . Megjegyezzük, hogy ha hajlandóak vagyunk polinomok együtthatóival modulo számolni, akkor ez a megoldás egyszerűbben is megfogalmazható. A modulo vett maradékok egy elemű testet alkotnak. Vegyük mindhárom polinom együtthatóit modulo , ekkor fölötti polinomokat kapunk. A feltétel szerint és is osztható -szel -ben, tehát osztható -tel. Ennek a gondolatmenetnek a precíz megalapozása a [3] könyvben olvasható (1.1. szakasz, illetve 2.3.8. gyakorlat).
3.8. feladat. Tegyük föl, hogy prímosztója a számnak, de . Igazoljuk, hogy ekkor van olyan , hogy és .
Megoldás. Mivel , ezért , és így . Legyen . Ekkor , azaz . Mivel prím, osztója valamelyik tényezőnek. 3.9. feladat. Igazoljuk a tételt.
Megoldás. Tegyük föl, hogy prímosztója a számnak, de . Az előző feladat miatt van olyan , hogy és . Legyen , , továbbá legyen mindazon polinomok szorzata, ahol de . Ha a 3.4. tétel állítását helyett -re alkalmazzuk, akkor adódik. Helyettesítsünk -t, ekkor láthatjuk, hogy és konstans tagja is osztható -vel. Ezért a 3.7. feladat miatt az polinom -es tagjának együtthatója osztható -vel. A binomiális tétel szerint ez . Mivel miatt relatív prím -hoz, ezért . Az Olvasó a 3.6. tételt felhasználva most már könnyen általánosíthatja a 2.3. feladat megoldását, és beláthatja, hogy végtelen sok alakú prímszám van. Mi ezt a lépést azért bontjuk három feladatra, mert így könnyebb lesz követni a cikk második részében az eset gondolatmenetét.
3.10. feladat. Mutassuk meg, hogy minden pozitív egészhez van olyan egész, hogy osztható egy -nál nagyobb prímszámmal.
Megoldás. Legyen , ahol az pozitív egész értékét később választjuk meg. Mivel ha , ezért -et elég nagyra választva , és így -nak van egy prímosztója. Tudjuk, hogy , ezért relatív prím -hoz. Így .
3.11. feladat. Igazoljuk, hogy ha a prím nagyobb -nél, és olyan egész szám, amelyre , akkor a prím alakú.
Megoldás. A 3.6. tételből következik, hogy , hiszen miatt nem teljesül. Ezért .
3.12. feladat. Bizonyítsuk be, hogy minden esetén végtelen sok alakú prímszám van.
Megoldás. Tegyük föl indirekt, hogy csak véges sok ilyen prímszám van, legyenek ezek . Válasszuk a számot úgy, hogy ezek mindegyikénél, továbbá -nél is nagyobb legyen. A 3.10. feladat miatt van olyan egész, továbbá egy -nál nagyobb prím, melyre . Az előző feladat szerint a prím alakú, ami ellentmondás.
Ajánlott irodalom
[1] | Erdős Pál, Surányi János: Válogatott fejezetek a számelméletből, Polygon Kiadó (1996). |
[2] | Freud Róbert, Gyarmati Edit: Számelmélet, Nemzeti Tankönyvkiadó (2006). |
[3] | Kiss Emil: Bevezetés az algebrába, TypoTeX Kiadó (2007). |
[4] | M. R. Murty: Primes in certain arithmetic progressions, J. Madras Univ. (1988), 161‐169. |
[5] | I. Schur: Über die existenz unendlich vieler primzahlen in einiger speziellen arithmetischen progressionen, Sitzungber. Berliner Math. Ges., 11 (1912), 40─50. |
[6] | Szalay Mihály: Számelmélet, TypoTeX Kiadó (1998). |
|
|