$x_1=2$
$x_{n+1}=2(x_n)^2-1$
Dimostrare he $n$ e $x_n$ sono relativamente primi per ogni $n\geq 1 $
Noto che se un intero $k$ è tale che $k|x_n$, allora $x_{n+1}\equiv -1 \mod k$, e $x_{n+i}\equiv 1 \mod k$ per ogni $i\geq 2$. (*)
Voglio dimostrare che se un primo $p$ divide $x_n$, allora $p$ non divide $n$ (e viceversa).
Sapendo che $x_1\equiv 2 \mod p$, considero tutti i possibili resti nella divisione per $p$ dei termini fino a $x_n$:trattandosi di una successione, otterrò un "ciclo",ovvero se mai otterrò due volte lo stesso resto nella divisione per $p$ vuol dire che da quel momento mi si ripeterà all'infinito quella successione di resti.
Sapendo che i valori $0,-1,1$ per il resto mi portano in un breve ciclo "separato" che finisce su infiniti termini $\equiv 1 \mod p$, il ciclo più lungo di resti nella successioni che mai si ripetano è di lunghezza $p-3$.
Infatti se otteniamo $x_i\equiv x_j \mod p$, con $1\leq i<j<n$, vuol dire necessariamente che tra $x_i$ e $x_j$, c'è un termine congruo a 0 mod $p$: questo ci è assicurato dal fatto che se due resti si ripetono, tra i 2 termini che ripetono lo stesso resto si dovranno trovare termini che danno gli stessi identici resti di quelli che vengono DOPO il secondo di questi termini ,(trattandosi di un ciclo), e avendo noi un $x_n\equiv 0$ successivo a $x_j$,siamo quindi sicuri che tra $x_i$ e $x_j$ c'è un termine divisibile per $p$.
Nel caso invece del ciclo più lungo in cui per $p-3$ termini non si ripetono resti, avrò che comunque dopo $p-3$ termini devo ottenere un termine congruo a 0, altrimenti cadrei nel caso precedente. Entrambi questi casi rendono il fatto che $x_n \equiv 0 \mod p$ un assurdo, perchè se esiste un termine divisibile per $p$ precedente a $x_n$, per il fatto $\rightarrow$ (*) da quel momento in poi non posso più ottenere termini divisibili per $p$, e questo ci dà la tesi.
(ha un senso?
)