OliForum Matematico

Sia data la successione:
$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? )

LukasEta ha scritto: 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$

Perché? non ho capito. ma se $n=9$ $p=3$ $x_3\equiv x_4 \equiv 1$ e non c'è nessun termine divisibile per 3 tra $x_3$ e $x_4$

paga92aren ha scritto:Perché? non ho capito. ma se n=9 p=3 x3≡x4≡1 e non c'è nessun termine divisibile per 3 tra x3 e x4

.

Il mio discorso vale se $x_n\equiv 0$ \mod p... $x_9$ non è un multiplo di 3, quindi non me lo puoi usare come controesempio..Comunque cerco di spiegarmi meglio!
Io volevo dimostrare che se $x_n$ fosse divisile per $p$, e ci fossero prima di $x_n$ due elementi congrui modulo $p$, allora tra quei due termini della successione dovrebbe esserci un termine congruo a 0 modulo $p$.. Questo perchè in una successione i resti "ciclano", cioè ogni termine congruo a $n$ (p) mi manda in un elemento congruo a $m$ ect...se ho due termini congrui, significa che tra quei 2 c'è stato un ciclo, che dovrà ripetersi nuovamente dopo il secondo: se dopo il secondo ,prima o poi ci fosse un termine congruo a 0 (in questo caso abbiamo supposto $x_n$),allora vorrebbe dire che $0$ appartiene anche al ciclo che intercorre tra i termini $x_i\equiv x_j$...Chiamo $x_f$ il termine congruo a 0 compreso tra $x_i$ e $x_j$. Tuttavia , se esistesse $x_f$, allora $x_{f+1}\equiv -1$, e tutti i termini successivi sarebbero congrui a 1, il che è assurdo perchè $x_n\equiv 0$. Allora $x_n$ è l'unico termine di tutta la successione ad essere divisibile per $p$, e come conseguenza tutti i resti dei termini precedenti a $x_n$ sono diversi.
Ma allora $k\leq p-1$, perchè altrimenti avremmo un numero di termini più grande di quello dei resti diversi ammissibili. (principio dei cassetti). Siccome $p$ non divide nessuno dei numeri $1,2,3....p-1$, allora $p$ non divide $k$

Adesso ho capito la tua idea e mi sembra che funziona.

LukasEta ha scritto: Ma allora $k\leq p-1$, perchè altrimenti avremmo un numero di termini più grande di quello dei resti diversi ammissibili. (principio dei cassetti). Siccome $p$ non divide nessuno dei numeri $1,2,3....p-1$, allora $p$ non divide $k$

Qua ti basta dire che $k<p$ allora $p\not |k$, è ovvio e sempre vero che $p\not | 1,2,3...p-1$ e non c'entra niente con la tua dimostrazione...

piccola nota stilistica: dà $a \not |b$, mentre dà $a\nmid b$.
non lo sapevate? sapevatelo!