prime-chasing

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
wotzu
Messaggi: 52
Iscritto il: 16 dic 2015, 21:33

prime-chasing

Messaggio da wotzu »

trovare tutti i primi della forma $n^n+1$ che sono $<10^{19}$.
andreac
Messaggi: 50
Iscritto il: 12 set 2008, 17:16

Re: prime-chasing

Messaggio da andreac »

Oltre a provare (a manina) i pochi casi, c'è un modo più elegante?
Testo nascosto:
$ 15^{15}+1 < 10^{19} < 16^{16}+1 $
ed eliminando gli n dispari (tolto $ n=1 $ ), mi restano una manciata di casi da verificare
RiccardoKelso

Re: prime-chasing

Messaggio da RiccardoKelso »

Io ho tolto solo i multipli di 3 in quanto $n^{3k}$ scomponibile in somma di cubi, ma nulla di più :(
AlexThirty
Messaggi: 217
Iscritto il: 20 giu 2015, 20:58

Re: prime-chasing

Messaggio da AlexThirty »

Teoricamente si possono togliere tutti i multipli di numeri dispari. Vanno quindi controllati solo le potenze di 2
Un bresciano esportato nel cremonese

-"Dal palazzo di giustizia di Catania o esci con più soldi di prima, o non esci proprio"
-"Baroni uscirebbe con un Win - Win".
Tutti si mettono a ridere, e allora intuisco che non aveva detto "Weed - Win" come avevo capito.
andreac
Messaggi: 50
Iscritto il: 12 set 2008, 17:16

Re: prime-chasing

Messaggio da andreac »

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
Giulia 400
Messaggi: 43
Iscritto il: 31 dic 2011, 13:00
Località: Città degli scacchi (VI)

Re: prime-chasing

Messaggio da Giulia 400 »

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... :wink:
"La vita è come uno specchio: ti sorride se la guardi sorridendo". :)
wotzu
Messaggi: 52
Iscritto il: 16 dic 2015, 21:33

Re: prime-chasing

Messaggio da wotzu »

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''
wotzu
Messaggi: 52
Iscritto il: 16 dic 2015, 21:33

Re: prime-chasing

Messaggio da wotzu »

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$.
Rispondi