3 problemi (tdn)

[TomSawyer1]

1) Dimostrare che $(F_n,F_m)=1$, per qualsiasi $n$ diverso da $m$, quando $F_n$
denota l'n-esimo numero di Fermat (dedurre anche l'infinità dei numeri primi).

2)Dimostrare che $(F_n,F_(n+1))=1$, quando $F_n$ denota l'n-esimo numero di Fibonacci.

3) Dimostrare che se $2^m+1$ è primo, allora $m=2^n$, per qualche $n,m in NN$.

[fields1]

3) L'ordine di $2$ modulo $2^m+1$ è $2m$. Infatti $2^m+1=0 (mod 2^m+1)$ e dunque $2^m=-1 (mod 2^m+1)$. Poiché $2^(m+i)= -2^i (mod 2^m+1)$ e inoltre $2^(2m)=1 (mod 2^m+1)$, segue facilmente che l'ordine di $2$ modulo $2^m+1$ è $2m$. Poiché $2^m+1$ è primo, per il teorema di Fermat, $2^(2^m)=1 (mod 2^m+1)$. Di conseguenza $2m | 2^m$ e dunque $m | 2^(m-1)$ e dunque $m=2^n$ per qualche $n\in NN$.

[Aethelmyth]

Uhm ieri sera ci stavo pensando e credo di aver trovato un modo utilizzando congruenze modulo 3 e 5 ... ora non ho la testa per comprendere bene la tua soluzione ne per ricordare la mia

[fu^2]

"Crook":
2)Dimostrare che $(F_n,F_(n+1))=1$, quando $F_n$ denota l'n-esimo numero di Fibonacci.

lo si fa facilmente col metodo di induzione questo

[TomSawyer1]

La soluzione del terzo è chiaramente giusta..

"fu^2":[quote="Crook"]
2)Dimostrare che $(F_n,F_(n+1))=1$, quando $F_n$ denota l'n-esimo numero di Fibonacci.

lo si fa facilmente col metodo di induzione questo [/quote]

Il secondo è molto facile, sì. Comunque, posta la soluzione, magari.

[Sk_Anonymous]

"Crook":2) Dimostrare che $(F_n,F_(n+1))=1$, quando $F_n$ denota l'n-esimo numero di Fibonacci.

Banale: se m, n sono interi non negativi, allora $gcd(F_n,F_m) = F_{gcd(m,n)}$ (lemma di Lucas). Peraltro, è mia la generalizzazione (sulle pagine dell'AMM) di questo e di un altro risultato (associato al nome di Knuth), per aver provato che "se a, b sono numeri REALI distinti tali che a+b ed ab siano entrambi interi, allora i) $(a^n-b^n)/(a-b)$ è anch'esso intero, per ogni $n \in NN$ e ii) $gcd((a^m - b^m)/(a-b), (a^n-b^n)/(a-b)) = (a^{gcd(m,n)} - b^{gcd(m,n)})/(a-b)$, per ogni $m, n \in NN$. Fiqo, no?

EDIT: dannato MathMl...

[Sk_Anonymous]

"Crook":1) Dimostrare che $(F_n,F_m)=1$, per qualsiasi $n$ diverso da $m$, quando $F_n$
denota l'n-esimo numero di Fermat (dedurre anche l'infinità dei numeri primi).

Banale: per ogni $n \in NN$, vale $F_n = 2 + \prod_{k=0}^{n-1} F_k$ (per induzione). Wlog, supposto perciò $m < n$, vale $gcd(F_n, F_m) = gcd(2,F_m) = 1$, secondo l'algoritmo di Euclide. Poiché $F_n > 1$, per ogni $n \in NN$, l'insieme dei fattori primi che dividono almeno un termine della successione $\{F_n\}$ è infinito, viz esistono infiniti numeri primi.

[fu^2]

questa è una fimostrazione che ho provato a afer un pò alternativa... non so se è correttissima, ma volevo provare qualcosa di diverso da quella classica per induzione:-D


allora prima di dimostrare la tesi, dimostro che ogni due "posti" dispari c'è un "posto" pari...

la serie di fibonacci è
1,1,2,3,5,8,...

$a_1=1
$a_2=1
$a_3=2
...


sappiamo che numero pari si può scrivere cm 2k
mentre un numero dispari come 2k+1

quindi sle combinazioni di valori che possono assumere a(n) e a(n+1) sono tre
$a_n=2k
$a_(n+1)=2k

però questo non possiamo accettarlo, in quanto se fossero due pari, tutta la serie dovrebbe essere composta da numeri pari, ma il proimo termine è dispari e quindi non possiamo accettarla.

o

$a_n=2k+1
$a_(n+1)=2k+1
$a_(n+2)=a_n+a_(n+1)=2k+1+2k+1=4k+2$ che è un numero pari

o

$a_n=2k
$a_(n+1)=2k+1
$a_(n+2)=a_n+a_(n+1)=2k+2k+1=4k+1$ che è un numero dispari

notere che se calcoliamo $a_(n+3)$ nel secondo caso otteniamo un numero dispari per il terzo caso e se lo calcoliamo nel terzo caso otteniamo un numero pari per il secondo caso e così all'infinito...

ora...

PASSIAMO AL QUESITO

$(a_(n),a_(n+1))$=$(a_(n-2)+a_(n-1),a_(n-1)+a_(n))$

quindi come dimostrato prima possiamo scrivere, ipotizzando che $a_(n-1)$ è dispari

$(2k+1+2k+1,2k+1+2k)$=$(4k+2,4k+1)$ l'MCD tra 4k+2 e 4k+1 è soltanto 1, l'ipotesi è dimostarta. giusto?

[Sk_Anonymous]

"Crook":3) Dimostrare che se $2^m+1$ è primo, allora $m=2^n$, per qualche $n,m in NN$.

Sia $m = 2^n \cdot q$, dove $n, q \in NN$ e q = 1 mod 2. Allora $2^m + 1 = (2^{2^n} + 1) \sum_{k=0}^{q-1} (-1)^k 2^{2^n \cdot k}$. Se $q > 1$, la sommatoria a seconda membro è $> 1$, e perciò $2^m + 1$ è composto, poiché prodotto di due interi positivi entrambi $> 1$.

[TomSawyer1]

Non conoscevo l'identità per $2^m+1$, molto utile.

[Sk_Anonymous]

"Crook":Non conoscevo l'identità per $2^m+1$, molto utile.

In realtà, sono (quasi) certo che non ti è assolutamente nuova: per ogni $a, b \in RR$ ed ogni $p \in N$, è vero infatti (più in generale) che $a^p - b^p = (a - b) \cdot \sum_{k=0}^{p-1} a^{p-k} b^k$. Ponici $a = 2^{2^n}$, $b = -1$ e $p = q$, essendo $n, q \in NN$ e q = 1 mod 2, e ricavane l'identità a cui ti riferisci.

[TomSawyer1]

"fu^2":$(a_(n),a_(n+1))$=$(a_(n-2)+a_(n-1),a_(n-1)+a_(n))$

quindi come dimostrato prima possiamo scrivere, ipotizzando che $a_(n-1)$ è dispari

$(2k+1+2k+1,2k+1+2k)$=$(4k+2,4k+1)$ l'MCD tra 4k+2 e 4k+1 è soltanto 1, l'ipotesi è dimostarta. giusto?

Ci sono errori abbastanza gravi. Li hai visti?

[fu^2]

no... scusa potresti indicarmi dov'è l'errore o dove sono gli errori?... grazie

[TomSawyer1]

Tu sostituisci ad $a_(n-2)+a_(n-1)$ questo: $2k+1+2k+1$. Il primo errore è nel dire che $a_(n-2)$ sia dispari. Il secondo è che non si tratta dello stesso $k$!

[fu^2]

dispari o pari poco cambia... perchè se è fosse stato pari sarebbe stato dispari dall'altra parte..
mentre la questione del K è vero, non ci avevo pensato.. ero troppo soddisfatto per la mia dimostrazione che ho pensato.. son negato per queste cose

[TomSawyer1]

"fu^2":dispari o pari poco cambia... perchè se è fosse stato pari sarebbe stato dispari dall'altra parte..

Non è vero che cambia poco. Tu ipotizzi che $a_(n-1)$ sia dispari, quindi $a_(n-2)$ è pari.

[fu^2]

no ogni 2 dipari c'è uno pari, quindi $a_(n-2)$ può benissimo essere dispari

[TomSawyer1]

Sì, è vero, ero convinto che avessi considerato come dispari $a_n$.