Una sequenza tale che $\text{MCD}(n,x_n)=1$
Una sequenza tale che $\text{MCD}(n,x_n)=1$
Sia fissata una sequenza $(x_n)_{n \in \mathbb{N}}$ di modo tale che $x_1=2$ e $x_{n+1}=2x_n^2-1$ per ogni intero $n\ge 1$. Dimostrare che $\text{MCD}(n,x_n)=1$
The only goal of science is the honor of the human spirit.
Re: Una sequenza tale che $\text{MCD}(n,x_n)=1$
Supponiamo per assurdo che esista $p$ primo per cui esiste $m$ intero tale che $p\mid m$ e $p\mid x_m$ (cioè per cui $p\mid MCD(m,x_m)$).
Vediamo un po' di cose carine che capitano:
a) se esiste $k$ tale che $x_k \equiv 1 \pmod p$ allora vale anche per tutti i termini seguenti. Infatti se $k$ è il minore che verifica questa proprietà, ricavo che $x_{n+1} =2x_n-1\equiv2\cdot 1^2-1=1\pmod p$. Quindi preso il caso base relativo ad $k$, per induzione ho che $x_i\equiv 1 \pmod p \forall i\ge k$.
b) se esiste $k$ tale che $x_k\equiv 0\pmod p$ allora è unico. Infatti se $k$ è il più piccolo che verifica la proprietà, ho che $x_{k+1}=2x_k^2-1\equiv -1 \pmod p$; $x_{k+2}=2x_{k+1}^2-1\equiv 1 \pmod p$ e quindi per quanto detto sopra $x_i\equiv 1 \pmod p \forall i\ge k+2$.
Ora mi basta dimostrare che se esiste un $k$ che verifica quest'ultima proprietà, allora non è multiplo di $p$, in modo che non possa succedere che $p$ divida un termine e il suo indice, ricavando così l'assurdo. Consideriamo i primi $p-1$ numeri della serie a modulo $p$.
Divido tre casi:
- se tra essi c'è un numero congruo a 0, allora per b) è unico e il suo indice non è multiplo di $p$;
- se tra essi c'è un numero congruo a 1, allora per a) tutti i successivi sono congrui a 1 e pertanto lo sono anche tutti i numeri con indice multiplo di $p$;
- se tra essi non compare nè la classe 0 nè la classe 1, allora ho ancora p-2 classi di resto e p-1 numeri; quindi per il pigeonhole ho due indici $i < j<p$ tali che $x_i\equiv x_j \pmod p$. Siccome la classe di un numero dipende unicamente dal suo precedente, se compaiono due numeri della stessa classe, allora si verifica una periodicità formata dai numeri compresi tra $i$ e $j-1$, tra cui per quanto ipotizzato non è presente la classe 0. Quindi si ripeteranno classi senza lo 0, e quindi questa classe non comparirà mai.
In tutti e tre i casi ho trovato l'assurdo e quindi segue la tesi.
Vediamo un po' di cose carine che capitano:
a) se esiste $k$ tale che $x_k \equiv 1 \pmod p$ allora vale anche per tutti i termini seguenti. Infatti se $k$ è il minore che verifica questa proprietà, ricavo che $x_{n+1} =2x_n-1\equiv2\cdot 1^2-1=1\pmod p$. Quindi preso il caso base relativo ad $k$, per induzione ho che $x_i\equiv 1 \pmod p \forall i\ge k$.
b) se esiste $k$ tale che $x_k\equiv 0\pmod p$ allora è unico. Infatti se $k$ è il più piccolo che verifica la proprietà, ho che $x_{k+1}=2x_k^2-1\equiv -1 \pmod p$; $x_{k+2}=2x_{k+1}^2-1\equiv 1 \pmod p$ e quindi per quanto detto sopra $x_i\equiv 1 \pmod p \forall i\ge k+2$.
Ora mi basta dimostrare che se esiste un $k$ che verifica quest'ultima proprietà, allora non è multiplo di $p$, in modo che non possa succedere che $p$ divida un termine e il suo indice, ricavando così l'assurdo. Consideriamo i primi $p-1$ numeri della serie a modulo $p$.
Divido tre casi:
- se tra essi c'è un numero congruo a 0, allora per b) è unico e il suo indice non è multiplo di $p$;
- se tra essi c'è un numero congruo a 1, allora per a) tutti i successivi sono congrui a 1 e pertanto lo sono anche tutti i numeri con indice multiplo di $p$;
- se tra essi non compare nè la classe 0 nè la classe 1, allora ho ancora p-2 classi di resto e p-1 numeri; quindi per il pigeonhole ho due indici $i < j<p$ tali che $x_i\equiv x_j \pmod p$. Siccome la classe di un numero dipende unicamente dal suo precedente, se compaiono due numeri della stessa classe, allora si verifica una periodicità formata dai numeri compresi tra $i$ e $j-1$, tra cui per quanto ipotizzato non è presente la classe 0. Quindi si ripeteranno classi senza lo 0, e quindi questa classe non comparirà mai.
In tutti e tre i casi ho trovato l'assurdo e quindi segue la tesi.
This is it. This is your story. It all begins here.
Re: Una sequenza tale che $\text{MCD}(n,x_n)=1$
molto bene (fonte: Cesenatico 2007 /5)
The only goal of science is the honor of the human spirit.