OliForum Matematico

trovare tutti i primi della forma $n^n+1$ che sono $<10^{19}$.

Oltre a provare (a manina) i pochi casi, c'è un modo più elegante?

Io ho tolto solo i multipli di 3 in quanto $n^{3k}$ scomponibile in somma di cubi, ma nulla di più

Teoricamente si possono togliere tutti i multipli di numeri dispari. Vanno quindi controllati solo le potenze di 2

RiccardoKelso ha scritto:Io ho tolto solo i multipli di 3 in quanto $n^{3k}$ scomponibile in somma di cubi, ma nulla di più

Forse ho frainteso il testo del quesito? Sto considerando solo
$ 1^{1} + 1, 2^{2} + 1, 3^{3} + 1,..., 14^{14} + 1, 15^{15} + 1 $
e da questi ho tolto tutti gli $ n > 1 $ dispari

Penso che RiccardoKelso intendesse scrivere che $n^{3}+1$ divide $n^{3k}+1$.
Comunque mettendo insieme le idee che avete scritto, con un poco di sforzo in più, si arriva a dover controllare solamente un caso non banale...

effettivamente $n$ deve essere una potenza di $2$ infatti se non lo fosse allora $n=t^m$ dove $t=(2^k\cdot m)^{2^k}$ e $m$ è un numero dispari.
Essendo dispari $t^m+1=(t+1)(t^{m-1}-t^{m-2}\cdots -t+1)$.
Ora vi resta da cercare il primi nelle potenze di $2$ e ''basta''

per quanto detto fino ad adesso $n$ è uguale a $1$ oppure deve essere pari, più precisamente una potenza di $2$.
quindi $n=2^{2^t\cdot (2k+1)}$ e
$n^n+1=2^{2^t\cdot (2k+1)\cdot 2^{2^t\cdot (2k+1)}}+1=2^{2^{t+2^t(2k+1)}\cdot (2k+1)}+1=(2^{2^{t+2^t(2k+1)}})^{(2k+1)}+1$
ma questo è divisibile per $2^{2^{t+2^t(2k+1)}}+1$ quindi non è sicuramente primo per $k\ge 1$.
Allora $n$ è della forma $n=2^{2^t}$ e sostituendo $t=0,1,2$ a $(2^{2^t})^{2^{2^t}}+1$ si ottiene rispettivamente $5,257,16^{16}+1$.
$5$ e $257$ sono due primi e per fortuna $16^{16}+1>16^{16}=4^{32}>10\cdot 4^{30}=10\cdot (4^5)^{6}>10\cdot (10^3)^{6}=10^{19}$ e quindi non ci interessa.
in definitiva i primi sono $2,5,257$.