Cesenatico 2007

[tommy1996q]

Posto un problema della finale delle olimpiadi di matematica del 2007. Quelli primi li ho fatti, ma di questo non ho capito nemmeno la soluzione proposta! Metto il testo e la soluzione nello spoiler, se qualcuno ci capisse qualcosa e me lo spiegasse in altri termini mi farebbe un piacere.

Ecco il problema:

Sia data la successione
$x(1) = 2;$
$x(n+1) = 2x(n)^2 − 1 $ per n ≥ 1

Dimostrare che n e x(n) sono relativamente primi per ogni n ≥ 1.

Soluzione: Dimostriamo che, se p `e un numero primo che divide x(n), allora p non divide n.
Se p = 2, allora la tesi `e banalmente vera, in quanto tutti i termini x(n) sono dispari per n > 1. Quindi si ha che 2 divide x(n) se e solo se n = 1.
Supponiamo dunque p > 2. Chiamiamo k il più piccolo intero positivo tale che p divida x(k). La successione r(n) dei resti di x(n) nella divisione per p ammette un numero finito di valori (compresi fra 0 e p−1), dunque esisteranno due interi i < j tali che $r(i) = r(j)$ . Per ogni m ≥ 0 si avr`a che$ r(i+m) = r(j+m)$, quindi la successione r(n) è periodica per n ≥ i; ne segue che il valore r(k) = 0 (p divide x(k)) si deve ottenere prima che ci siano due termini della successione r(n) ripetuti.

Inoltre, se n < k, allora$ r(n) ≠ p − 1$, perchè altrimenti$ r(n+1) = r(n+2) = r(n+3) = ・ ・ ・ = 1$, e quindi r(n) non sarebbe mai zero. Quindi si deve avere $r(k)= 0$ per qualche k ≤ p − 1. Ma se $r(k)= 0$, allora $r(k+1) = p − 1 e r(n)= 1 per ogni n > k + 1$, e dunque x(k) `e l’unico termine della successione divisibile per p. Poichè p non divide nessuno dei numeri 1, 2, . . . , p − 1, p non può dividere k.

Nota: In alternativa ad escludere che r(n) possa essere uguale a p − 1 per p > 2 ed n < k, si può notare
che i resti possibili sono non più dei resti dei quadrati (infatti devono essere uguali a 2 volte il resto di
un quadrato meno uno). Poichè per $1 ≤ x ≤ (p − 1)/2$

si ha che il resto di$ x^2$ `e uguale al resto di$ (p−x)^2$, il numero dei resti possibili non supera$ (p − 1)/2 + 1$ un numero che `e minore o uguale a p − 1 per p ≥ 3.

A parte il fatto che non ho capito la spiegazione, non mi torna nemmeno che non faccia riferimento alla formula esplicita della successione!

[dan952]

"tommy1996q":Inoltre, se n < k, allora r(n)≠p−1, perchè altrimentir(n+1)=r(n+2)=r(n+3)=・・・=1, e quindi r(n) non sarebbe mai zero. [...] non mi torna nemmeno che non faccia riferimento alla formula esplicita della successione!

Lì ne fa riferimento, infatti è proprio per come è definita che possiamo affermare quello che c'è scritto sopra