Quinto problema della gara nazionale individuale del 2007

[DottorDoom]

Ciao ragazzi.. Non riesco a capire come risolvere questo problema; anche vedendo la soluzione... Data la successione a(1)=2 e a(n+1)=a(n)^2 -1, bisogna dimostrare che MCD(a(n);n)=1

[Drago]

Allora, l'idea base è che se prendi un qualunque primo $p$, allora c'è al più un termine divisibile per $p$; infatti se guardi la successione modulo $p$, se c'è un termine divisibile per $p$, avrai $\dots0, -1, 1, 1, 1,\dots$
Ora, prendi un primo che divide $n$ e $a_n$ per assurdo; quindi tra i termini $a_1,\dots,a_{n-1}$ non ci sono $0,\pm1$ e per pigeonhole ci sono allora 2 termini che si ripetono e quindi la successione è periodica, ma ciò è impossibile perchè poi sono tutti 1...

E' scritta da cani, però l'idea fondamentale è appunto la periodicità...

[DottorDoom]

Grazie mille