Sequenza e primi

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
alex00
Messaggi: 8
Iscritto il: 18 giu 2016, 00:57

Sequenza e primi

Messaggio da alex00 » 04 nov 2016, 21:51

Sia \(a_{n+1}=2^{a_n}-1\) provare che l'insieme di numeri primi che dividono \(a_n \forall n\) è infinito.
Testo nascosto:
Ho una soluzione ma non sono sicuro della correttezza.

Consideriamo un primo \(p\) che divida \(2^{a_n}-1\), questo vuol dire che \(2^{a_n}\equiv 1 \pmod p\) quindi \(a_n|p-1\) in quanto è ordine moltiplicativo. Ora da ciò deduciamo che \(p\equiv 1 \pmod{a_n}\).
In conclusione \(p\) non può dividere \(a_n\), e per giunta è anche maggiore di \(a_n\) quindi non può essere anche divisore di qualche altro elemento più piccolo di \(a_n\). Dunque ogni \(a_n\) presenta un "nuovo" primo ed essendo la sequenza infinita ci sono infiniti primi diversi.

Avatar utente
Sirio
Messaggi: 296
Iscritto il: 08 set 2016, 22:01

Re: Sequenza e primi

Messaggio da Sirio » 05 nov 2016, 07:49

C'è una cosa che non mi convince.
Testo nascosto:
alex00 ha scritto:\(2^{a_n}\equiv 1 \pmod p\) quindi \(a_n|p-1\) in quanto è ordine moltiplicativo.
$a_n$ può esser multiplo dell'ordine moltiplicativo.
シリオ
$T=\sqrt{\dfrac l g 12\pi}$
"Sirio Passirio" cit. Nicola S.

alex00
Messaggi: 8
Iscritto il: 18 giu 2016, 00:57

Re: Sequenza e primi

Messaggio da alex00 » 05 nov 2016, 11:31

Eh è quello su cui non sono sicurissimo, cioè è possibile dire che avrò sempre un primo per cui accade questo? (L'altra mia ipotesi era di usare Zsigmondy)

Avatar utente
Sirio
Messaggi: 296
Iscritto il: 08 set 2016, 22:01

Re: Sequenza e primi

Messaggio da Sirio » 05 nov 2016, 13:31

Anzi, mi sa tanto che ho trovato un controesempio...
Testo nascosto:
Se $a_0=1$ allora $a_n=1$ $\forall n$
シリオ
$T=\sqrt{\dfrac l g 12\pi}$
"Sirio Passirio" cit. Nicola S.

alex00
Messaggi: 8
Iscritto il: 18 giu 2016, 00:57

Re: Sequenza e primi

Messaggio da alex00 » 06 nov 2016, 16:00

Mi sembra ovvio che \(a_0\not= 1\), diciamo che era sottinteso.

darkcrystal
Messaggi: 683
Iscritto il: 14 set 2005, 11:39
Località: Chiavari

Re: Sequenza e primi

Messaggio da darkcrystal » 11 nov 2016, 15:04

Innanzitutto un commento sul testo: immagino voglia dire "l'insieme dei numeri primi che dividono almeno uno degli $a_n$ è infinito", vero? (non è quello che c'è scritto, però!)
La soluzione di alex00 che c'è nel primo post non funziona per il motivo che dice Sirio: per quanto ne sappiamo, a priori $a_n$ può essere arbitrariamente più grande di $p-1$. Quello che verrebbe da fare a me, invece di pensare a teoremoni vari (Zsygmondy? Naah... comunque non vedo come applicarlo a questo problema!), è
Testo nascosto:
cercare di capire cosa succeda a questa successione se la guardiamo modulo $m$, per un $m$ qualunque.
E poi, una volta fatto questo,
Testo nascosto:
farsi la seguente domanda: se $p$ divide sia $a_n$ che $a_{n+1}$, quanto è grande l'esponente di $p$ nella fattorizzazione di $a_{n+1}$ rispetto a quello nella fattorizzazione di $a_n$? Ma quanto è grande $a_{n+1}$ rispetto ad $a_n$?
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein

Membro dell'EATO

Giovanni_98
Messaggi: 69
Iscritto il: 10 apr 2015, 18:19

Re: Sequenza e primi

Messaggio da Giovanni_98 » 11 nov 2016, 15:51

Definiamo $P(a_i)$ come il più piccolo primo che divide $a_i$. Per dimostrare la tesi dimostriamo che la funzione $P(a_i)$ è una funzione strettamente crescente (cioè che al crescere di $i$ cresce anche $P(a_i))$. Abbiamo $a_{i+1} = 2^{a_i} - 1$. Ora se $p$ è un primo che divide $a_{i+1}$ allora $ord_p (2) \mid a_i$. Poichè $ord_{P(a_{i+1})} (2) \mid P(a_{i+1})-1$ vale $ord_{P(a_{i+1})} \leq P(a_{i+1})-1$, ma ricordiamo anche che vale come prima scritto $ord_{P(a_{i+1})}(2) \mid a_i$, allora se $ord_{P(a_{i+1})}(2) \ne 1$ (ed è ovviamente verò poichè $2^1-1=1$ che è minore di ogni numero primo) vale $ord_{P(a_{i+1})} (2)\ge P(a_i)$ , da cui $P(a_{i+1})-1 \ge ord_{P(a_{i+1})}(2) \ge P(a_i)$ vale $P(a_{i+1})-1 \ge P(a_i)$ come volevamo.

darkcrystal
Messaggi: 683
Iscritto il: 14 set 2005, 11:39
Località: Chiavari

Re: Sequenza e primi

Messaggio da darkcrystal » 11 nov 2016, 16:11

Bella! E molto più semplice di quella che avevo in mente :)
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein

Membro dell'EATO

Giovanni_98
Messaggi: 69
Iscritto il: 10 apr 2015, 18:19

Re: Sequenza e primi

Messaggio da Giovanni_98 » 12 nov 2016, 10:09

Grazie Dark :)

Rispondi