OliForum Matematico

Buongiorno ragazzi!
Vorrei ricevere un’opinione sulla correttezza di questa dimostrazione: l’ho scritta io ma vorrei sapere se è giusta e comunque cosa ne pensate…grazie!

TESTO DEL PROBLEMA:
Sia x(1), x(2), x(3), ...... la successione di interi definita da
x(1)=3
x(n+1)= (x(n))^2 – 2 per n≥1
Dimostrare che due elementi qualsiasi distinti della successione sono sempre primi fra loro.

DIMOSTRAZIONE:
Premessa:
la tesi può essere formulata anche nel modo seguente: dimostrare che ogni elemento della successione non ha alcun divisore in comune con tutti i suoi successivi (e dunque anche con tutti i precedenti, per la proprietà simmetrica).

Dimostrazione:
dimostreremo che ogni elemento non ha divisori in comune con i successivi mediante il principio di induzione.
x(1)=3; x(2)=7 e dunque P(0) è verificata perché 3 e 7 non hanno divisori comuni diversi da 1.
Supponendo che x(n) e x(n+1) non abbiano divisori in comune, dimostriamolo per x(n+2)
x(n+2)= (x(n))^4 + 2 – 4(x(n))2
E’ evidente che x(n) non divide nemmeno x(n+2) perché se così fosse dovrebbe dividere anche il 2, ma x(n) non è mai pari per come è costruita la successione.
Per induzione, dunque, x(n) non divide mai un qualsiasi x(n+k) (c.v.d.)

Purtroppo così come la metti la dimostrazione non funziona. Il problema è che tu dici di voler dimostrare che x(n) non ha fattori comuni con x(n+k) per ogni k, e questo andrebbe bene. Però, poi, quello provi a dimostrare per induzione è solo che x(n) è primo con x(n+1). In effetti c'è un problema anche in questo perchè il tuo passo induttivo è: se x(n) è primo con x(n+1), allora è primo anche con x(n+2) (mentre per fare quest'induzione servirebbe di concludere che x(n+1) è primo con x(n+2)).

Credo che quello che ti fa fare confusione sia la presenza di due variabili (n e k). L'induzione come la vuoi fare te dovrebbe essere così. Fissiamo n.
1) Passo base. x(n) è primo con x(n+1). Questo è un enunciato a parte, a sua volta potrebbe essere dimostrato per induzione su n (e questa è più o meno l'induzione che provavi a fare tu)
2) Passo induttivo. Se x(n) è primo con x(n+k), allora x(n) è primo con x(n+k+1). Qui è fissato n e aumentiamo k ad ogni passo.

Comunque non so se sia facile fare una dimostrazione per induzione dell'esercizio (proprio perché ci sono due variabili e probabilmente servirebbe una doppia induzione). Un piccolo suggerimento, se conosci un po' le congruenze. Prova a ragionare modulo p, dove p è un primo qualunque.

In bocca al lupo!

E' sufficiente mostrare che, per ogni $ n,k\in\mathbb{N}^+ $: $ \gcd(x_n, x_{n+k}) = 1 $. Banalmente $ x_{n+1} \equiv -2 \bmod x_n $. Se poi k > 1, allora $ x_{n+k} = (\ldots ((x_n^2 - 2)^2 - 2)^2 + \ldots - 2)^2 - 2 $, dove si innestano esattamente k-1 ordini di parentesi. Pertanto ancora $ x_{n+k} \equiv 2 \bmod x_n $. Da qui $ \gcd(x_n, x_{n+k}) = \gcd(x_n, 2) $, in base all'algoritmo di Euclide per il calcolo del massimo comun divisore. Senonché $ x_n $ è dispari, per ogni $ n\in\mathbb{N}^+ $, e perciò $ \gcd(x_n, 2) = 1 $.