G4 problema 25

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

Moderatore: tutor

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

Messaggioda lordgauss » 01 gen 1970, 01:33

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>

Torna a “[vecchio forum]Giornalino della Matematica”

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite