| Cím: | Prímképletek | ||
| Szerző(k): | Laczkovich Miklós | ||
| Füzet: | 1997/október, 385 - 398. oldal |  PDF | MathML |
|
| 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. A 31, 331, 3331, 33331, 333331, 3333331, 33333331 számok mind prímek. Ezt úgy is kifejezhetjük, hogy a képlet prímszámot szolgáltat az , 3, , 8 értékek mindegyikére. A szám azonban már összetett, mert osztható 17-tel. Ezt az osztás elvégzése nélkül is beláthatjuk a kongruencia jelölésének felhasználásával. Azt mondjuk, hogy kongruens -vel modulo (képletben ), ha és azonos maradékot adnak -mel osztva; azaz, ha osztható -mel. Könnyű ellenőrizni, hogy azonos modulushoz tartozó kongruenciákat szabad összeadni és szorozni. Azaz, ha és , akkor és . De mégsem lesz mindegyikük prím. A -adik bekeretezett szám ugyanis , és ez biztosan összetett -ra, hiszen ekkor . Meglepő módon a képlet a , 1, , 15 helyettesítési értékek mindegyikére prímet ad. Ha meg akarjuk keresni azokat a pozitív egészeket, amelyekre prímszám a , 1, , értékek mindegyikére, akkor a következőképpen okoskodhatunk. Először is (-t véve) prímszám kell, hogy legyen. Ha , akkor az és számok nem lehetnek sem 3-mal, sem 5-tel oszthatók, így 3-mal osztva 2-t, 5-tel osztva pedig 1-et vagy 2-t ad maradékul. Mivel páratlan is, ezért a 30-cal való osztási maradéka csak 11 vagy 17 lehet. Egy további feltétel, hogy -nek is prímnek kell lennie. Tegyük fel ugyanis, hogy és . Ekkor és , ahol tehát Azt kaptuk tehát, hogy vagy , 3, 5, vagy pedig olyan vagy alakú prímszám, amelyre is prím. A 100-nál kisebb számok közül ezeket a feltételeket csak a 2, 3, 5, 11, 17, 41, valamint a 71 elégítik ki. Ezek közül a , 3, 5, 11, 17, 41 számokra valóban teljesül, hogy prímszám a , 1, , értékek mindegyikére. A 71-re ez már nem igaz, mert összetett. Sokáig megoldatlan volt, hogy a 41 után van-e még ilyen tulajdonságú szám. Csak az 1960-as években sikerült bebizonyítani, hogy ilyen szám nem létezik. A fentiek alapján természetesen vetődik fel az a kérdés, hogy van-e olyan képlet, amelynek a pozitív egészekben felvett értékei mind prímek. Először megmutatjuk, hogy egy egész együtthatós polinom ‐ hacsak nem konstans ‐ nem szolgáltathat ilyen képletet. Ennek bizonyításához két segédtételre lesz szükségünk. Először is belátjuk, hogy ha egész együtthatós polinom, akkor esetén . Valóban,
A másik állítás, amelyre szükségünk van, azt állítja, hogy ha a Világos, hogy ha nem konstans, és a főegyütthatója negatív, akkor minden előre magadott számnál kisebb lesz, ha elég nagy. Most már könnyen beláthatjuk, hogy ha az egész együtthatós polinom nem konstans, akkor a értékek nem lehetnek mind prímek. Válasszunk ugyanis egy olyan pozitív egészet, amelyre . Ha (, 2, ), akkor , tehát , azaz osztható -mel. De tudjuk, hogy , ha elég nagy; mondjuk, ha . Ekkor minden elég nagy -re , így és osztható -mel, tehát összetett. A polinomoknál jóval komplikáltabb képletekről is beláthatjuk, hogy nem szolgáltathatnak csupa prímszámot. Ennek tárgyalásához szükségünk lesz az ún. ,,kis Fermat-tételre'', ami azt állítja, hogy ha prím és nem osztható -vel, akkor . Ezt így láthatjuk be: Az , , , számok csupa különböző maradékot adnak -vel osztva. Valóban, ha , akkor . Mivel prím és nem osztható -vel, ebből következik, hogy . Ha tehát , , akkor szükségképpen . Mivel az , , , számok egyike sem osztható -vel, ebből következik, hogy a -vel vett osztási maradékaik az , 2, , számok (esetleg más sorrendben). Így , azaz . Ezért , tehát , hiszen nem osztója -nak. Ennek felhasználásával lássuk be például, hogy az képlet nem szolgáltathat csupa prímet. Az érték mindenesetre prím, ezért és . Ebből következik, hogy és minden pozitív egészre. Ha tehát , akkor Most bizonyítsuk be, hogy az
A következő általános tétel hasonló módszerrel bizonyítható. Legyen olyan képlet, amely alakú kifejezések szorzatainak összege, ahol és egész együtthatós polinomok, melyek közül a -ek főegyütthatói pozitívak. Ha az (, 2, ) értékek között van végtelen sok különböző, akkor ezen értékek között van végtelen sok összetett szám. Itt a végtelen sok különböző értékre vonatkozó feltétel lényeges, mert pl. az képlet a fenti alakú és minden értéke prím. A fenti tétel azt állítja, hogy ha csupa prímszámot ad minden pozitív egészre, akkor az -et definiáló képlet a fent leírtaknál bonyolultabb kell, hogy legyen. Ha például olyan prímképletet keresünk, amelyben csak az összeadás, kivonás, szorzás és hatványozás műveleteit használhatjuk, akkor szerepelnie kell benne olyan ,,emeletes hatványnak'' (azaz kitevőben szereplő hatványnak), amelynek a kitevője tartalmazza az változót. A legegyszerűbb ilyen képlet: . Ez persze -ra nem ad prímeket, mert mindig páros. De mi a helyzet a képlettel? Az , 1, 2, 3, 4 számokat behelyettesítve a 3, 5, 17, 257, 65537 értékeket kapjuk; mindnyájan prímek. Ennek alapján Pierre de Fermat azt sejtette (1640 körül), hogy minden -re prímszám. Ez a sejtés csaknem 100 éven át megoldatlan maradt, mert a következő szám: Végül is Leonhard Euler volt az, aki 1732-ben a kérdést eldöntötte. Euler felismerte, hogy prímosztói csak speciális alakúak lehetnek, nevezetesen minden prímosztója alakú, ahol pozitív egész. Ezt a következőképpen láthatjuk be. Legyen egy prímosztója -nek. Mivel páratlan, ezért a kis Fermat-tétel szerint . Legyen a legkisebb pozitív egész, amelyre . Ekkor a 2-hatványok -vel való osztási maradékai szerint periodikus sorozatot alkotnak. Valóban, alapján , , , és hasonlóan, minden -re (a kongruenciákat (mod ) értve). Ebből következik, hogy minden , 2, -re. Másrészt választása folytán ha , ezért a periodicitásból következik, hogy akkor és csak akkor ad 1 maradékot -vel osztva, ha osztható -vel. Mármost , ugyanis , tehát osztható -nel, tehát -vel is. A fentiek szerint ebből következik, hogy . Megmutatjuk, hogy szükségképpen . Valóban, esetén osztója lenne -nek is. Ebből viszont következne, holott , hiszen . Ezzel beláttuk, hogy . Mivel pedig , ezért tehát azaz ahol pozitív egész. Valójában Euler azt is belátta, hogy ha és a prím osztója -nek, akkor ahol pozitív egész. Meg lehet mutatni ugyanis, hogy ha a prím alakú, akkor . A fenti okoskodásban ezért tehát azaz ahol pozitív egész. Ezt -re alkalmazva azt kapjuk, hogy minden prímosztója alakú. Ez jelentősen leszűkíti a lehetőségeket. A 2-nél nagyobb prímek ugyanis 128-cal osztva 64-féle maradékot adhatnak (nevezetesen az , 3, , 127 számokat), és azt várhatjuk, hogy a 65536-nál kisebb prímeknek durván 1/64-ed része lesz alakú. Ez kb. prímet jelent. Ezért annak eldöntéséhez, hogy prímszám-e, a 6500 osztás helyett várhatóan a legrosszabb esetben is elég száz-egynéhány osztást elvégezni. Euler elszánta magát ennek az elvégzésére. Óriási szerencséje volt; az első alakú prím, 257, ugyan nem osztója -nek, de a második, 641, már igen: . Ezzel Fermat sejtése megdőlt: az képlet nem állít elő minden -re prímszámot. Egyébként a következő Fermat-szám, prímtényezőkre bontását csak 1880-ban sikerült megtalálni: . Az ezt követő Fermat-szám, faktorizációját 1970-ben találták meg; eszerint egy 17-jegyű és egy 22-jegyű prím szorzata. Azóta kiderült, hogy összetett szám minden -re (bár nem mindegyiküknek sikerült meghatározni a prímtényezős alakját). Sok nagyobb indexű Fermat-számot is megvizsgáltak, de még egy prímet sem találtak közöttük. A fentiekből az a tanulság, hogy hacsak egy képletről nem tudjuk eleve, hogy valamilyen oknál fogva minden értéke prímszám lesz, akkor nem várhatjuk el, hogy ezt ,,szívességből'' megtegye, még akkor sem, ha az első néhány értéke prím (mint pl. az vagy a képletek esetében). Eddig senki nem talált olyan képletet, amely egész számokból és az változóból az összeadás, kivonás, szorzás és hatványozás műveleteinek segítségével épül fel, és amely minden pozitív egész -re prímszámot szolgáltat (azt is feltéve persze, hogy a képlet végtelen sok különböző értéket ad). A következőkben megmutatjuk, hogy a feltételek enyhítésével már találhatunk ilyen képleteket. Először olyan képleteket tekintünk, amelyekben nemcsak egészek, hanem tetszőleges valós konstansok is szerepelhetnek. Ekkor persze az szám egészrészét megadó függvény használatát is meg kell engednünk, mert különben nem tudjuk biztosítani, hogy a képlet egész számokat szolgáltasson. (E függvény definíciója a következő: az az egyértelműen meghatározott egész szám, amelyre . Így pl. .) Ezek felhasználásával már viszonylag egyszerű képletet adhatunk az -edik prímszámra, amelyet a következőkben -nel fogunk jelölni. Megmutatjuk, hogy van olyan valós szám, amelyre
A fenti konstrukcióban hallgatólagosan felhasználtuk, hogy jegyeinek száma legfeljebb , mert különben ,,nem férne el''. Megmutatjuk, hogy jegyeinek száma legfeljebb . Nevezzünk egy számot négyzetmentesnek, ha nem osztható 1-nél nagyobb négyzetszámmal. Ez azzal ekvivalens, hogy az prímtényezős felbontásában minden prím első hatványon szerepel; azaz, hogy különböző prímek szorzata. Bármely egész szám előáll mint egy négyzetszám és egy négyzetmentes szám szorzata. Ha ugyanis -t elosztjuk azzal a legnagyobb osztójával, amely négyzetszám, akkor a hányados nyilván négyzetmentes lesz. (Ha négyzetmentes, akkor 1-gyel osztunk.) Írjuk fel a -nél nem nagyobb számokat alakban, ahol négyzetmentes. Itt , tehát . A szám különböző prímek szorzata, melyek mindegyike legfeljebb , hiszen . Így -t úgy kapjuk, hogy a , , , prímek közül néhányat összeszorzunk. Ezt -féleképpen tehetjük meg (annyiféleképpen, ahány részhalmaza van a halmaznak). A számot tehát legfeljebb -féleképpen, a számot pedig legfeljebb -féleképpen választhatjuk meg. Mivel alakban minden -nél nem nagyobb szám előáll, ebből következik, hogy , , és így . Mivel , ezért legfeljebb -jegyű. A (4) képletre visszatérve megállapíthatjuk, hogy a puszta érdekességén kívül más haszna nemigen van; például nem használhatjuk fel prímszámok gyártására. Ahhoz ugyanis, hogy a képlet segítségével értékét meghatározhassuk, tudnunk kellene értékét. Ehhez viszont már ismernünk kellene az összes prímszámot. Egyébként vannak még egyszerűbb prímképletek is: létezik például egy valós szám úgy, hogy prímszám lesz minden pozitív egész értékére. Ennek a képletnek ugyanaz a baja, mint (4)-nek: meghatározásához végtelen sok prímszámot kell felhasználni. Most rátérünk azokra a prímképletekre, amelyekben a konstansok csak egész számok lehetnek, de a felhasználható műveleteket nem korlátozzuk. Megmutatjuk, hogy ha az alapműveleteken kívül felhasználhatjuk az (egészrész), (törtrész) függvényeket, valamint a Ha az szám prím, akkor az , , , számok egyike sem egész, tehát az törtrészek egyike sem 0. Ekkor tehát a szorzat minden tényezője (mert egy és 0 közé eső szám egészrésze). A szorzat értéke tehát , hiszen a tényezők száma , ami páratlan. Ha viszont összetett, akkor egész szám lesz legalább egy -re, és ekkor alapján a fenti szorzat értéke 0. Így esetén a
Ezt így láthatjuk be: Az állítás , 3-ra nyilvánvaló, tehát feltehetjük, hogy . A kis Fermat tétel bizonyításakor megmutattuk, kogy ha nem osztható -vel, akkor az , , , számok -vel vett osztási maradékai az , 2, , számok (esetleg más sorrendben). Ebből következik, hogy az , 2, , számok között pontosan egy olyan szám van, amelyre . Nevezzük ezt a számot reciprokának (mod ). Ha , akkor és reciprokai különbözők. Valóban, -ből következik, hogy , tehát , hiszen . Ha egy szám reciproka önmaga, akkor , , tehát vagy . A fentiekből következik, hogy a 2, 3, , számok mindegyikét a reciprokával párosítva diszjunkt párokat kapunk. Mivel az egy párhoz tartozó számok szorzata -vel osztva 1-et ad maradékul, ezért , tehát .
Természetesen jó volna olyan prímképletet találni, amelyben a felhasznált műveletek száma minimális. Már említettük, hogy nem ismeretes olyan prímképlet, amelyben csak összeadás, szorzás és hatványozás szerepel. A következőkben a célunk annak bizonyítása, hogy van olyan prímképlet, amelyben csak összeadás, kivonás, szorzás, és maximum szerepel. Ennek az ismertetését messziről kell kezdenünk. Diophantosz görög matematikus volt, aki a harmadik században élt Alexandriában. ,,Aritmetika'' című művében egész együtthatós egyenletek egész, illetve racionális megoldásait vizsgálta, és az ilyen egyenleteket azóta diofantoszi vagy diofantikus egyenleteknek nevezik. Ilyenek például
A (8) alatt felsorolt egyenletek triviális megoldásai azok, amelyekre , vagy , . Az első két egyenletnek vannak nem-triviális megoldásai is, pl. , illetve . A harmadiknak viszont nem ismerjük egyetlen nem-triviális megoldását sem, de az sincs bizonyítva, hogy ilyen megoldás nem létezik. Ezek a jelenségek tipikusak: előfordul, hogy egész egyszerűnek látszó diofantikus egyenletek megoldása a legnagyobb nehézségbe ütközik, sőt, gyakori eset, hogy azt sem tudjuk eldönteni, hogy a kérdéses egyenletnek van-e egyáltalán megoldása. Ezek a tapasztalatok vezették David Hilbertet 1900-ban az alábbi kérdéshez: van-e olyan algoritmus (valamely mechanikus, automatikus eljárás), amely bármely megadott diofantikus egyenletről el tudja dönteni, hogy van-e megoldása? Ha Hilbert korában már léteztek volna számítógépek, nyilván úgy tette volna a kérdést, hogy van-e ilyen számítógépes program. A probléma megoldására 70 évig kellett várni. Ahhoz, hogy a megoldást megérthessük, be kell vezetnünk három fogalmat. Azt mondjuk, hogy természetes számoknak egy végtelen sorozata rekurzív, ha van olyan algoritmus (azaz számítógépes program), amely bármely számról el tudja dönteni, hogy tagja-e a sorozatnak vagy sem. Például a 2-hatványok sorozata rekurzív, mert bármely pozitív egészről el tudjuk dönteni, hogy 2-hatvány-e vagy sem: addig osztjuk 2-vel, amíg páratlan számot kapunk. Ha ez a szám 1, akkor 2-hatvány; egyébként pedig nem. A prímszámok sorozata is rekurzív, hiszen bármely számról el tudjuk dönteni, hogy prím-e: csak azt kell megvizsgálni, hogy osztható-e valamely nála kisebb, de 1-nél nagyobb számmal. (Azzal most nem foglalkozunk, hogy ennek eldöntése mennyi ideig tart; a lényeg az, hogy az algoritmus véges sok lépésben elvégezhető legyen.) Egy sorozat akkor és csak akkor rekurzív, ha van olyan számítógépes program, amely a sorozat tagjait növekvő sorrendben kinyomtatja. Ha ugyanis a sorozat rekurzív, akkor írhatunk egy olyan programot, amely egymás után megvizsgálja a természetes számokat és eldönti, hogy tagjai-e a sorozatnak, és ha egy számról úgy találja, hogy igen, akkor -et kinyomtatja. Megfordítva, ha van egy nyomtatóprogram, amely a sorozat tagjait növekvő sorrendben kinyomtatja, akkor a következő algoritmust készíthetjük annak eldöntésére, hogy egy szám tagja-e a sorozatnak. Indítsuk el a nyomtatóprogramot, és várjunk addig, amíg egy -nél nagyobb szám megjelenik. Ha az eddig kinyomtatott számok között szerepel, akkor tagja a sorozatnak, egyébként pedig nem (hiszen később már nem kerülhet sorra). Más a helyzet, ha van ugyan olyan program, amely a sorozat elemeit kinyomtatja, de nem feltétlenül növekvő sorrendben. (Az ilyen sorozatokat rekurzíve felsorolható sorozatoknak nevezzük.) Egy ilyen sorozat esetében, ha egy szám megjelenik a kinyomtatott számok között, akkor tagja a sorozatnak. Ha viszont nem tagja a sorozatnak, akkor ezt esetleg soha nem tudjuk meg, hiszen soha nem lehetünk biztosak abban, hogy nem lesz-e később kinyomtatva. Tehát egy rekurzíve felsorolható sorozat nem feltétlenül rekurzív. A matematikai logika egyik nevezetes felfedezése, hogy rekurzíve felsorolható, de nem rekurzív sorozatok valóban léteznek, sőt, konkrétan meg is adhatók. (Ezt úgy kell érteni, hogy konkrétan megadható olyan program, amely kinyomtatja a sorozat elemeit. A sorozatot magát nem tudjuk megadni abban az értelemben, hogy a tagjait felsoroljuk növekvő sorrendben, hiszen akkor a sorozat rekurzív volna.) A harmadik fogalom, amelyre szükségünk lesz, a diofantikus sorozat fogalma. Egy diofantikus egyenlet általános alakja (az egyenlet jobb oldalának bal oldalra vitele után) , ahol egész együtthatós polinom; azaz olyan kifejezés, amely az , , változókból és egész számokból képződik az összeadás, kivonás és szorzás műveleteinek felhasználásával. Egy sorozatot akkor nevezünk diofantikusnak, ha létezik egy egész együtthatós polinom a következő tulajdonsággal: egy természetes szám akkor és csak akkor tagja a sorozatnak, ha a diofantikus egyenletnek van megoldása a természetes számok körében, azaz ha vannak természetes számok úgy, hogy . Ekkor azt mondjuk, hogy a sorozatot a polinom generálja. A négyzetszámok sorozata például diofantikus, mert egy szám akkor és csak akkor négyzetszám, ha az (egyváltozós) egyenlet megoldható a természetes számok körében. Tehát a négyzetszámok sorozatát az polinom generálja. Nem nehéz belátni, hogy minden diofantikus sorozat rekurzíve felsorolható. Tegyük fel ugyanis, hogy a sorozatot a polinom generálja. A rövidség kedvéért nevezzük vektornak a természetes számokből álló -hosszúságú számsorozatokat. Ekkor az összes vektort felsorolhatjuk egyetlen végtelen sorozatban. Ezt úgy tehetjük meg, hogy elsőként felírjuk az vektort, majd azokat, amelyekben (ezekből van), majd azok jönnek, amelyekben , és így tovább. Minden egyes vektorra számítsuk ki a értéket. Ha ez nulla, akkor nyomtassuk ki -et. Ha nem nulla, akkor ugorjunk át a következő vektorra. Nyilvánvaló, hogy ilyen módon éppen azokat az számokat nyomtattuk ki, amelyekre a diofantikus egyenlet megoldható, és ezzel megmutattuk, hogy a kérdéses sorozat rekurzíve felsorolható. Mármost Hilbert problémájának megoldásában a kulcslépés annak bizonyítása volt, hogy minden rekurzíve felsorolható sorozat szükségképpen diofantikus. A három fogalom logikai kapcsolata tehát a következő: A Hilbert-problémának ez a negatív megoldása nem jelenti azt, mintha találtunk volna egy olyan diofantikus egyenletet, amelyről sohasem dönthetjük el, hogy van-e gyöke vagy sem. Elvileg elképzelhető, hogy előbb-utóbb mindegyik diofantikus egyenletről kideríthetjük, hogy megoldható-e. Ebben az esetben azonban a módszernek egyenletről egyenletre változnia kell; általános, minden egyenletre egyaránt alkalmazható algoritmus nincs. Most térjünk vissza a prímszámokhoz. Mivel a prímszámok sorozata rekurzív, ezért rekurzíve felsorolható, tehát diofantikus. Így létezik egy polinom, amely a prímszámok sorozatát generálja. Képezzük a (i) . Ekkor prím (mert a prímeket generálja), és . (ii) . Ekkor és így Azt kaptuk tehát, hogy -ba természetes számokat helyettesítve vagy prímet vagy nem-pozitív számot kapunk. Másrészt így minden prímet megkapunk, mert ha prím, akkor alkalmas , , -ra, tehát . A fentieket összefoglalva megállapíthatjuk, hogy a
A bonyolultságtól eltekintve (9) majdnem ideális prímképletnek tekinthető; csak a többváltozós jellege zavaró egy kicsit. Felmerül a kérdés, nem lehetne-e hasonló, de egyváltozós képletet nyerni. Esetleg lemondhatnánk arról, hogy a képlet minden prímet előállítson, megelégednénk végtelen sok prím előállításával is. Egy egyszerű ötlettel (9) azonnal egyváltozóssá tehető: írjunk az változók helyébe egy-egy függvényt. Az így kapott
Látszólag készen vagyunk. Azonban a dolog mégsem ilyen egyszerű: ha pl. , , gyanánt egész együtthatós polinomokat választunk, akkor a (10) képlet csak véges sok különböző értéket fog előállítani. Ugyanis ebben az esetben is egész együtthatós polinom lesz. Ha konstans, akkor is konstans. Ha nem konstans és a főgyütthatója negatív, akkor minden elég nagy -re , tehát . Ha viszont nem konstans és a főgyütthatója pozitív, akkor minden elég nagy -re , tehát . Ez azt jelentené, hogy minden elég nagy -re prímszám, amiről már beláttuk, hogy lehetetlen (egy nem konstans egész együtthatós polinom az végtelen sok értékére összetett számot ad). Ez az eset tehát nem fordulhat elő Ez a jelenség első pillantásra hihetetlennek tűnik: a polinomnak végtelen sok pozitív értéke van (hiszen minden prímet felvesz), de akárhogy helyettesítünk egész együtthatós polinomokat a változók helyébe, a kapott polinom vagy konstans, vagy pedig negatív minden elég nagy -re. Ez a különös jelenség azonban már egész egyszerű polinomok körében is fellép. Meg lehet mutatni, hogy a polinom is rendelkezik ezzel a tulajdonsággal. Ha el akarjuk érni, hogy a (10) képlet végtelen sok prímet szolgáltasson, a legegyszerűbb az függvényeket úgy megválasztani, hogy minden vektor előálljon alakban. Ekkor (10) minden prímet elő fog állítani. Ha egy vektorhoz létezik egy természetes szám, melyre akkor azt fogjuk mondani, hogy az függvények kódolják az vektort. Olyan függvényeket keresünk tehát, amelyek minden, nemnegatív egészekből álló vektort kódolnak. Mint láttuk, ezt polinomokkal nem érhetjük el, ezért fel kell használnunk más függvényeket is. Ekkor azonban egy újabb technikai nehézség lép fel. Ha szeretnénk minél egyszerűbb képleteket használni, akkor az függvények nemcsak a pozitív egészekből, hanem a tetszőleges egészekből álló vektorokat is kódolni fogják. A polinom a negatív egészekben felvehet pozitív összetett számot is, és akkor (10) értéke nem lesz minden -re prím. Ezen a következő módszerrel segíthetünk. Legyen , és tekintsük a Olyan függvényeket fogunk gyártani, amelyek minden -hosszúságú, természetes számokból álló vektort kódolnak. Ezeket az változók helyére írva egyváltozós prímképletet kapunk. A konstrukciót csak -re és -ra adjuk meg, de világos lesz, hogy minden -re elvégezhető. Lássuk be először, hogy az függvénypár minden olyan számpárt kódol, amelyre . Legyen ugyanis . Ekkor Ha most , tetszőleges természetes számok, akkor , tehát van olyan amelyre és . Ekkor és , tehát az függvénypár minden természetes számokból álló számpárt kódol. Most tekintsük az esetet. Belátjuk először, hogy a Ha most , , tetszőleges természetes számok, akkor , tehát van olyan , amelyre , és . Ebből következik, hogy a , és függvények minden természetes számokból álló számhármast kódolnak. Ezt a konstrukciót minden -re elvégezhetjük. Ha az így kapott függvényeket -be helyettesítjük, akkor végül is a következő tételt kapjuk. Létezik olyan kifejezés, amely az , , , , függvények egész együtthatós polinomja (azaz a fenti függvényekból és egész számokból kapható az összeadás, kivonás és szorzás műveleteinek segítségével), és amelyre a (, 1, ) számok halmaza pontosan a prímszámok halmazával egyenlő. Ilyen alakban nem csak a prímszámok állíthatók elő. Ha ismét áttekintjük a tételhez vezető gondolatmenetet, láthatjuk, hogy bármely rekurzíve felsorolható sorozatnak van ilyen előállítása. Mindazonáltal a prímszámok előállításával kapcsolatban felmerül néhány érdekes kérdés. 1. A prímszámokat előállító képletekben mennyi az minimális értéke? (A fenti gondolatmenet -et ad, hiszen -ra az ismert legkisebb érték 9, és .) Lehet-e pl. olyan prímképletet megadni, amely csak az és függvényeket használja? 2. Megadható-e olyan, fenti alakú függvény, amelyre minden -re?
|