Primi in una successione

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Leonhard Euler
Messaggi: 42
Iscritto il: 01 gen 2018, 15:12

Primi in una successione

Messaggio da Leonhard Euler »

Sia $ a\geq1 $ un intero fissato, si definisca la successione $ x_n=2^{2^{n} }+a $. Dimostrare che esiste almeno un intero positivo $ m $ per cui $ x_m $ non sia primo.
Bonus: Gli interi non primi appartenenti alla successione $ x_n $ sono in numero finito?
« [...] ha cessato di calcolare e di vivere. » (Eulogia di Eulero)
Parmenide
Messaggi: 27
Iscritto il: 30 mag 2018, 21:24

Re: Primi in una successione

Messaggio da Parmenide »

Consideriamo $a$ dispari, altrimenti $2|x_n$ $\forall n$.
Per $a=1$ otteniamo i numeri di Fermat, e $x_5$ non è primo. Studiamo quindi $a\ge 2$.
Consideriamo ora $m$ tale che $\displaystyle 2^{m}>a$ e analizziamo i possibili fattori primi di $x_m$:

siccome $a\not\equiv 1$ mod $2^m$ in quanto $2^m>a\geq 2$, allora $2^{2^m}+a\not\equiv 1$ mod $2^m$ e quindi esiste $p$ primo tale che $p\not\equiv 1$ mod $2^m$ e $p|2^{2^m}+a$.
Scriviamo $p-1=2^kc$, con $k<m$ e $c$ dispari.

Dimostriamo ora che esistono $m,m_1$ interi tali che $\displaystyle \left(2^{2^m}+a,2^{2^{m_1}}+a\right)>1$. Questo permette di concludere che almeno uno tra $x_m$ e $x_{m_1}$ non è primo, in quanto la successione $x_n$ è strettamente crescente.

Sia $m_1=\displaystyle m+ord_c 2$. Usando le proprietà del MCD si ha $\displaystyle{\left(2^{2^m}+a,2^{2^{m_1}}+a\right)=\left(2^{2^m}+a, 2^{2^{m_1}}-2^{2^m}\right)}$
Abbiamo che $2^{2^{m_1}}-2^{2^m}\equiv 2^{2^m}\left(2^{2^{m+ord_c 2}-2^m}-1\right)$ mod $p$
Ma $\displaystyle 2^{m+ord_c 2}-2^m\equiv 2^m\left(2^{ord_c 2}-1\right)\equiv 0$ mod $p-1$ in quanto $2^k|2^m$ essendo $k<m$ e $2^{ord_c 2}\equiv 1$ mod $c$, da cui $c|2^{ord_c 2}-1$.

Allora possiamo scrivere $2^{m_1}-2^m=h(p-1)$, per cui $2^{2^{m_1}}-2^{2^m}\equiv 0$ mod $p$.
Siccome, per come abbiamo definito $p$, si ha $p| 2^{2^m}+a$, allora $\displaystyle \left(2^{2^m}+a, 2^{2^{m_1}}-2^{2^m}\right)\geq p >1$ e quindi uno tra $x_m$ e $x_{m_1}$ non è primo.
Rispondi