Ugrás a tartalomhoz

Matematikai mozaik

Andrásfai Béla, Bakos Tibor, Bognár Jánosné, Bognár Mátyás, Gallai Tibor, Hódi Endre, Laczkovich Miklós, Molnár Ferenc, Reimann István, Rényi Alfréd, Révész Pál, Rónyai Lajos, Surányi János, Vadkerty Tibor, Varga Tamás

Typotex

PRÍMKÉPLETEK

PRÍMKÉPLETEK

LACZKOVICH, MIKLÓS


Tartalom

IRODALOM

A 31, 331, 3331, 33 331

33 331 , 333 331 333 331 , 3 333 331 3 333 331 , 33 333 331 33 333 331 számok mind prímek. Ezt úgy is kifejezhetjük, hogy a (10^n–7)∕3 ( 10 n 7 ) 3 képlet prímszámot szolgáltat az n=2 n = 2 , 3, …, 8 értékek mindegyikére. A 333 333 331=(10^9–7)∕3 333 333 331 = ( 10 9 7 ) 3 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 a a kongruens b b -vel modulo m m (képletben a≡b(mod m) a b ( mod m ) ), ha a a és b b azonos maradékot adnak m m -mel osztva; azaz, ha a–b a b osztható m m -mel. Könnyű ellenőrizni, hogy azonos modulushoz tartozó kongruenciákat szabad összeadni és szorozni. Azaz, ha a≡b(mod m) a b ( mod m ) és c≡d(mod m) c d ( mod m ) , akkor a+c≡b+d(mod m) a + c b + d ( mod m ) és a⋅c≡b⋅d(mod m) a c b d ( mod m ) .

Mivel 102=17⋅6

102 = 17 6 ,  így   10^9=100^4⋅10≡(–2)^4⋅10≡–10≡7(mod 17) 10 9 = 100 4 10 ( 2 ) 4 10 10 7 ( mod 17 ) , tehát 10^9–7 10 9 7 osztható 17-tel. Meg lehet mutatni egyébként, hogy 33…331 33 331 sohasem osztható a 2, 3, 5, 7, 11, 13, 37 prímek egyikével sem. Nem ismeretes, hogy van-e végtelen sok 33…331=(10^n–7)∕3 33 331 = ( 10 n 7 ) 3 alakú prímszám. Ez a kérdés minden bizonnyal épp olyan nehéz, mint hogy van-e végtelen sok 2^n–1 2 n 1 alakú, ún. Mersenne-prím. Az utóbbi probléma pedig több száz éve megoldatlan.

Az alábbi táblázatban a bekeretezett (nem áthúzott) számok sokáig prímeknek bizonyulnak:

De mégsem lesz mindegyikük prím. A k

k -adik bekeretezett szám ugyanis 17+(1+2+…+k)⋅2=k^2+k+17 17 + ( 1 + 2 + + k ) 2 = k 2 + k + 17 , és ez biztosan összetett k=16 k = 16 -ra, hiszen ekkor k^2+k+17=k(k+1)+17=17^2 k 2 + k + 17 = k ( k + 1 ) + 17 = 17 2 . Meglepő módon a k^2+k+17 k 2 + k + 17 képlet a k=0 k = 0 , 1, …, 15 helyettesítési értékek mindegyikére prímet ad.

Ha meg akarjuk keresni azokat a p

p pozitív egészeket, amelyekre k^2+k+p k 2 + k + p prímszám a k=0 k = 0 , 1, …, p–2 p 2 értékek mindegyikére, akkor a következőképpen okoskodhatunk. Először is (k=0 k = 0 -t véve) p p prímszám kell, hogy legyen. Ha pg3 p g 3 , akkor az 1^2+1+p 1 2 + 1 + p és 2^2+2+p 2 2 + 2 + p számok nem lehetnek sem 3-mal, sem 5-tel oszthatók, így p p 3-mal osztva 2-t, 5-tel osztva pedig 1-et vagy 2-t ad maradékul. Mivel p p páratlan is, ezért a 30-cal való osztási maradéka csak 11 vagy 17 lehet. Egy további feltétel, hogy 4p–1 4 p 1 -nek is prímnek kell lennie. Tegyük fel ugyanis, hogy d∣4p–1 d 4 p 1 és 1ldl4p–1 1 l d l 4 p 1 . Ekkor d≤(4p–1)∕3 d ( 4 p 1 ) 3 és d=2x+1 d = 2 x + 1 , ahol tehát

xl(d/2)≤(4p–1/6)≤p–2,
x l d 2 4 p 1 6 p 2 ,

ha pg5

p g 5 . Így x^2+x+p x 2 + x + p -nek prímnek kell lennie. Azonban d d osztója 4(x^2+x+p)=(2x+1)^2+4p–1=d^2+(4p–1) 4 ( x 2 + x + p ) = ( 2 x + 1 ) 2 + 4 p 1 = d 2 + ( 4 p 1 ) -nek, tehát x^2+x+p x 2 + x + p -nek is, hiszen páratlan. Ez csak úgy lehetséges, ha d=2x+1=x^2+x+pgx^2+x+2 d = 2 x + 1 = x 2 + x + p g x 2 + x + 2 , x^2–x+1l0 x 2 x + 1 l 0 , ami lehetetlen.

Azt kaptuk tehát, hogy vagy p=2

p = 2 , 3, 5, vagy pedig p p olyan 30k+11 30 k + 11 vagy 30k+17 30 k + 17 alakú prímszám, amelyre 4p–1 4 p 1 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 p=2 p = 2 , 3, 5, 11, 17, 41 számokra valóban teljesül, hogy k^2+k+p k 2 + k + p prímszám a k=0 k = 0 , 1, …, p–2 p 2 értékek mindegyikére. A 71-re ez már nem igaz, mert 2^2+2+71=77 2 2 + 2 + 71 = 77 ö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 p(x)=c_kx^k+c_(k–1)x^(k–1)+…+c_0

p ( x ) = c k x k + c k 1 x k 1 + + c 0 egész együtthatós polinom, akkor a≡b(mod m) a b ( mod m ) esetén p(a)≡p(b)(mod m) p ( a ) p ( b ) ( mod m ) . Valóban,

(1)

p(b)–p(a)=c_k(b^k–a^k)+c_(k–1)(b^(k–1)–a^(k–1))+…+c_1(b–a).
p ( b ) p ( a ) = c k ( b k a k ) + c k 1 ( b k 1 a k 1 ) + + c 1 ( b a ) .

Itt   b^i–a^i

b i a i -ből   (b–a) ( b a ) kiemelhető: b^i–a^i=(b–a)(b^(i–1)+b^(i–2)a+…+ba^(i–2)+a^(i–1)) b i a i = ( b a ) ( b i 1 + b i 2 a + + b a i 2 + a i 1 ) . Ha (1) jobb oldalának minden tagjából kiemeljük b–a b a -t, akkor azt kapjuk, hogy p(b)–p(a)=(b–a)⋅A p ( b ) p ( a ) = ( b a ) A , ahol A A egész szám, hiszen a a , b b , c_0 c 0 , …, c_k c k mindannyian egészek. Így p(b)–p(a) p ( b ) p ( a ) osztható b–a b a -val. Ha a≡b(mod m) a b ( mod m ) , akkor m m osztója b–a b a -nak, tehát p(b)–p(a) p ( b ) p ( a ) -nak is, azaz p(a)≡p(b)(mod m) p ( a ) p ( b ) ( mod m ) .

A másik állítás, amelyre szükségünk van, az, hogy ha a

p(x)=c_kx^k+c_(k–1)x^(k–1)+…+c_0
p ( x ) = c k x k + c k 1 x k 1 + + c 0

polinom nem konstans és a főegyütthatója pozitív, akkor p(x)

p ( x ) minden előre megadott számnál nagyobb lesz, ha x x elég nagy. Ezt így láthatjuk be: Jelöljük a ∣c_(k–1)∣+…+∣c_1∣+∣c_0∣ c k 1 + + c 1 + c 0 számot c c -vel. Ha xg1 x g 1 , akkor 1lxlx^2l…lx^(k–1) 1 l x l x 2 l l x k 1 , tehát

p(x)≥c_kx^k–∣c_(k–1)∣x^(k–1)–…–∣c_1∣x–∣c_0∣≥ ≥c_kx^k–∣c_(k–1)∣x^(k–1)–…–∣c_1∣x^(k–1)–∣c_0∣x^(k–1)= =c_kx^k–cx^(k–1)=x^(k–1)(c_kx–c).
p ( x ) c k x k c k 1 x k 1 c 1 x c 0 c k x k c k 1 x k 1 c 1 x k 1 c 0 x k 1 = = c k x k c x k 1 = x k 1 ( c k x c ) .

Ha xgc∕c_k

x g c c k , akkor c_kx–cg0 c k x c g 0 , tehát xg1 x g 1 alapján p(x)gc_kx–c. p ( x ) g c k x c . Ha tehát azt akarjuk, hogy p(x) p ( x ) nagyobb legyen egy előre megadott Kg0 K g 0 számnál, akkor x x -et elég úgy választani, hogy nagyobb legyen 1 és (c+K)∕c_k ( c + K ) c k mindegyikénél. Ekkor ugyanis a fentiek szerint p(x)gc_kx–cgK p ( x ) g c k x c g K teljesülni fog.

Világos, hogy ha p

p nem konstans, és a főegyütthatója negatív, akkor p(x) p ( x ) minden előre magadott számnál kisebb lesz, ha x x elég nagy.

Most már könnyen beláthatjuk, hogy ha az egész együtthatós p(x)

p ( x ) polinom nem konstans, akkor a p(n) p ( n ) értékek nem lehetnek mind prímek. Válasszunk ugyanis egy olyan n_0 n 0 pozitív egészet, amelyre ∣p(n_0)∣=mg1 p ( n 0 ) = m g 1 . Ha n=n_0+i⋅m n = n 0 + i m (i=1 i = 1 , 2, …), akkor n≡n_0(mod m) n n 0 ( mod m ) , tehát p(n)≡p(n_0)=±m≡0(mod m) p ( n ) p ( n 0 ) = ± m 0 ( mod m ) , azaz p(n) p ( n ) osztható m m -mel. De tudjuk, hogy ∣p(x)∣gm p ( x ) g m , ha x x elég nagy; mondjuk, ha xgx_0 x g x 0 . Ekkor minden elég nagy i i -re n=n_0+i⋅mgx_0 n = n 0 + i m g x 0 , így ∣p(n)∣gm p ( n ) g m és p(n) p ( n ) osztható m m -mel, tehát p(n) p ( n ) ö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 p

p prím és n n nem osztható p p -vel, akkor n^(p–1)≡1 n p 1 1 (mod p) ( mod p ) . Ezt így láthatjuk be:

Az n

n , 2n 2 n , …, (p–1)n ( p 1 ) n számok csupa különböző maradékot adnak p p -vel osztva. Valóban, ha in≡jn(mod p) i n j n ( mod p ) , akkor p∣in–jn=(i–j)n p i n j n = ( i j ) n . Mivel p p prím és n n nem osztható p p -vel, ebből következik, hogy p∣i–j p i j . Ha tehát 1≤i 1 i , j≤p–1 j p 1 , akkor szükségképpen i=j i = j .

Mivel az n

n , 2n 2 n , …, (p–1)n ( p 1 ) n számok egyike sem osztható p p -vel, ebből következik, hogy a p p -vel vett osztási maradékaik az 1, 2, …, p–1 p 1 számok (esetleg más sorrendben). Így n⋅2n⋯(p–1)n≡1⋅2⋯(p–1)(mod p) n 2 n ( p 1 ) n 1 2 ( p 1 ) ( mod p ) , azaz n^(p–1)(p–1)!≡(p–1)!(mod p) n p 1 ( p 1 ) ! ( p 1 ) ! ( mod p ) . Ezért p∣(n^(p–1)–1)(p–1)! p n p 1 1 ( p 1 ) ! , tehát p∣(n^(p–1)–1) p n p 1 1 , hiszen p p nem osztója (p–1)! ( p 1 ) ! -nak.

Ennek felhasználásával lássuk be például, hogy az f(n)=22^n+18^n+1

f ( n ) = 22 n + 18 n + 1 képlet nem szolgáltathat csupa prímet. Az f(1)=41 f ( 1 ) = 41 érték mindenesetre prím, ezért 22^(40)≡1(mod 41) 22 40 1 ( mod 41 ) és 18^(40)≡1 18 40 1 (mod 41) ( mod 41 ) . Ebből következik, hogy 22^(40k)≡1(mod 41) 22 40 k 1 ( mod 41 ) és 18^(40k)≡1(mod 41) 18 40 k 1 ( mod 41 ) minden k k pozitív egészre. Ha tehát n=40k+1 n = 40 k + 1 , akkor

22^n+18^n+1=22^(40k+1)+18^(40k+1)+1= =22⋅22^(40k)+18⋅18^(40k)+1≡22+18+1=41≡0 (mod 41),
22 n + 18 n + 1 = 22 40 k + 1 + 18 40 k + 1 + 1 = = 22 22 40 k + 18 18 40 k + 1 22 + 18 + 1 = 41 0 ( mod 41 ) ,

és így f(40k+1)

f ( 40 k + 1 ) nem lehet prím, ha kg0 k g 0 .

Most bizonyítsuk be, hogy az

f(n)=100(n^2+n)^(n^3+n^2+2n)+1
f ( n ) = 100 ( n 2 + n ) n 3 + n 2 + 2 n + 1

képlet sem szolgáltathat csupa prímet! (Ez kicsit nehezebb lesz.) Először is válasszunk egy olyan n_0

n 0 pozitív egészet, amelyre p=f(n_0)gn_0^2+n_0 p = f ( n 0 ) g n 0 2 + n 0 . Ilyen például n_0=1 n 0 = 1 , amikor is p=1601g2 p = 1601 g 2 . Ha p p összetett szám, akkor máris beláttuk, hogy f f értékei a pozitív egészekben nem mind prímek. Ha p p prím (mint az adott esetben is), akkor tekintsük az n=n_0+ip(p–1) n = n 0 + i p ( p 1 ) alakú számokat, ahol i=1 i = 1 , 2, …. Belátjuk, hogy ezekre az n n -ekre f(n) f ( n ) mindig osztható p p -vel. Valóban, rögzítsünk egy ilyen n n -et, és tekintsük a q(x)=100x^(n^3+n^2+2n)+1 q ( x ) = 100 x n 3 + n 2 + 2 n + 1 polinomot! Tudjuk, hogy ha a≡b(mod m) a b ( mod m ) , akkor q(a)≡q(b)(mod m) q ( a ) q ( b ) ( mod m ) . Mivel n≡n_0(mod p) n n 0 ( mod p ) , ezért q(n)≡q(n_0)(mod p) q ( n ) q ( n 0 ) ( mod p ) , azaz

(2)

f(n)=100(n^2+n)^(n^3+n^2+2n)+ +1≡100(n_0^2+n_0)^(n^3+n^2+2n)+1 (mod p).
f ( n ) = 100 ( n 2 + n ) n 3 + n 2 + 2 n + + 1 100 ( n 0 2 + n 0 ) n 3 + n 2 + 2 n + 1 ( mod p ) .

Ugyanígy, felhasználva, hogy n≡n_0(mod p–1)

n n 0 ( mod p 1 ) , azt kapjuk, hogy n^3+n^2+2n≡n_0^3+n_0^2+2n_0(mod p–1) n 3 + n 2 + 2 n n 0 3 + n 0 2 + 2 n 0 ( mod p 1 ) , tehát n^3+n^2+2n=n_0^3+n_0^2+2n_0+c(p–1) n 3 + n 2 + 2 n = n 0 3 + n 0 2 + 2 n 0 + c ( p 1 ) , ahol c c pozitív egész. Ezt (2)-be helyettesítve azt kapjuk, hogy

(3)

f(n) ≡100(n_0^2+n_0)^(n_0^3+n_0^2+2n_0+c(p–1))+1≡ ≡100(n_0^2+n_0)^(n_0^3+n_0^2+2n_0)⋅(n_0^2+n_0)^(c(p–1))+1 (mod p).
f ( n ) 100 ( n 0 2 + n 0 ) n 0 3 + n 0 2 + 2 n 0 + c ( p 1 ) + 1 100 ( n 0 2 + n 0 ) n 0 3 + n 0 2 + 2 n 0 ( n 0 2 + n 0 ) c ( p 1 ) + 1 ( mod p ) .

Mivel 1≤n_0^2+n_0lp

1 n 0 2 + n 0 l p , ezért a kis Fermat-tétel szerint (n_0^2+n_0)^((p–1))≡1(mod p) ( n 0 2 + n 0 ) ( p 1 ) 1 ( mod p ) , és így, tekintve, hogy c c pozitív egész, azt kapjuk, hogy (n_0^2+n_0)^(c(p–1))≡1(mod p) ( n 0 2 + n 0 ) c ( p 1 ) 1 ( mod p ) . Ezt (3)-ba helyettesítve:

f(n)≡100(n_0^2+n_0)^(n_0^3+n_0^2+2n_0)+1=p≡0 (mod p),
f ( n ) 100 ( n 0 2 + n 0 ) n 0 3 + n 0 2 + 2 n 0 + 1 = p 0 ( mod p ) ,

tehát f(n)

f ( n ) valóban osztható p p -vel. Mivel f f szigorúan monoton növő, ezért ig0 i g 0 -ra n=n_0+ip(p–1)gn_0 n = n 0 + i p ( p 1 ) g n 0 -ból f(n)gf(n_0) f ( n ) g f ( n 0 ) következik, Ezért f(n) f ( n ) összetett szám lesz. Így például f f értéke az 1+1601⋅1600=2 561 601 1 + 1601 1600 = 2 561 601 helyen osztható 1601-gyel, és ezért összetett.

A következő általános tétel hasonló módszerrel bizonyítható. Legyen f(n)

f ( n ) olyan képlet, amely p(n)^(q(n)) p ( n ) q ( n ) alakú kifejezések szorzatainak összege, ahol p(n) p ( n ) és q(n) q ( n ) egész együtthatós polinomok, melyek közül a q(n) q ( n ) -ek főegyütthatói pozitívak. Ha az f(n) f ( n ) (n=1 n = 1 , 2, …) értékek között van végtelen sok különböző, akkor ezek között az é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 f(n)=18+(–1)^n

f ( n ) = 18 + ( 1 ) n képlet a fenti alakú és f f minden értéke prím.

⋆

A fenti tétel azt állítja, hogy ha f(n)

f ( n ) csupa prímszámot ad minden n n pozitív egészre, akkor az f f -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 n n változót. A legegyszerűbb ilyen képlet: 2^(2^n) 2 2 n . Ez persze ng0 n g 0 -ra nem ad prímeket, mert mindig páros. De mi a helyzet a 2^(2^n)+1 2 2 n + 1 képlettel? Az n=0 n = 0 , 1, 2, 3, 4 számokat behelyettesítve a 3, 5, 17, 257, 65 537 65 537 értékeket kapjuk; mindnyájan prímek. Ennek alapján Pierre de Fermat azt sejtette (1640 körül), hogy F_n=2^(2^n)+1 F n = 2 2 n + 1 minden n n -re prímszám. Ez a sejtés csaknem 100 éven át megoldatlan maradt, mert a következő szám:

F_5=2^(2^5)+1=4 294 967 297
F 5 = 2 2 5 + 1 = 4 294 967 297

már olyan nagy, hogy annak eldöntése, hogy prím-e vagy sem, reménytelennek látszott. Valóban, gondoljunk csak bele: ha sem kalkulátor, sem számítógép nem állna rendelkezésünkre, el tudnánk-e dönteni, hogy F_5

F 5 prím-e? Volna-e jobb ötletünk, mint elosztani F_5 F 5 -öt minden nála kisebb számmal? Persze elég volna csupán a √(F_5) F 5 -nél nem nagyobb számokkal osztani, hiszen ha egy n n szám összetett, akkor van olyan d d osztója, amelyre 1ld≤√n 1 l d n . Az adott esetben tehát csak a 65 536 65 536 -nál nem nagyobb számokkal kellene osztani; sőt, ezek közül elég lenne a prímeket venni, melyek száma kb. 6500. Ha minden osztás két percet vesz igénybe, még ez is 200 óra munka volna; nem csoda, ha olyan sokáig senki nem vállalkozott rá.

Végül is Leonhard Euler volt az, aki 1732-ben a kérdést eldöntötte. Euler felismerte, hogy F_n

F n prímosztói csak speciális alakúak lehetnek, nevezetesen F_n F n minden prímosztója k⋅2^(n+1)+1 k 2 n + 1 + 1 alakú, ahol k k pozitív egész. Ezt a következőképpen láthatjuk be. Legyen p p egy prímosztója F_n F n -nek. Mivel p p páratlan, ezért a kis Fermat-tétel szerint 2^(p–1)≡1(mod p) 2 p 1 1 ( mod p ) . Legyen d d a legkisebb pozitív egész, amelyre 2^d≡1(mod p) 2 d 1 ( mod p ) . Ekkor a 2-hatványok p p -vel való osztási maradékai d d szerint periodikus sorozatot alkotnak. Valóban, 2^d≡1=2^0 2 d 1 = 2 0 alapján 2^(d+1)≡2=2^1 2 d + 1 2 = 2 1 , 2^(d+2)≡2⋅2^1=2^2 2 d + 2 2 2 1 = 2 2 , 2^(d+3)≡2⋅2^2=2^3 2 d + 3 2 2 2 = 2 3 , és hasonlóan, 2^(d+i)≡2^i 2 d + i 2 i minden i i -re (a kongruenciákat (mod p p ) értve). Ebből következik, hogy 2^(s⋅d)≡1 2 s d 1 minden s=1 s = 1 , 2, …-re. Másrészt d d választása folytán 2^i≢1 2 i 1 ha 0lild 0 l i l d , ezért a periodicitásból következik, hogy 2^m 2 m akkor és csak akkor ad 1 maradékot p p -vel osztva, ha m m osztható d d -vel.

Mármost 2^(2^(n+1))≡1(mod p)

2 2 n + 1 1 ( mod p ) , ugyanis 2^(2^(n+1))–1=(2^(2^n)+1)⋅(2^(2^n)–1) 2 2 n + 1 1 = 2 2 n + 1 2 2 n 1 , tehát 2^(2^(n+1))–1 2 2 n + 1 1 osztható F_n F n -nel, tehát p p -vel is. A fentiek szerint ebből következik, hogy d ∣ 2^(n+1) d 2 n + 1 . Megmutatjuk, hogy szükségképpen d=2^(n+1) d = 2 n + 1 . Valóban, dl2^(n+1) d l 2 n + 1 esetén d d osztója lenne 2^n 2 n -nek is. Ebből viszont 2^(2^n)≡1 2 2 n 1 következne, holott 2^(2^n)=F_n–1≡–1(mod p) 2 2 n = F n 1 1 ( mod p ) , hiszen p ∣ F_n p F n . Ezzel beláttuk, hogy d=2^(n+1) d = 2 n + 1 . Mivel pedig 2^(p–1)≡1(mod p) 2 p 1 1 ( mod p ) , ezért 2^(n+1)=d ∣ p–1, 2 n + 1 = d p 1 , tehát p–1=k⋅2^(n+1), p 1 = k 2 n + 1 , azaz p=k⋅2^(n+1)+1, p = k 2 n + 1 + 1 , ahol k k pozitív egész.

Valójában Euler azt is belátta, hogy ha n≥2

n 2 és a p p prím osztója F_n F n -nek, akkor p=k⋅2^(n+2)+1, p = k 2 n + 2 + 1 , ahol k k pozitív egész. Meg lehet mutatni ugyanis, hogy ha a p p prím 8k+1 8 k + 1 alakú, akkor 2^((p–1)∕2)≡1(mod p) 2 ( p 1 ) 2 1 ( mod p ) . A fenti okoskodásban ezért 2^(n+1)=d ∣ (p–1)∕2, 2 n + 1 = d ( p 1 ) 2 , tehát (p–1)∕2=k⋅2^(n+1), ( p 1 ) 2 = k 2 n + 1 , azaz p=k⋅2^(n+2)+1, p = k 2 n + 2 + 1 , ahol k k pozitív egész.

Ezt n=5

n = 5 -re alkalmazva azt kapjuk, hogy F_5 F 5 minden prímosztója 2^7⋅k+1=128k+1 2 7 k + 1 = 128 k + 1 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 1, 3, …, 127 számokat), és azt várhatjuk, hogy a 65 536 65 536 -nál kisebb prímeknek durván 1∕64 1 64 -ed része lesz 128k+1 128 k + 1 alakú. Ez kb. 6500∕64l102 6500 64 l 102 prímet jelent. Ezért annak eldöntéséhez, hogy F_5 F 5 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ő 128k+1 128 k + 1 alakú prím, 257, ugyan nem osztója F_5 F 5 -nek, de a második, 641, már igen: F_5=4 294 967 297=641⋅6 700 417 F 5 = 4 294 967 297 = 641 6 700 417 . Ezzel Fermat sejtése megdőlt: az F_n=2^(2^n)+1 F n = 2 2 n + 1 képlet nem állít elő minden n n -re prímszámot.

Egyébként a következő Fermat-szám, F_6

F 6 prímtényezőkre bontását csak 1880-ban sikerült megtalálni: F_6=274 177⋅67 280 421 310 721 F 6 = 274 177 67 280 421 310 721 . Az ezt követő Fermat-szám, F_7 F 7 faktorizációját 1970-ben találták meg; eszerint F_7 F 7 egy 17-jegyű és egy 22-jegyű prím szorzata. Azóta kiderült, hogy F_n F n összetett szám minden 5≤n≤21 5 n 21 -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 n^2+n+17

n 2 + n + 17 , n^2+n+41 n 2 + n + 41 vagy a 2^(2^n)+1 2 2 n + 1 képletek esetében).

Eddig senki nem talált olyan képletet, amely egész számokból és az n

n 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 n n -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 x

x szám egészrészét megadó [x] [ x ] 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ő: [x] [ x ] az az egyértelműen meghatározott egész szám, amelyre [x]≤xl[x]+1 [ x ] x l [ x ] + 1 . Így pl. [3∕2]=1 [ 3 2 ] = 1 , [π]=3 [ π ] = 3 , [7]=7 [ 7 ] = 7 , [–4]=–4 [ 4 ] = 4 , [–3∕2]=–2 [ 3 2 ] = 2 , [–π]=–4 [ π ] = 4 .) Ezek felhasználásával már viszonylag egyszerű képletet adhatunk az n n -edik prímszámra, amelyet a következőkben p_n p n -nel fogunk jelölni. Megmutatjuk, hogy van olyan α α valós szám, amelyre

(4)

p_n=[10^(n^2)α]–10^(2n–1)[10^((n–1)^2)α] (n=1,2,…).
p n = 10 n 2 α 10 2 n 1 10 ( n 1 ) 2 α ( n = 1 , 2 , ) .

Képezzünk ugyanis a prímszámok p_n

p n sorozatából egy végtelen tizedestörtet a következőképpen! A tizedestört egészrésze 0 lesz. A tizedesvessző után írjuk le egymás után a prímszámokat, megfelelő számú 0-val elválasztva őket! Az elválasztó 0-k számát úgy választjuk meg, hogy p_n p n utolsó számjegye éppen a tizedesvessző utáni n^2 n 2 -edik helyre kerüljön. Tehát az 1., 4., 9., 16. jegy a 2-es, 3-as, 5-ös, 7-es lesz, a 24. és a 25. 1-es, a 35. ismét 1-es, a 36. 3-as stb. Legyen az így definiált végtelen tizedestört α α , tehát legyen

α=0,200 300 005 000 000 70…0110…0130….
α = 0,200 300 005 000 000 70 0110 0130 .

Ekkor A_n=[10^(n^2)α]

A n = 10 n 2 α az az egész szám, amelynek a jegyeit az α α -nak a tizedesvessző utáni első n^2 n 2 jegye adja. A konstrukcióból adódik, hogy A_n A n olyan n^2 n 2 -jegyű szám, amely éppen p_n p n jegyeivel végződik. Nyilvánvaló, hogy az A_n A n első (n–1)^2 ( n 1 ) 2 jegyéből képzett szám A_(n–1)=[10^((n–1)^2)α] A n 1 = 10 ( n 1 ) 2 α lesz. Ha tehát A_(n–1) A n 1 -et kiegészítjük n^2–(n–1)^2=2n–1 n 2 ( n 1 ) 2 = 2 n 1 darab 0-val, azaz megszorozzuk 10^(2n–1) 10 2 n 1 -gyel, és az így kapott számot kivonjuk A_n A n -ből, akkor éppen p_n p n -et kapjuk. Ezzel (4)-et beláttuk.

A fenti konstrukcióban hallgatólagosan felhasználtuk, hogy p_n

p n jegyeinek száma legfeljebb n^2–(n–1)^2=2n–1 n 2 ( n 1 ) 2 = 2 n 1 , mert különben p_n p n „nem férne el”. Megmutatjuk, hogy p_n p n jegyeinek száma legfeljebb n n .

Nevezzünk egy m

m számot négyzetmentesnek, ha nem osztható 1-nél nagyobb négyzetszámmal. Ez azzal ekvivalens, hogy az m m prímtényezős felbontásában minden prím első hatványon szerepel; azaz, hogy m m különböző prímek szorzata. Bármely k k egész szám előáll mint egy négyzetszám és egy négyzetmentes szám szorzata. Ha ugyanis k k -t elosztjuk azzal a legnagyobb osztójával, amely négyzetszám, akkor a hányados nyilván négyzetmentes lesz. (Ha k k négyzetmentes, akkor 1-gyel osztunk.)

Írjuk fel a p_n

p n -nél nem nagyobb számokat b^2c b 2 c alakban, ahol c c négyzetmentes. Itt b^2≤p_n b 2 p n , tehát b≤√(p_n) b p n . A c c szám különböző prímek szorzata, melyek mindegyike legfeljebb p_n p n , hiszen c≤p_n c p n . Ezért c c -t úgy kapjuk, hogy a p_1 p 1 , p_2 p 2 , …, p_n p n prímek közül néhányat összeszorzunk. Ezt 2^n 2 n -féleképpen tehetjük meg (annyiféleképpen, ahány részhalmaza van a {p_1,p_2,…,p_n} { p 1 , p 2 , , p n } halmaznak). A b b számot tehát legfeljebb √(p_n) p n -féleképpen, a c c számot pedig legfeljebb 2^n 2 n -féleképpen választhatjuk meg. Mivel b^2c b 2 c alakban minden, p_n p n -nél nem nagyobb szám előáll, ebből következik, hogy p_n≤√(p_n)⋅2^n p n p n 2 n , √(p_n)≤2^n p n 2 n , és így p_n≤4^n p n 4 n . Mivel 4^nl10^n 4 n l 10 n , ezért p_n p n legfeljebb n n -jegyű.

Ez a becslés lényegesen javítható: valójában p_n

p n jegyeinek száma alig nagyobb n n jegyeinek számánál. Így pl. p_(100)=541 p 100 = 541 , p_(1000)=7919 p 1000 = 7919 , p_(10 000)=104 729 p 10 000 = 104 729 , p_(10^(10)) p 10 10 11-jegyű, p_(10^(100)) p 10 100 pedig 102-jegyű. Az utóbbi két állítás abból következik, hogy

n(logn+loglogn–1,5)lp_nln(logn+loglogn+8), valamint   nlognlp_n
n ( log n + log log n 1,5 ) l p n l n ( log n + log log n + 8 ) , valamint    n log n l p n

minden n≥2

n 2 -re. E képletekben logn log n az ún. természetes vagy e e alapú logaritmus, amelynek alapja

e=lim_(n→∞)(1+(1/n))^n=2,718 28….
e = lim n 1 + 1 n n = 2,718 28 .

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 p_n

p n é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 cg1 c g 1 valós szám úgy, hogy [c^(3^n)] c 3 n prímszám lesz n n minden pozitív egész értékére. Ennek a képletnek ugyanaz a baja, mint (4)-nek: c c 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 [x]

[ x ] (egészrész), {x}=x–[x] { x } = x [ x ] (törtrész) függvényeket, valamint a

∑_(i=k)^na_i=a_k+a_(k+1)+…+a_n és ∏_(i=k)^na_i=a_k⋅a_(k+1)⋅…⋅a_n
i = k n a i = a k + a k + 1 + + a n és i = k n a i = a k a k + 1 a n

jelöléseket, akkor szintén kaphatunk képleteket p_n

p n -re. Jelöljük π(x) π ( x ) -szel az x x számnál nem nagyobb prímek számát. Először π(x) π ( x ) -re adunk képletet.

Ha az ng2

n g 2 szám prím, akkor az (n/2) n 2 , (n/3) n 3 , …, (n/n–1) n n 1 számok egyike sem egész, tehát az {(n/2)},{(n/3)},…,{(n/n–1)} n 2 , n 3 , , n n 1 törtrészek egyike sem 0. Ekkor tehát a ∏_(i=2)^(n–1)[–{(n/i)}] i = 2 n 1 n i szorzat minden tényezője –1 1 (mert egy –1 1 és 0 közé eső szám egészrésze). A szorzat értéke tehát –1 1 , hiszen a tényezők száma n–2 n 2 , ami páratlan. Ha viszont n n összetett, akkor n∕i n i egész szám lesz legalább egy 2≤i≤n–1 2 i n 1 -re, és ekkor [–{(n/i)}]=[–0]=0 n i = [ 0 ] = 0 alapján a fenti szorzat értéke 0. Így x≥3 x 3 esetén a

–∑_(n=3)^x∏_(i=2)^(n–1)[–{(n/i)}]
n = 3 x i = 2 n 1 n i

képlet értéke π(x)–1

π ( x ) 1 , hiszen a szumma n n -edik tagja –1 1 , ha n n prím, és 0, ha n n összetett. (π(x) π ( x ) -ből azért kell 1-et levonni, mert a 2-t kizártuk a szummából.) Azt kaptuk tehát, hogy

(5)

π(x)=1–∑_(n=3)^x∏_(i=2)^(n–1)[–{(n/i)}] (x=3,4,…).
π ( x ) = 1 n = 3 x i = 2 n 1 n i ( x = 3 , 4 , ) .

Valamivel egyszerűbb képletet is kaphatunk π(x)

π ( x ) -re az ún. Wilson-tétel felhasználásával. Ez azt állítja, hogy ha p p prím, akkor (p–1)!≡–1(mod p) ( p 1 ) ! 1 ( mod p ) .

Ezt így láthatjuk be: Az állítás p=2

p = 2 , 3-ra nyilvánvaló, tehát feltehetjük, hogy p≥5 p 5 . A kis Fermat-tétel bizonyításakor megmutattuk, hogy ha n n nem osztható p p -vel, akkor az n n , 2n 2 n , …, (p–1)n ( p 1 ) n számok p p -vel vett osztási maradékai az 1, 2, …, p–1 p 1 számok (esetleg más sorrendben). Ebből következik, hogy az 1, 2, …, p–1 p 1 számok között pontosan egy olyan i i szám van, amelyre n⋅i≡1(mod p) n i 1 ( mod p ) . Nevezzük ezt a számot n n reciprokának (mod p p ). Ha n≢m(mod p) n m ( mod p ) , akkor n n és m m reciprokai különbözők. Valóban, n⋅i≡m⋅i≡1 n i m i 1 -ből következik, hogy p∣ni–mi=(n–m)i p n i m i = ( n m ) i , tehát p∣n–m p n m , hiszen 1≤i≤p–1 1 i p 1 . Ha egy 1≤n≤p–1 1 n p 1 szám reciproka önmaga, akkor n^2≡1 n 2 1 , p∣n^2–1=(n–1)(n+1) p n 2 1 = ( n 1 ) ( n + 1 ) , tehát n=1 n = 1 vagy n=p–1 n = p 1 .

A fentiekből következik, hogy a 2, 3, …, p–2

p 2 számok mindegyikét a reciprokával párosítva diszjunkt párokat kapunk. Mivel az egy párhoz tartozó számok szorzata p p -vel osztva 1-et ad maradékul, ezért 2⋅3⋯(p–2)≡1(mod p) 2 3 ( p 2 ) 1 ( mod p ) , tehát (p–1)!≡–1(mod p) ( p 1 ) ! 1 ( mod p ) .

A Wilson-tétel megfordítható: ha ng1

n g 1 osztója (n–1)!+1 ( n 1 ) ! + 1 -nek, akkor n n prím. Valóban, ha 1ldln 1 l d l n , akkor d ∣ (n–1)! d ( n 1 ) ! . Ha d d osztója volna n n -nek, akkor n ∣ (n–1)!+1 n ( n 1 ) ! + 1 alapján d d is osztója volna (n–1)!+1 ( n 1 ) ! + 1 -nek, ami lehetetlen. Így n n nem osztható a 2, …, n–1 n 1 számok egyikével sem, tehát prím. Összefoglalva: az ((n–1)!+1)∕n ( ( n 1 ) ! + 1 ) n tört akkor és csak akkor egész, ha n=1 n = 1 vagy n n prím. Ebből következik, hogy

∑_(n=1)^x[–{((n–1)!+1/n)}]=–(x–π(x)–1),
n = 1 x ( n 1 ) ! + 1 n = x π ( x ) 1 ,

hiszen összetett n

n -re a szumma n n -edik tagja –1 1 , míg prím n n -re és n=1 n = 1 -re 0. Ebből azt kapjuk, hogy

(6)

π(x)=x–1+∑_(n=1)^x[–{((n–1)!+1/n)}] (x=1,2,…).
π ( x ) = x 1 + n = 1 x ( n 1 ) ! + 1 n ( x = 1 , 2 , ) .

Az (5) és (6) képletek mindegyikét felhasználhatjuk p_n

p n kifejezésére. Jelöljük φ φ -vel azt a függvényt, amelyre

φ(x)={1, ha x=0,1,2,… / 0, ha x=–1,–2,….
φ ( x ) = 1 , ha  x = 0 , 1 , 2 , 0 , ha  x = 1 , 2 , .

(A φ

φ függvényt csak az egész számokban értelmezzük.) A φ φ függvényre könnyen adhatunk képletet, pl. φ(x)=1+[(1/3x+2)] φ ( x ) = 1 + 1 3 x + 2 minden x x egész számra. Mármost k≤p_n k p n esetén π(k)≤n π ( k ) n , tehát φ(n–π(k))=1 φ ( n π ( k ) ) = 1 , míg kgp_n k g p n esetén π(k)gn π ( k ) g n , tehát φ(n–π(k))=0 φ ( n π ( k ) ) = 0 . Ebből következik, hogy

p_n=∑_(k=1)^(4^n)φ(n–π(k)).
p n = k = 1 4 n φ ( n π ( k ) ) .

Valóban, a szumma tagjainak értéke k=1

k = 1 , …, p_n p n esetén 1, egyébként pedig  0. Mivel p_n≤4^n p n 4 n , ezért a szumma értéke p_n p n . Ha ebben a formulában φ(x) φ ( x ) helyébe 1+[1∕(3x+2)] 1 + [ 1 ( 3 x + 2 ) ] -t írunk, π(x) π ( x ) -et pedig (6)-tal helyettesítjük, akkor a következő képletet kapjuk p_n p n -re:

p_n=4^n+∑_(k=1)^(4^n)[(1/3n–3k+5–3∑_(i=1)^k[–{((i–1)!+1/i)}])] (n=1,2,…).
p n = 4 n + k = 1 4 n 1 3 n 3 k + 5 3 i = 1 k ( i 1 ) ! + 1 i ( n = 1 , 2 , ) .

(Itt (6) helyett (5)-öt is alkalmazhatjuk, de ekkor apró módosítás szükséges, tekintve, hogy (5) csak x≥3

x 3 -ra érvényes.)

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, [x]

[ x ] , √x x és maximum szerepel. Ennek 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

(7)

x^2–2y^2=1, x^2–60y^2=1, x^2–61y^2=1,
x 2 2 y 2 = 1 , x 2 60 y 2 = 1 , x 2 61 y 2 = 1 ,

vagy

(8)

x^3+y^3=u^3+v^3, x^4+y^4=u^4+v^4, x^5+y^5=u^5+v^5.
x 3 + y 3 = u 3 + v 3 , x 4 + y 4 = u 4 + v 4 , x 5 + y 5 = u 5 + v 5 .

A (7) alatt felsorolt három egyenlet mindegyikének megoldása x=1

x = 1 , y=0; y = 0 ; ezeket triviális megoldásnak hívjuk. Nemtriviális megoldások is léteznek: az első egyenlet legkisebb pozitív egész megoldása x=3 x = 3 , y=2 y = 2 , a másodiké pedig x=31 x = 31 , y=4 y = 4 . A harmadiké viszont x=1 766 319 049 x = 1 766 319 049 , y=226 153 980 y = 226 153 980 .

A (8) alatt felsorolt egyenletek triviális megoldásai azok, amelyekre x=u

x = u , y=v y = v vagy x=v x = v , y=u y = u . Az első két egyenletnek vannak nem-triviális megoldásai is, pl. 9^3+10^3=1^3+12^3 9 3 + 10 3 = 1 3 + 12 3 , illetve 133^4+134^4=59^4+158^4 133 4 + 134 4 = 59 4 + 158 4 . 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 fel 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 n

n 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 nem kapunk. Ha ez a szám 1, akkor n n 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 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 n

n számról úgy találja, hogy igen, akkor n n -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 n n szám tagja-e a sorozatnak. Indítsuk el a nyomtatóprogramot, és várjunk addig, amíg egy n n -nél nagyobb szám megjelenik. Ha az eddig kinyomtatott számok között n n 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 n

n szám megjelenik a kinyomtatott számok között, akkor tagja a sorozatnak. Ha viszont n n nem tagja a sorozatnak, akkor ezt esetleg soha nem tudjuk meg, hiszen soha nem lehetünk biztosak abban, hogy n n 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) P(x_1,x_2,…,x_k)=0

P ( x 1 , x 2 , , x k ) = 0 , ahol P(x_1,x_2,…,x_k) P ( x 1 , x 2 , , x k ) egész együtthatós polinom; azaz olyan kifejezés, amely az x_1 x 1 , …, x_k x k 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 P(x_1,…,x_k,x_(k+1)) P ( x 1 , , x k , x k + 1 ) polinom a következő tulajdonsággal: egy y y természetes szám akkor és csak akkor tagja a sorozatnak, ha a P(x_1,…,x_k,y)=0 P ( x 1 , , x k , y ) = 0 diofantikus egyenletnek van megoldása a természetes számok körében, azaz ha vannak x_1,…,x_k x 1 , , x k természetes számok úgy, hogy P(x_1,…,x_k,y)=0 P ( x 1 , , x k , y ) = 0 . Ekkor azt mondjuk, hogy a sorozatot a P(x_1,…,x_k,x_(k+1)) P ( x 1 , , x k , x k + 1 ) polinom generálja. A négyzetszámok sorozata például diofantikus, mert egy y y szám akkor és csak akkor négyzetszám, ha az x^2–y=0 x 2 y = 0 (egyváltozós) egyenlet megoldható a természetes számok körében. Tehát a négyzetszámok sorozatát az x_1^2–x_2 x 1 2 x 2 polinom generálja.

Nem nehéz belátni, hogy minden diofantikus sorozat rekurzíve felsorolható. Tegyük fel ugyanis, hogy a sorozatot a P(x_1,…,x_k,x_(k+1))

P ( x 1 , , x k , x k + 1 ) polinom generálja. A rövidség kedvéért nevezzük vektornak a természetes számokből álló k+1 k + 1 -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 (0,…,0) ( 0 , , 0 ) vektort, majd azokat, amelyekben x_1+…+x_(k+1)=1 x 1 + + x k + 1 = 1 (ezekből k+1 k + 1 van), majd azok jönnek, amelyekben x_1+…+x_(k+1)=2 x 1 + + x k + 1 = 2 , és így tovább. Minden egyes (x_1,…,x_(k+1)) ( x 1 , , x k + 1 ) vektorra számítsuk ki a P(x_1,…,x_k,x_(k+1)) P ( x 1 , , x k , x k + 1 ) értéket! Ha ez nulla, akkor nyomtassuk ki x_(k+1) x k + 1 -et! Ha nem nulla, akkor ugorjunk át a következő vektorra! Nyilvánvaló, hogy ilyen módon éppen azokat az y y számokat nyomtattuk ki, amelyekre a P(x_1,…,x_k,y)=0 P ( x 1 , , x k , y ) = 0 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ő:

rekurzív⇒rekurzíve felsorolható⇔diofantikus.
rekurzív rekurzíve felsorolható diofantikus.

Ebből pedig már következik, hogy nincs olyan algoritmus, amely bármely megadott diofantikus egyenletről el tudná dönteni, hogy van-e megoldása. Vegyünk ugyanis egy olyan sorozatot, amely rekurzíve felsorolható, de nem rekurzív. Mivel ez a sorozat szükségképpen diofantikus, létezik egy P(x_1,…,x_k,x_(k+1))

P ( x 1 , , x k , x k + 1 ) polinom, amely generálja. Ha létezne olyan algoritmus, amely bármely diofantikus egyenletről el tudja dönteni, hogy van-e megoldása, akkor minden y y -ról eldönthetnénk, hogy tagja-e a sorozatnak vagy sem, hiszen a P(x_1,…,x_k,y)=0 P ( x 1 , , x k , y ) = 0 diofantikus egyenletet az állítólagos algoritmussal megvizsgálva megállapíthatnánk, hogy megoldható-e vagy sem. Ez azonban lehetetlen, mert akkor a sorozatunk rekurzív lenne, holott olyan sorozatból indultunk ki, ami nem az.

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 P(x_1,…,x_k,x_(k+1))

P ( x 1 , , x k , x k + 1 ) polinom, amely a prímszámok sorozatát generálja. Képezzük a

Q(x_1,…,x_k,x_(k+1))=x_(k+1)(1–2P^2(x_1,…,x_k,x_(k+1)))
Q ( x 1 , , x k , x k + 1 ) = x k + 1 1 2 P 2 ( x 1 , , x k , x k + 1 )

polinomot! Ha Q

Q -ban az x_1 x 1 , …, x_k x k , x_(k+1) x k + 1 változók helyére természetes számokat helyettesítünk, akkor két eset lehetséges.

(i) P(x_1,…,x_k,x_(k+1))=0

P ( x 1 , , x k , x k + 1 ) = 0 . Ekkor x_(k+1) x k + 1 prím (mert P P a prímeket generálja), és Q(x_1,…,x_k,x_(k+1))=x_(k+1) Q ( x 1 , , x k , x k + 1 ) = x k + 1 .

(ii) P(x_1,…,x_k,x_(k+1))≠0

P ( x 1 , , x k , x k + 1 ) 0 . Ekkor 1–2P^2(x_1,…,x_k,x_(k+1))≤1–2l0 1 2 P 2 ( x 1 , , x k , x k + 1 ) 1 2 l 0 és így

Q(x_1,…,x_k,x_(k+1))≤0.
Q ( x 1 , , x k , x k + 1 ) 0 .

Azt kaptuk tehát, hogy Q

Q -ba természetes számokat helyettesítve vagy prímet, vagy nempozitív számot kapunk. Másrészt így minden prímet megkapunk, mert ha p p prím, akkor P(x_1,…,x_k,p)=0 P ( x 1 , , x k , p ) = 0 alkalmas x_1 x 1 , …, x_k x k -ra, tehát Q(x_1,…,x_k,p)=p Q ( x 1 , , x k , p ) = p . A fentieket összefoglalva megállapíthatjuk, hogy a

(9)

max(Q(x_1,…,x_k,x_(k+1)),2)
max ( Q ( x 1 , , x k , x k + 1 ) , 2 )

kifejezés a változók nemnegatív egész értékeire mindig prímet ad, és minden prímet megad. Ilyen tulajdonságú Q

Q polinomok explicite is megadhatók; sajnos mindegyikük komplikált. Van közöttük 10-változós, ennek a foka azonban nagyobb 10^(45) 10 45 -nél. Van 5-ödfokú ilyen polinom is; ez azonban 42 változót tartalmaz. A jelenleg ismert legegyszerűbb egy 26-változós, 25-ödfokú polinom, amely kinyomtatva 9 sort foglal el a [3] könyv 115-116. oldalán.

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 x_i

x i változók helyébe egy-egy f_i(n) f i ( n ) függvényt. Az így kapott

(10)

max(Q(f_1(n),…,f_(k+1)(n)),2)
max ( Q ( f 1 ( n ) , , f k + 1 ( n ) ) , 2 )

képlet egyváltozós, és ha az f_i(n)

f i ( n ) érték nemnegatív egész minden i=1 i = 1 , …, k+1 k + 1 -re és n=0 n = 0 , 1, 2, …-re, akkor (10) minden n n -re prímet fog előállítani.

Látszólag készen vagyunk. Azonban a dolog mégsem ilyen egyszerű: ha pl. f_1

f 1 , …, f_(k+1) f k + 1 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 Q(f_1(n),…,f_(k+1)(n))=q(n) Q ( f 1 ( n ) , , f k + 1 ( n ) ) = q ( n ) is egész együtthatós polinom lesz. Ha q q konstans, akkor max(q(n),2) max ( q ( n ) , 2 ) is konstans. Ha q q nem konstans és a főegyütthatója negatív, akkor minden elég nagy n n -re q(n)l0 q ( n ) l 0 , tehát max(q(n),2)=2 max ( q ( n ) , 2 ) = 2 . Ha viszont q q nem konstans és a főegyütthatója pozitív, akkor minden elég nagy n n -re q(n)g2 q ( n ) g 2 , tehát max(q(n),2)=q(n) max ( q ( n ) , 2 ) = q ( n ) . Ez azt jelentené, hogy q(n) q ( n ) minden elég nagy n n -re prímszám, amiről már beláttuk, hogy lehetetlen (egy nem konstans egész együtthatós polinom az n n 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 Q(x_1,…,x_k,x_(k+1))

Q ( x 1 , , x k , x k + 1 ) 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 Q(f_1(n),…,f_(k+1)(n))=q(n) Q ( f 1 ( n ) , , f k + 1 ( n ) ) = q ( n ) polinom vagy konstans, vagy pedig negatív minden elég nagy n n -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 Q(x,y)=(x^2+1)(1–2(x^2–2y^2–1)^2) Q ( x , y ) = ( x 2 + 1 ) ( 1 2 ( x 2 2 y 2 1 ) 2 ) 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_1,…,f_(k+1)

f 1 , , f k + 1 függvényeket úgy megválasztani, hogy minden (a_1,…,a_(k+1)) ( a 1 , , a k + 1 ) vektor előálljon (f_1(n),…,f_(k+1)(n)) ( f 1 ( n ) , , f k + 1 ( n ) ) alakban. Ekkor (10) minden prímet elő fog állítani. Ha egy (a_1,…,a_(k+1)) ( a 1 , , a k + 1 ) vektorhoz létezik egy n n természetes szám, melyre f_1(n)=a_1,…,f_(k+1)(n)=a_(k+1), f 1 ( n ) = a 1 , , f k + 1 ( n ) = a k + 1 , akkor azt fogjuk mondani, hogy az f_1,…,f_(k+1) f 1 , , f k + 1 függvények kódolják az (a_1,…,a_(k+1)) ( a 1 , , a k + 1 ) 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_i f i 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 Q Q polinom a negatív egészekben felvehet pozitív összetett számot is, és akkor (10) értéke nem lesz minden n n -re prím. Ezen a következő módszerrel segíthetünk. Legyen m=4(k+1) m = 4 ( k + 1 ) , és tekintsük a

Q_1(y_1,…,y_m)= =Q(y_1^2+y_2^2+y_3^2+y_4^2,y_5^2+y_6^2+y_7^2+y_8^2,… …,y_(m–3)^2+y_(m–2)^2+y_(m–1)^2+y_m^2)
Q 1 ( y 1 , , y m ) = = Q y 1 2 + y 2 2 + y 3 2 + y 4 2 , y 5 2 + y 6 2 + y 7 2 + y 8 2 , , y m 3 2 + y m 2 2 + y m 1 2 + y m 2

polinomot. Ezt tehát úgy kapjuk Q

Q -ból, hogy mindegyik x_i x i változó helyére négy új változó négyzetösszegét írjuk. Most felhasználjuk azt a nevezetes tételt, amely szerint minden természetes szám előáll négy négyzetszám összegeként (lásd [1], 237. oldal). Nyilvánvaló, hogy Q_1 Q 1 -ben a változók helyére tetszőleges egészeket helyettesítve ugyanazokat az értékeket kapjuk, mint amikor Q Q -ban a változók helyére tetszőleges természetes számokat helyettesítünk. Így a max(Q_1(y_1,…,y_m),2) max ( Q 1 ( y 1 , , y m ) , 2 ) képlet prímszámot szolgáltat, valahányszor y_1,…,y_m y 1 , , y m egészek, továbbá minden prímszámot megkapunk már akkor is, ha az y_i y i -k helyére természetes számokat helyettesítünk.

Olyan függvényeket fogunk gyártani, amelyek minden m

m -hosszúságú, természetes számokból álló vektort kódolnak. Ezeket az y_i y i változók helyére írva egyváltozós prímképletet kapunk. A konstrukciót csak m=2 m = 2 -re és m=3 m = 3 -ra adjuk meg, de világos lesz, hogy minden m m -re elvégezhető.

Lássuk be először, hogy az ([√n],n–[√n]^2)

( n , n n 2 ) függvénypár minden olyan (b_1,b_2) ( b 1 , b 2 ) számpárt kódol, amelyre b_1≥b_2≥0 b 1 b 2 0 . Legyen ugyanis n=b_1^2+b_2 n = b 1 2 + b 2 . Ekkor

b_1^2≤nlb_1^2+2b_1+1
b 1 2 n l b 1 2 + 2 b 1 + 1

(hiszen b_2≤b_1

b 2 b 1 ), tehát b_1≤√nlb_1+1 b 1 n l b 1 + 1 . Így [√n]=b_1 [ n ] = b 1 és

n–[√n]^2=(b_1^2+b_2)–b_1^2=b_2.
n n 2 = ( b 1 2 + b 2 ) b 1 2 = b 2 .

Ha most a_1

a 1 , a_2 a 2 tetszőleges természetes számok, akkor a_1+a_2≥a_2 a 1 + a 2 a 2 , tehát van olyan n n , amelyre [√n]=a_1+a_2 [ n ] = a 1 + a 2 és n–[√n]^2=a_2 n n 2 = a 2 . Ekkor [√n]–(n–[√n]^2)=a_1 [ n ] n n 2 = a 1 és n–[√n]^2=a_2 n n 2 = a 2 , tehát az ([√n]–n+[√n]^2,n–[√n]^2) ( [ n ] n + n 2 , n n 2 ) függvénypár minden természetes számokból álló számpárt kódol.

Most tekintsük az m=3

m = 3 esetet! Belátjuk először, hogy a

g_1(n)=[ ^4√n], g_2(n)=[√n]–g_1(n)^2,
g 1 ( n ) = n 4 , g 2 ( n ) = n g 1 ( n ) 2 ,

g_3(n)=n–(g_1(n)^2+g_2(n))^2
g 3 ( n ) = n g 1 ( n ) 2 + g 2 ( n ) 2

függvények minden olyan (b_1,b_2,b_3)

( b 1 , b 2 , b 3 ) vektort kódolnak, melyekre b_1≥b_2≥b_3≥0 b 1 b 2 b 3 0 . Valóban, legyen n=(b_1^2+b_2)^2+b_3 n = ( b 1 2 + b 2 ) 2 + b 3 . Ekkor (b_1^2+b_2)^2≤nl(b_1^2+b_2)^2+2(b_1^2+b_2)+1 ( b 1 2 + b 2 ) 2 n l ( b 1 2 + b 2 ) 2 + 2 ( b 1 2 + b 2 ) + 1 (hiszen b_3≤b_2 b 3 b 2 ), tehát b_1^2+b_2≤√nlb_1^2+b_2+1 b 1 2 + b 2 n l b 1 2 + b 2 + 1 és b_1^2≤√nlb_1^2+2b_1+1 b 1 2 n l b 1 2 + 2 b 1 + 1 (hiszen b_2≤b_1 b 2 b 1 ). Így [√n]=b_1^2+b_2 n = b 1 2 + b 2 , [ ^4√n]=b_1 n 4 = b 1 , amiből g_1(n)=b_1 g 1 ( n ) = b 1 , g_2(n)=b_2 g 2 ( n ) = b 2 és g_3(n)=b_3 g 3 ( n ) = b 3 .

Ha most a_1

a 1 , a_2 a 2 , a_3 a 3 tetszőleges természetes számok, akkor a_1+a_2+a_3≥a_2+a_3≥a_3 a 1 + a 2 + a 3 a 2 + a 3 a 3 , tehát van olyan n n , amelyre g_1(n)=a_1+a_2+a_3 g 1 ( n ) = a 1 + a 2 + a 3 , g_2(n)=a_2+a_3 g 2 ( n ) = a 2 + a 3 és g_3(n)=a_3 g 3 ( n ) = a 3 . Ebből következik, hogy a g_1–g_2 g 1 g 2 , g_2–g_3 g 2 g 3 és g_3 g 3 függvények minden természetes számokból álló számhármast kódolnak.

Ezt a konstrukciót minden m

m -re elvégezhetjük. Ha az így kapott függvényeket Q_1 Q 1 -be helyettesítjük, akkor végül is a következő tételt kapjuk.

Létezik olyan f(n)

f ( n ) kifejezés, amely az n n , [√n] n , [ ^4√n] n 4 , …, [ ^(2^r)√n] n 2 r 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 max(f(n),2) max ( f ( n ) , 2 ) (n=0 n = 0 , 1, …) számok halmaza pontosan a prímszámok halmazával egyenlő.

Ilyen alakban nemcsak 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 r

r minimális értéke? (A fenti gondolatmenet r=39 r = 39 -et ad, hiszen k k -ra az ismert legkisebb érték 9, és r=m–1=4(k+1)–1 r = m 1 = 4 ( k + 1 ) 1 .) Lehet-e pl. olyan prímképletet megadni, amely csak az n n és [√n] n függvényeket használja?

2. Megadható-e olyan, fenti alakú f

f függvény, amelyre f(n)=p_n f ( n ) = p n minden n n -re?