Una cosuccia su Mersenne e Fermat

euler_25 · Messaggio da **euler_25** » 01 gen 1970, 01:33

Ho già proposto questo problema nella sezione \"Facile facile sui primi di Fermat\" aperta da Pazqo, ma evidentemente è passata inosservata... in ogni caso, ecco di seguito il problema:
 
 \"dimostrare che i numeri di Fermat sono a due a due primi fra loro e quindi estendere la medesima proprietà a tutti i numeri di Mersenne M[p] per i quali p sia un numero primo.\"
 
 Salvo alias euler_25
 
 -----------------------------------------------------------------------------------------
 
 \"Every prime number is one of my best friends\" - Srinivasa

WindowListener · Messaggio da **WindowListener** » 01 gen 1970, 01:33

Dimostriamo che i numeri della forma 2^(2^n) + 1 sono primi tra loro, procediamo per assurdo:
 supponiamo esista un primo p tale che 2^(2^n)+1 = 0 mod p
 2^(2^k) +1 = 0 mod p
 
 allora avremo 2^(2^n) = -1 mod p
 2^(2^k) = -1 mod p
 
 supponiamo n > k allora n = k + h da cui
 2^(2^n) = 2^[(2^k)(2^h)] = [2^(2^k)]^(2^h) = -1 mod p ----> (-1)^(2^h) = -1 mod p
 questa equazione ha soluzione solo se h = 0 quindi n = k , I numeri di Fermat sono primi tra loro.
 
 Consideriamo l\'insieme dei resti modulo p ( dove p e\' primo) privato dello 0 , questo insieme con l\'operazione di moltiplicazione e\' un gruppo. Sia G = <2> G e\' ciclico e essendo sottogruppo 1 che in questo caso e\' l\'identita\' e\' contenuto in G. Si dimostra facilmente che in tale struttura se 2^a = 1 mod p possiamo avere solamente due casi o a e\' il piu\' piccolo numero tale che 2^k = 1 mod p o a e\' multiplo di tale numero.
 
 quindi tornando al problema se avessimo due numeri di Mersenne che sono divisibili per uno stesso primo p, si avra\'
 (x,y sono numeri primi)
 
 2^x = 1 mod p
 2^y = 1 mod p
 
 allora per quanto detto prima o x e\' il minimo numero (>0) tale che soddisfi proprieta\' voluta o e\' un numero non primo , quindi vale la prima possibilita\' , analogamente si ragiona con y , ma essendo entrambi primi x = y .............

euler_25 · Messaggio da **euler_25** » 01 gen 1970, 01:33

Eccellente! [ Questo Messaggio è stato Modificato da: euler_25 il 16-12-2003 11:41 ]

euler_25 · Messaggio da **euler_25** » 01 gen 1970, 01:33

Dopo Mersenne e Fermat, siccome vi scopro interessati, ho deciso di proporvi una serie di 4 nuovi problemi su due altre celeberrime sequenze di numeri ampiamente studiati in campo Matematico...
 
 ---------------
 
 i) Per ogni n intero positivo, sia Pn(&#8729<IMG SRC="images/forum/icons/icon_wink.gif"> il polinomio di variabile reale definito assumendo, per ogni x€R:
 
 Pn(x) := x^(n+2) - x^(n+1) - Fn*x - Fn - 1
 
 ove {Fn} denota la successione dei numeri di Fibonacci.
 Calcolare il quoziente e il resto della divisione di Pn(x) per il trinomio di secondo grado: x^2 - x - 1.
 
 ---------------
 
 ii) Trovare una trasformazione lineare L(&#8729<IMG SRC="images/forum/icons/icon_wink.gif">: R^2 ---> R^2 tale che, per ogni n€N: L(Fn,Ln) = (Fn + 1,Ln + 1), ove {Ln} ed {Fn} indicano, rispettivamente, le successioni dei numeri di Lucas e Fibonacci.
 
 ----------------
 
 iii) Sia {Fn(x)} la successione dei polinomi di Fibonacci, definita assumendo, per ogni x€R: F0(x) = 0, F1(x) = 1 ed Fn(x) = x*Fn - 1(x) + Fn - 2(x), per ogni n ≥ 2. Dimostrare che, comunque fissato un n intero positivo o nullo:
 
 int[0..+infty] 1/[(x^2 + 1)*F2n+1(2x)] dx = Pi/(4n + 2)
 
 ----------------
 
 iv) Dimostrare che ogni intero positivo ammette una e una sola rappresenta-zione di Zeckendorf, ovvero è esprimibile in modo unico come somma di termini distinti e non consecutivi della successione {fn} definita assumendo, per ogni n intero positivo o nullo: fn = Fn + 2, ove {Fn} denota l\'ulteriore successione dei numeri di Fibonacci.
 
 ----------------
 
 Buon lavoro a tutti! Salvo Tr. <IMG SRC="images/forum/icons/icon_smile.gif"> [ Questo Messaggio è stato Modificato da: euler_25 il 20-12-2003 22:46 ]

lordgauss · Messaggio da **lordgauss** » 01 gen 1970, 01:33

Mi pare che dopo il parossismo iniziale, il rapporto con euler sia generalmente diventato costruttivo.
 Continuo a pensare che certe escursioni in una matematica un po\' troppo superiore siano fuori luogo in questo forum, ma ognuno valuterà da sè.
 
 Ciò che trovo positivo è che euler ponga anche questioni di matematica elementare o olimpica che dir si voglia.
 
 Per dimostrare la mia buona volontà, passo ad affrontare il problema 4) di quelli proposti, che è abbastanza immediato nonostante varie imprecisioni nel testo <IMG SRC="images/forum/icons/icon_wink.gif">
 
 TESI 1: ogni intero positivo si può scrivere come somma di numeri di Fibonacci distinti e non consecutivi.
 
 NOTA: nel testo che euler ha postato si dice \"interi non negativi\", in realtà la tesi vale solo per quelli positvi: se infatti si ammettesse la presenza dello 0 e si considerasse 0 un numeri di Fibonacci, dimostrata questa tesi 1, esisterebbero per ogni intero positivo almeno due rappresentazioni: una senza 0 ed una con lo 0.
 
 Ragioniamo per induzione estesa.
 
 i) 1 = F[1]
 
 ii) Supponiamo che tutti gli interi da 1 a n-1 siano rappresentabili come somma di numeri di Fibonacci non consecutivi. Mostriamo che allora lo è anche n.
 Sia F[k] il massimo numero di Fibonacci minore o uguale a n. Ovviamente deve essere F[k] > n/2, poichè altrimenti 2F[k] <= n < F[k+1], da cui 2F[k] < F[k+1] = F[k]+F[k-1], assurdo.
 Pertanto n-F[K] è un intero minore di F[k]. Per ipotesi induttiva, esso è somma di numeri di Fibonacci distinti. Dunque anche n = (n-F[k]) + F[k] lo è.
 Inoltre nella rappresentazione di n-F[k] non ci sono numeri di Fibonacci consecutivi: se in quella di n ci fossero, non potrebbero che essere F[k] e F[k-1]. Ma in tal caso n>=F[k] + F[k-1] = F[k+1], assurdo.
 
 TESI 2: tale rappresentazione è unica per ogni intero positivo.
 
 Questa tesi è FALSA. basti l\'identità (dimostrabile agevolmente per induzione) SUM(i=1...n) F[2i-1] = F[2n].
 
 Occorre un\'ipotesi aggiuntiva: per esempio, essa può essere che l\'intero positivo non debba essere un numero di Fibonacci di indice pari.
 
 In questo caso, supponiamo per assurdo che la tesi sia falsa e sia n il minimo intero per cui essa non vale. Nelle due sommatorie che costituiscono le due distinte rappresentazioni non compaiono termini uguali, che altrimenti si potrebbero elidere, in contraddizione con il fatto che n sia minimo.
 Mantenendo il significato dato nella tesi 1, in una rappresentazione comparirà F[k]. Ora, distinguiamo due casi:
 - se k=2j, allora la somma che non contiene F[k] vale al più F[2j-1] + F[2j-3] + ... + F[1] = F[k], che è minore di n (per l\'ipotesi aggiuntiva che abbiamo fatto).
 - se k=2j+1, allora la somma che non contiene F[k] vale al più F[2j] + F[2j-2] + ... + F[2] = F[k]-1, che è minore di n (anche l\'dentità usata ora è facilmente dimostrabile per induzione).
 
 In ambedue i casi la somma non contenente F[k] è minore di n, il che è assurdo. Dunque la rappresentazione di n come somma di numeri di Fibonacci è unica.

lordgauss · Messaggio da **lordgauss** » 01 gen 1970, 01:33

Sì, il testo porta ad oscurità anche perchè F[1]=F[2]=1, e la funzione F[n] non è iniettiva... ok, comunque sono solo dettagli fuorvianti.

Antimateria · Messaggio da **Antimateria** » 01 gen 1970, 01:33

Se poniamo F[1]=1, F[2]=2, etc funziona tutto. Anzi, da questo deriva il lemma che dice F[n]-1 = F[n-1]+F[n-3]+F[n-5]..., che è il motivo per cui esiste l\'espressione unica di ogni intero positivo.
 
 Infatti, siccome il più grande numero esprimibile come somma di numeri di Fibonacci tra F[1] e F[n] non consecutivi è F[n]+F[n-2]+F[n-4]+..., e siccome per il lemma questa somma vale esattamente F[n+1]-1, la tesi è dimostrata immediatamente per induzione.[addsig]

Messaggio da **ma_go** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 ii) Trovare una trasformazione lineare L(&#8729<IMG SRC="images/forum/icons/icon_wink.gif">: R^2 ---> R^2 tale che, per ogni n€N: L(Fn,Ln) = (Fn + 1,Ln + 1), ove {Ln} ed {Fn} indicano, rispettivamente, le successioni dei numeri di Lucas e Fibonacci.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 ok, io vedo di \"eliminare\" questo qui: chiamiamo p e q le soluzioni di x²-x-1 = 0, con p>q.
 ora, è noto che i numeri di fibonacci si scrivono nella forma:
 Fn = [pn-qn]/sqrt5
 forse è meno noto sapere che i numeri di lucas (definiti analogamente ai fibonacci, con L0 = 2, L1 = 1) si scrivono nella forma:
 Ln = pn+qn.
 ora, risultano evidenti le identità:
 pn = [Ln + Fn·sqrt5]/2
 qn = [Ln - Fn·sqrt5]/2.
 da queste si ricava, in base alle identità sopracitate:
 
 Fn+1 = [pn+1-qn+1]/sqrt5 = {p[Ln + Fn·sqrt5]/2 - q[Ln - Fn·sqrt5]/2}/sqrt5 = Ln/2 + Fn/2
 
 Ln+1 = pn+1+qn+1 = p[Ln + Fn·sqrt5]/2 + q[Ln - Fn·sqrt5]/2 = Ln/2 + 5Fn/2.
 
 quindi abbiamo trovato le trasformazioni lineari cercate...
 
 un prof mi ha suggerito un altro metodo: una trasformazione lineare si associa ad una matrice quadrata del secondo ordine Q (in questo caso) e soddisfa Q(a+b) = Qa +Qb.
 ora, sfruttando le identità di base dei fibonacci e dei lucas, si dimostra che se esiste tale trasformazione, essa soddisfa un paio di identità (ottenute lavorando solo sui primi tre fibonacci + lucas) e si ricava il tutto senza calcoli pq-osi... <IMG SRC="images/forum/icons/icon_smile.gif">
 
 dovrei aver fatto anche il primo, ma devo ricontrollare i conti.

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

forse mi sbaglio, ma mi sembra che Euler volesse una trasformazione lineare in due variabili (da R2 in R2)...

Messaggio da **ma_go** » 01 gen 1970, 01:33

scusa, ma tu quante ne conti??? <IMG SRC="images/forum/icons/icon_eek.gif">

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

uhm...
 chiedo venia, mi sa di aver confuso trasformazione lineare con funzione <IMG SRC="images/forum/icons/icon_smile.gif">

Biagio · Messaggio da **Biagio** » 01 gen 1970, 01:33

qualcuno ha un bel sito da consigliarmi, possibilmente in italiano, sui numeri di fibonacci e le loro proprietà?

euler_25 · Messaggio da **euler_25** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2003-12-18 17:26, lordgauss wrote:
 Per dimostrare la mia buona volontà, passo ad affrontare il problema 4) di quelli proposti, che è abbastanza immediato nonostante varie imprecisioni nel testo <IMG SRC="images/forum/icons/icon_wink.gif">
 
 TESI 1: ogni intero positivo si può scrivere come somma di numeri di Fibonacci distinti e non consecutivi.
 
 NOTA: nel testo che euler ha postato si dice \"interi non negativi\", in realtà la tesi vale solo per quelli positvi: se infatti si ammettesse la presenza dello 0 e si considerasse 0 un numeri di Fibonacci, dimostrata questa tesi 1, esisterebbero per ogni intero positivo almeno due rappresentazioni: una senza 0 ed una con lo 0.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Molto attento! I miei complimenti! Davvero bravo! Vorrà dire, my Lord, che per il futuro mi toccherà d\'essere un tantino più attento di quanto non sia già stato finora... a buon rendere, dunque! <IMG SRC="images/forum/icons/icon_wink.gif">
 A parte ogni presunzione, non mi capita spesso di lasciarmi cogliere in fallo su questioni inerenti la Matematica, e ancor meno mi avviene di dover riconoscere incondizionatamente i miei errori in proposito! Ma nel tuo caso, beh, non ho sinceramente argomenti da usare in mia difesa... <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif"> <IMG SRC="images/forum/icons/icon27.gif">
 
 --
 
 Ciò detto, devo tuttavia dissentire con alcune considerazioni promosse da Antimateria e pertinenti la corretta definizione della successione di Fibonacci {Fn}. Questa infatti, come giustificato da tutta una serie di motivazioni che non sto qui a ripetere per ragioni di brevità (consiglio in ogni caso, a chiunque volesse approfondire, di visitare in proposito il sito ufficiale del Fibonacci Quaterly, previa una ricerca su Google del suo url o di un link qualsiasi a quelle medesime pagine), si costruisce ricorsivamente assumendo F0 := 0, F1 := 1 ed Fn := Fn - 1 + Fn - 2, per n >= 2, e questo non è assolutamente in discussione! Dunque, il modo più corretto di rimediare alla 2a delle imprecisioni contenute nella traccia del problema (iv) e prontamente evidenziate da Lord non è certo di ridefinire la successione di Fibonacci assumendo F0 := 1, F1 := 2 ed Fn := Fn - 1 + Fn - 2, per n >= 2, dacché questo comporterebbe la perdita di altre notevoli proprietà che solo la prima scelta può (di converso) garantire! D\'accordo? Piuttosto, si potrebbe riformulare il problema nei termini che lo stesso Gauss ha provveduto di suggerire, e ai quali conformerò pertanto la traccia del quesito di cui qui si discute. Ciao!
 
 Salvo Tr.
 
 P.S.: sono molto contento d\'aver visto Antimateria interessarsi in qualche modo ai problemi che ho postato su questo forum! Al di là degli screzi e delle divergenze di idee che in passato abbiam potuto avere, tieni ben fermo in quella zucca vuota che ti ritrovi, o mio diletto Antimateria, ch\'io per te nutro una stima profonda e inopinabile! E di questo, almeno, prova a non sorridere mai! <IMG SRC="images/forum/icons/icon_cool.gif">
 --------
 
 Per Biagio: ti consiglio di dare un\'okkiata a questo url:
 
 http://www.mcs.surrey.ac.uk/Personal/R. ... i/fib.html
 
 Sebbene il sito non sia ineccepibile sotto il profilo dell\'organizzazione delle idee e delle informazioni, tuttavia ne fornisce molte e molto variegate! Da questo punto di vista, è davvero una chicca... nel suo genere!
 
 [ Questo Messaggio è stato Modificato da: euler_25 il 19-12-2003 23:54 ] [ Questo Messaggio è stato Modificato da: euler_25 il 20-12-2003 00:08 ]

Antimateria · Messaggio da **Antimateria** » 01 gen 1970, 01:33

Ok Euler, non intendevo ridefinire la successione di Fibonacci. Quello che intendevo fare era formulare il teorema in questo modo:
 
 Ogni intero non negativo si può esprimere in modo unico come somma di numeri di Fibonacci non consecutivi, i cui indici non siano 0 (F0=0) e 1 (F1=1).
 [allo 0 si può far corrispondere l\'insieme vuoto]
 
 Mi pare infatti che così sia molto più elegante che non imporre che il numero non sia del tipo F2n, e metta a disposizione la semplice dimostrazione che ho abbozzato nel post precedente.

euler_25 · Messaggio da **euler_25** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2003-12-20 01:55, Antimateria wrote:
 ...Ogni intero non negativo si può esprimere in modo unico come somma di numeri di Fibonacci non consecutivi, i cui indici non siano 0 (F0=0) e 1 (F1=1).
 [allo 0 si può far corrispondere l\'insieme vuoto]
 
 Mi pare infatti che così sia molto più elegante che non imporre che il numero non sia del tipo F2n, e metta a disposizione la semplice dimostrazione che ho abbozzato nel post precedente.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Beh, in questo caso, mi trovi assolutamente d\'accordo! <IMG SRC="images/forum/icons/icon_wink.gif">