G4 problema 25

Commenti e suggerimenti sull'iniziativa del "Giornalino della Matematica"

Moderatore: tutor

Bloccato
lordgauss
Messaggi: 478
Iscritto il: 01 gen 1970, 01:00
Località: Brunswick

Messaggio da lordgauss »

Con F(n) indichiamo l\'(n+1)-esimo numero di Fibonacci. Occorre dimostrare che MCD(F(n),F(m))=F(MCD(n,m))
<BR>
<BR>
<BR>Partiamo con il dare per scontata la seguente semplice proprietà: F(n)=F(0)+F(1)+F(2)+…+F(n-2)+1. Dimostriamo ora i seguenti Lemmi [ometto qui la dimostrazione dei primi 3 lemmi, altrimenti non si finisce più di leggere. Li lascio come erano originariamente, anche se qui 1 e 3 possono essere ragguppati, e il 2 non lo usiamo perchè è utile solo nella dimostrazione del 3.].
<BR>
<BR>Lemma 1
<BR>Se n==0 (mod m), ovvero n=km con k naturale, allora F(n)==0 (mod F(m)).
<BR>
<BR>Lemma 2
<BR>Per ogni n naturale, F(n) è primo con F(n+1)
<BR>
<BR>Lemma 3
<BR>Se F(n)==0 (mod F(m)) allora n==0 (mod m), ovvero: gli unici numeri di Fibonacci F(n) tali che F(n)==0 (mod F(m)) sono del tipo F(jm).
<BR>
<BR>
<BR>Lemma 4
<BR>Per tutti gli a, b naturali MCD(F(a),F(b)) = F(r), per un certo r naturale. Ovvero, il MCD tra due numeri di Fibonacci è sempre un numero di Fibonacci.
<BR>Proviamo la tesi per induzione. Senza perdere in generalità potremo supporre a>=b.
<BR>
<BR>I.
<BR>Per a=1, MCD(F(a),F(b))=MCD(F(1),F(0))=MCD(F(1),F(1))=F(1).
<BR>
<BR>II.
<BR>Supponiamo che per ogni a minore o uguale a j e per ogni b si abbia MCD(F(a),F(b))=F(r). Mostriamo che la tesi è valida anche per a=j+1. Poniamo ora j+1=b+s. Ricordando che
<BR>
<BR>F(j+1)=F(0)+F(1)+F(2)+…+F(j-1)+1
<BR>
<BR>abbiamo che MCD(F(j+1),F(b)) è uguale a
<BR>
<BR>MCD(F(0)+F(1)+…+F(b)+..+F(b+s-2)+1, F(b))
<BR>
<BR>che, per la stessa proprietà, è uguale a
<BR>
<BR>MCD(F(b)+F(b-1)+F(b)+F(b+1)+…+F(b+s-2), F(b)),
<BR>
<BR>che, eliminando i due F(b), è a sua volta uguale a
<BR>
<BR>MCD(F(b-1)+F(b+1)+…+F(b+s-2), F(b)).
<BR>
<BR>Per ciò che abbiamo detto nel Lemma 1, per ogni k naturale si ha che
<BR>F(b+k)==F(b-1)*F(k) (mod F(b)).
<BR>Pertanto, ancora modulo F(b),
<BR>
<BR>F(b-1)+F(b+1)+..+F(b+s-2)==F(b-1)+F(b-1)*F(1)+F(b-1)*F(2)+..+F(b-1)*F(s-2) =
<BR>
<BR>= F(b-1)*(1+F(1)+F(2)+…+F(s-2)) = F(b-1)*F(s).
<BR>
<BR>Quindi in definitiva MCD(F(j+1),F(b)) = MCD(F(b-1)*F(s), F(b)). Ma per il Lemma 2 F(b-1) e F(b) non hanno fattori in comune e dunque MCD(F(b-1)*F(s), F(b)) = MCD(F(s),F(b)) che per ipotesi induttiva è un numero di Fibonacci, visto che s è minore di j+1.
<BR>
<BR>Dimostrazione del teorema
<BR>A questo punto possiamo facilmente dimostrare che F(MCD(a,b)) = MCD(F(a),F(b)). Si ponga r=MCD(a,b). Allora per il Lemma 1 si ha che F(r)|F(a) e F(r)|F(b). Dimostriamo che F(r) è proprio MCD(F(a),F(b)).
<BR>A tal fine supponiamo invece che MCD(F(a),F(b))=F(t), con t>r. Allora per il Lemma 3 avremmo che t|a e t|b, il che è assurdo perché allora r non sarebbe MCD(a,b).
<BR>Quindi F(r) = MCD (F(a),F(b)), ovvero la tesi.
<BR><BR><BR><font size=1>[ Questo Messaggio è stato Modificato da: lordgauss il 2002-03-26 18:16 ]</font>
Bloccato