Quinto problema della gara nazionale individuale del 2007
-
- Messaggi: 6
- Iscritto il: 02/05/2013, 18:33
Quinto problema della gara nazionale individuale del 2007
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
Re: Quinto problema della gara nazionale individuale del 200
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à...
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à...
-
- Messaggi: 6
- Iscritto il: 02/05/2013, 18:33