Cím: Gauss-egészek és Dirichlet tétele I.
Szerző(k):  Keith Kearnes ,  Kiss Emil ,  Szendrei Ágnes 
Füzet: 2010/március, 136 - 141. oldal  PDF file
Témakör(ök): Szakmai cikkek

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 ak+b számtani sorozatot, ahol a>0. Ha a és b nem relatív prímek, akkor (a,b)>1 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 a>0 és a, b relatív prím egész számok, akkor az ak+b (k=1,2,...) 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 nk+1, illetve az nk-1 alakú számok sorozatára vonatkozó állítását. Az n betű végig ezt a pozitív egészet jelöli majd. Az a, b, c, d, i, j, k, , m, u és p betűk is végig egész számokat jelölnek, melyek közül p 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 nk+1 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 nk-1 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 ak+b számok sorozata akkor és csak akkor ilyen, ha b21(a). É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 4k-1 alakú prímszám van.
 
Megoldás. Tegyük föl indirekt, hogy csak véges sok ilyen prímszám van, legyenek ezek p1,p2,...,p. Tekintsük az N=4p1p2...p-1 számot. Ez 1-nél nagyobb, ezért prímszámok szorzata. E prímtényezők mindegyike 2-től és mindegyik pj-től különbözik, és így 4-gyel osztva már csak 1 maradékot adhat. Ekkor azonban a szorzatuk is 1-et ad maradékul, ami ellentmondás, mert N-1(4).  
 

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 a=12, akkor csak négy sorozat jön szóba: 12k+1, 12k+5, 12k+7, 12k+11. Ezekben egymáshoz képest ,,ugyanannyi'' prímszám van, a következő értelemben. Jelölje πb(x) a 12k+b alakú, x-nél nem nagyobb prímek számát. Ekkor b=1,5,7,11 mindegyikére
πb(x)x/log(x)14(x)
(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 x-ig körülbelül x/log(x), lásd [2], 5.4.1. tétel).
Ugyanakkor a 2.1. feladat megoldása nagyon ,,kevés'' 4k-1 alakú prímet szolgáltat. A kapott ,,új'' prímről ugyanis nem tudunk mást, mint hogy legföljebb N. Ez a sorozat pedig nagyon gyorsan növekszik: a 3-ból kiindulva a kapott számok 11, 131, 17 291, 298 995 971. Az Olvasónak érdemes meggondolnia, hogy az eljárás x-ig csak körülbelül loglog(x) darab 4k-1 alakú prímet biztosít. Ugyanakkor az x-nél nem nagyobb 4k-1 alakú prímek számának nagyságrendje x/2log(x).
 
Elemien bizonyítható az is, hogy végtelen sok 4k+1 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 p prímszám 4k-1 alakú, akkor pa2+b2-ből pa és pb következik. Speciálisan az u2+1 alakú számok mindegyik páratlan prímosztója 4k+1 alakú.
 
Megoldás. Ha a és b valamelyike osztható p-vel, akkor pa2+b2 miatt a másik is. Ha egyik sem, akkor az a2-b2(p) kongruenciát (p-1)/2-edik hatványra emelve az Euler‐Fermat-tétel miatt 1(-1)(p-1)/2(p) adódik. Mivel p-1(4), ezért (-1)(p-1)/2=-1. Így 1-1(p), ami ellentmond annak, hogy p páratlan.  
 

2.3. feladat. Igazoljuk, hogy végtelen sok 4k+1 alakú prímszám van.
 
Megoldás. Tegyük föl indirekt, hogy csak véges sok ilyen prímszám van, legyenek ezek p1,p2,...,p. Tekintsük az N=(2p1p2...p)2+1 számot. Ez 1-nél nagyobb, ezért prímszámok szorzata. E tényezők mindegyike 2-től és mindegyik pj-től különbözik, és a 2.2. feladat miatt 4-gyel osztva 1 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 (c,m)=1. Mutassuk meg, hogy van olyan pozitív k egész, melyre ck1(m).
 
Megoldás. Mivel véges sok modulo m maradék van, léteznek olyan i<j egészek, hogy cicj(m). A modulushoz relatív prím ci-vel egyszerűsítve cj-i1(m) adódik.  
 

Ha r a legkisebb olyan tulajdonságú pozitív k szám, ami az előző feladatban szerepel, akkor c hatványai egy r hosszúságú periódus szerint ismétlődnek, és így c különböző hatványainak száma r. Ezt az r számot c rendjének nevezzük modulo m, jele om(c). A periodicitás miatt ck1(m)om(c)k. Az Euler‐Fermat-tételből ezért következik, hogy om(c)φ(m).
 
3.2. gyakorlat. Számítsuk ki 2 és 3 rendjét modulo 7.
 
Megoldás. Mivel 2 hatványai modulo 7 rendre 2, 4, 81(7), ezért o7(2)=3. Hasonlóan, 3 első három hatványa modulo 7 rendre 3, 92 és 33=32323=6. Tovább nem érdemes számolni a következő okból. Az eddigiek szerint 3 rendje nagyobb, mint 3. De ez a rend osztója φ(7)=6-nak, ezért csakis 6 lehet.  
 
3.3. feladat. Legyen p prímosztója az u2+1 számnak. Igazoljuk, hogy op(u)=4 vagy p=2.
 
Megoldás. Mivel pu2+1u4-1, ezért u41(p), azaz op(u)4. Ha ez a rend nem 4, akkor 1 vagy 2. Mindkét esetben u21(p). A feltétel szerint u2-1(p), ezért -11(p), azaz p=2.  
 

Innen persze páratlan p esetén 4=op(u)φ(p)=p-1, azaz megkaptuk a 2.2. feladat második állítását. Ez a megoldás azt sugallja, hogy ha a 4k+1 sorozat helyett az nk+1 sorozatban keresünk prímeket, akkor u2+1u4-1 helyett az un-1 kifejezés alkalmas tényezőjével célszerű dolgoznunk.
Az xn-1 polinom szorzatra bontását körosztási polinomok segítségével végezhetjük el. Az xn-1 gyökei az εk=cos(2πk/n)+isin(2πk/n) komplex számok, ahol 1kn, vagyis az n-edik komplex egységgyökök (lásd [3], 1.5. szakasz). Mivel egész együtthatós polinomokat szeretnénk kapni, ezért xn-1 gyöktényezői közül bizonyosakat összevonunk. Legyen
Φn(x)=1kn;(k,n)=1(x-εk).
E polinom gyökei a primitív n-edik egységgyökök, maga Φn(x) pedig az n-edik körosztási polinom. Az alábbi tétel xn-1 kívánt szorzatra bontását szolgáltatja.
 
3.4. tétel. Ha n1, akkor a következők teljesülnek.
(1)Φn(x) foka φ(n).
(2)Érvényes az
xn-1=dnΦd(x)
azonosság.
(3)Φn(x) 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 Φn(x) polinomokat, amikor n=1,2,3,4,12.
 
Megoldás. Mivel a nevező n=1 esetén üres szorzat, Φ1(x)=x-1 (vagy a definícióból közvetlenül láthatjuk, hogy az 1 az egyetlen primitív ,,1-edik'' egységgyök). A képletből Φ2(x)=(x2-1)/(x-1)=x+1 és Φ3(x)=(x3-1)/(x-1)=x2+x+1. Mivel Φ1(x)Φ2(x)=x2-1, ezért Φ4(x)=(x4-1)/(x2-1)=x2+1. Hasonlóan összevonva a nevezőben
Φ12(x)=x12-1Φ1(x)Φ2(x)Φ3(x)Φ4(x)Φ6(x)=x12-1(x6-1)Φ4(x)=x6+1x2+1=x4-x2+1
(hiszen Φ1(x)Φ2(x)Φ3(x)Φ6(x)=x6-1).  
 

A Φ4(x)=x2+1 összefüggés alapján a 3.3. feladat állítása úgy is fogalmazható, hogy ha p prímosztója a Φ4(u) számnak, akkor op(u)=4 vagy p4. 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 p prímosztója a Φn(u) számnak. Ekkor op(u)=n vagy pn.
 
Mivel Φn(u)un-1, ezért p és u relatív prímek, tehát az op(u) rend értelmes.
 
3.7. feladat. Legyenek f(x), g(x), h(x) egész együtthatós polinomok, és tegyük föl, hogy f és g konstans tagja is osztható p-vel. Ekkor az f(x)g(x)h(x) szorzatpolinomban a konstans tag is, az x-es tag együtthatója is osztható p-vel.
 
Megoldás. Legyen f(x)=a0+a1x+..., g(x)=b0+b1x+..., h(x)=c0+c1x+.... Ekkor a szorzatpolinomban a konstans tag a0b0c0, az x-es tag együtthatója pedig a0b0c1+a0b1c0+a1b0c0.  
 

Megjegyezzük, hogy ha hajlandóak vagyunk polinomok együtthatóival modulo p számolni, akkor ez a megoldás egyszerűbben is megfogalmazható. A modulo p vett maradékok egy p elemű Zp testet alkotnak. Vegyük mindhárom polinom együtthatóit modulo p, ekkor Zp fölötti polinomokat kapunk. A feltétel szerint f(x) és g(x) is osztható x-szel Zp[x]-ben, tehát f(x)g(x)h(x) osztható x2-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 p prímosztója a Φn(u) számnak, de op(u)n. Igazoljuk, hogy ekkor van olyan mn, hogy mn és pΦm(u).
 
Megoldás. Mivel pΦn(u)un-1, ezért un1(p), és így op(u)n. Legyen op(u)=d<n. Ekkor ud1(p), azaz pud-1=mdΦd(u). Mivel p prím, osztója valamelyik tényezőnek.  
 

3.9. feladat. Igazoljuk a 3.6. tételt.
 
Megoldás. Tegyük föl, hogy p prímosztója a Φn(u) számnak, de op(u)n. Az előző feladat miatt van olyan mn, hogy mn és pΦm(u). Legyen f(x)=Φn(x+u), g(x)=Φm(x+u), továbbá legyen h(x) mindazon Φ(x+u) polinomok szorzata, ahol n de n,m. Ha a 3.4. tétel (2) állítását xn-1 helyett (x+u)n-1-re alkalmazzuk, akkor f(x)g(x)h(x)=(x+u)n-1 adódik. Helyettesítsünk x=0-t, ekkor láthatjuk, hogy f(x) és g(x) konstans tagja is osztható p-vel. Ezért a 3.7. feladat miatt az (x+u)n-1 polinom x-es tagjának együtthatója osztható p-vel. A binomiális tétel szerint ez nun-1. Mivel pΦn(u)un-1 miatt p relatív prím u-hoz, ezért pn.  
 

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 nk+1 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 nk-1 eset gondolatmenetét.
 
3.10. feladat. Mutassuk meg, hogy minden pozitív K egészhez van olyan u egész, hogy Φn(u) osztható egy K-nál nagyobb p prímszámmal.
 
Megoldás. Legyen u=LK!, ahol az L pozitív egész értékét később választjuk meg. Mivel Φn(x) ha x, ezért L-et elég nagyra választva Φn(LK!)>1, és így Φn(u)=Φn(LK!)-nak van egy p prímosztója. Tudjuk, hogy Φn(u)un-1, ezért p relatív prím u=LK!-hoz. Így p>K.  
 
3.11. feladat. Igazoljuk, hogy ha a p prím nagyobb n-nél, és u olyan egész szám, amelyre pΦn(u), akkor a p prím nk+1 alakú.
 
Megoldás. A 3.6. tételből következik, hogy op(u)=n, hiszen p>n miatt pn nem teljesül. Ezért n=op(u)φ(p)=p-1.  
 
3.12. feladat. Bizonyítsuk be, hogy minden n>0 esetén végtelen sok nk+1 alakú prímszám van.
 
Megoldás. Tegyük föl indirekt, hogy csak véges sok ilyen prímszám van, legyenek ezek p1,p2,...,p. Válasszuk a K számot úgy, hogy ezek mindegyikénél, továbbá n-nél is nagyobb legyen. A 3.10. feladat miatt van olyan u egész, továbbá egy K-nál nagyobb p prím, melyre pΦn(u). Az előző feladat szerint a p prím nk+1 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).