Un primo esprimibile come n^n+1 (Mathlinks)

[dario2994]

L'ho trovato su Mathlinks e lo piazzo perchè nasconde un bel fattarello che non conoscevo, da lasciare ai novizi:
Dato un primo $ p>2010 $ se è esprimibile come $ n^n+1 $ per qualche $ $ n\in\mathbb{N} $ allora $ $2^{64}|p-1 $

edit: ho editato, ora è 64, avevo toppato un conticino

[Maioc92]

perchè non $ 2^{64} $??

[Giulio_C]

Come novizio, ci provo.

Si osserva prima di tutto che $ n^{n} $ è pari, quindi contiene il fattore 2.
La prima potenza del tipo $ 2k^{2k}>2010 $ è $ 6^{6} $; tuttavia $ 6^{6}+1 $ non è primo perché è scomponibile come somma di cubi. Ugualmente, $ 8^{8}+1, 10^{10}+1, 12^{12}+1, 14^{14}+1 $ sono scomponibili come somme di potenze a esponente dispari, rispettivamente come $ (8^{2})^{3}+1^{3}, (10^{2})^{5}+1^{5}, (12^{4})^{3}+1^{3}, (14^{2})^{7}+1^{7} $. Invece $ 16^{16}+1 $ non è scomponibile poiché non può essere ridotto a una somma di potenze a esponente dispari, perciò è un numero primo. Quindi $ n=16 $ soddisfa l'ipotesi e $ 2^{64}|[(16^{16}+1)-1] $, poiché $ (16^{16}+1)-1=16^{16}=(2^{4})^{16}=2^{64} $.

In generale, si osserva che le uniche potenze che non possono essere ricondotte a potenze a esponente dispari sono quelle della forma $ q^{2^{2^{2^{\ldots}}}} $, con $ q $ primo; in particolare, le uniche potenze pari che non possono essere ricondotte a quella forma sono date da $ q=2 $; perciò, gli unici primi della forma $ n^{n}+1 $ sono $ 2^{2}+1, (2^{2})^{2^2}+1=4^{4}+1, \bigl(2^{2^{2}}\bigr)^{2^{2^{2}}}+1=16^{16}+1, \Bigl(2^{2^{2^{2}}}\Bigr)^{2^{2^{2^{2}}}}+1=256^{256}+1, \ldots $, ed evidentemente, a partire da $ 16^{16} $, tutte queste potenze sono divisibili per $ 2^{64} $. (Se la dimostrazione è corretta, credo sia questo il bel fattarello )

[Gauss91]

Invece $ 16^{16} + 1 $ non è scomponibile poiché non può essere ridotto a una somma di potenze a esponente dispari, perciò è un numero primo

.

Il fatto che non sia scomponibile perché non si può ridurre ad una somma di potenze ad esponente dispari è condizione necessaria ma non sufficiente perché sia primo.
Tipo $ 2^{32} + 1 $ non è primo. E ti dirò di più: non lo è neppure $ 16^{16} + 1 = 2^{64} + 1 =274177 \cdot 67280421310721 $.
Numeri di quel tipo vengono detti "numeri di Fermat", e non si sa neppure se ne esistono infiniti che siano primi (è una congettura).
Se vuoi qualche informazione, http://en.wikipedia.org/wiki/Fermat_number .
Ciao!

[dario2994]

Purtroppo hai sbagliato un particolare...
Qui hai sbagliato la fattorizzazione:
$ $8^8+1\not = (8^2)^3+1 $
Comunque sei vicino alla soluzione

[Haile]

Mmm

Il fatto che $ ~ n^n + 1 $ non sia scomponibile non implica che esso sia primo. Ad esempio $ ~ n^2+1 $ non è scomponibile negli interi, ma 8²+1 non è primo.

In particolare
$ ~ 16^{16} + 1 = 18446744073709551617 = 274177 \cdot 67280421310721 $

EDIT: anticipato

[Gauss91]

@Giulio_C: ci sei stravicinissimo è più semplice di quanto hai fatto!

[<enigma>]

Ovviamente n è pari, $ n=2k $. Però $ (2k)^{2k}+1=2^{2k} k^{2k}+1 $, cioè $ p-1=2^{2k} k^{2k} $, che è multiplo di $ 2^{2k} $. Quindi la tesi è verificata per tutti i $ 2k\geq 64 $, cioè gli $ n\geq 64 $; per i casi piccoli direi come ha già scritto Giulio_C che si possono ricondurre a potenze ad esponente dispari, e quindi gli unici casi da provare sono $ 2^2+1, 4^4+1, 8^8+1, 16^{16}+1, 32^{32}+1 $, cioè $ 2^2+1, 2^8+1, 2^{24}+1, 2^{64}+1, 2^{160}+1 $. In effetti i primi due sono primi ma minori di 2010, quelli ad esponenti 64 e 160 soddisfano le condizioni in ogni caso, e $ 2^{24}+1=(2^8)^3+1^3 $ si riconduce sempre ad un esponente dispari.

[dario2994]

Uhm... si è giusto.
Comunque il fattarello voleva essere:
$ $n^n+1\in\mathbb{P}\Rightarrow n=2^{2^a} $
Che è facilotto da dimostrare ;)

[<enigma>]

Faccio un tentativo stupido:
l'esponente di $ n $ deve avere solo fattori primi pari, perché altrimenti ci si ricondurrebbe alla somma di potenze dispari. Quindi $ n=2^k $; allora $ n^n=(2^k)^{2^{k}}=2^{k 2^k} $. Quindi $ k 2^k $ ha solo fattori pari per lo stesso discorso di prima, i.e. $ k=2^j $ e quindi $ n=2^{2^{j}} $.
Devo aver sbagliato qualcosa, è troppo semplice

[dario2994]

Non vedo perchè dovrebbe essere complicato xD E' giusto

[<enigma>]

Ah ok, è solo che avendo Sierpinski per primo dimostrato questo risultato, che a me sembra davvero elementare, pensavo fosse più difficile. (http://www.research.att.com/~njas/sequences/A121270)

Ho trovato un altro problema carino: sapreste dimostrare che per ogni $ n $ fissato esistono infiniti numeri primi congruenti a 1 (mod $ 2^n $)? (questo è leggermente più difficile )

[jordan]

E' stato più volte dimostrato in via elementare anche su qusto forum che esistono infiniti primi con resto 1 in Z/nZ, credo sia più che sufficiente

[dario2994]

Uhm... provo comunque.
Considero $ $m=2^{2^{n-1}}+1 $.
Dimostro che $ $p|m\Rightarrow p\equiv 1\pmod{2^n} $ che è la tesi.
Sfruttando l'ipotesi posso dire:
$ $Ord_p(2)|2^{n} $
Ed anche:
$ $Ord_p(2)\not| 2^{n-1} $
L'unica è che $ $Ord_p(2)=2^n $ da cui:
$ 2^n|p-1 $
Che è la tesi.

p.s. se questo è giusto provo a fare il caso generale...

EDIT: Ho provato a sfruttare questo metodo anche per il caso generale, peccato che mi pare funzioni solamente con n primo...

[<enigma>]

E' stato più volte dimostrato in via elementare anche su qusto forum che esistono infiniti primi con resto 1 in Z/nZ, credo sia più che sufficiente

Sì, ma se non sbaglio questa dimostrazione richiede l'uso dei polinomi ciclotomici (sto andando a memoria), io avevo in mente una dimostrazione ancora più elementare.