Hogyan kellene bebizonyitani? Ha n^n+1 prim szám, akkor igaz, hogy n=2^2^m valamilyen nem negativ egész m-re.

De igaz n=1-re is:

1^1+1=2 (ez prím)

m=0 esetén pedig: 2^(2^0)=2^1=2

Ha n=p*k (p páratlan prím), akkor

(p*k)^(p*k)+1=[(p*k)^(k)]^p+1^p

márpedig ismert, hogy páratlan kitevő esetén

a^k+b^k összeg felírható (a+b)*(.....) alakban

ezért n^n+1 nem lenne prím

ebből annyi jön ki, hogy n biztosan 2-hatvány

(még nem látom, hogy a kitevő miért lesz 2-hatvány)

Nem tudom, hogy segít-e (valószínűleg nem) de borzasztó érdekesnek találom, hogy a sima n = 2^k alakú n-ekre n^n + 1-nek a k-adik Fermat-szám (2^2^k + 1) mindig osztója, ha k páratlan, és mindig 2 maradékot ad vele, ha k páros.

Bizonyításom sincs, csak feltűnt:

[link]

Sőt, páros k esetén n^n + 1 nem csak F(k)-val osztva ad 2 maradékot, de F(k) összes prímtényezőjével egyenként is.

Ez utóbbit azért tartom igazán durvának, mert azt, hogy egy (2^2k)^(2^2k) + 1 alakú szám 2^2^2k + 1-gyel 2 maradékot adjon, arról még úgy-ahogy el tudom képzelni, hogy fehér ember számára is érthető módon be lehet bizonyítani.

De hogy többszáz, többezer jegyű, sőt, kellően nagy k-ra gyakorlatilag elképzelhetetlen nagy prímek tömkelegével is mind 2 maradékot adjon, na az már tényleg nem semmi.

Á, megvan. Nem volt baj, hogy feltűntek a Fermat-számok, mert a wikipedia-oldaláról tudtam lopni a bizonyításhoz egy lemmát.

Lemma: Ha 2^n + 1 prím, akkor n=2^m alakú, feltéve hogy n>0 (igaza volt #2-esnek). Belátni ugyanazzal a páratlan kitevős szabállyal lehet, mint ahogy #4-es tette.

Ezután #4-es bizonyításával belátjuk, hogy a kérdésben szereplő n is 2 hatványa, azaz n=2^k. Már csak azt kell belátni, hogy k maga is 2 hatvány.

A tétel tehát: ha (2^k)^(2^k) + 1 prím, akkor k=2^l alakú. Bizonyítás:

(2^k)^(2^k) + 1 = 2^(k*2^k) + 1.

A lemma alapján k*2^k = 2^m alakú. Ami természetesen csakis akkor teljesülhet, ha k 2-hatvány.