Calcolare:
- $ \gcd (2^n-1,2^m-1) $
- $ \gcd (2^n+1,2^m+1) $
con $ n,m \in \mathbb{N}_0 $
N.B.: gcd(a,b) sarebbe la notazione inglese di MCD(a,b) infatti gcd è l'acronimo di greatest common divisor
Massimo comun divisore
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara
E ze ti dicessi di "no", Zimo?!? Eddai, zuvvia, non pvendevtela... Pvova a capivmi: ze adesso ti enuncio il lemma di Knuth (btw, non penzave neppuve lontamente di contattavmi tvamite i messaggi pvivati... 
), levo agli altvi utenti il piaceve di confvontarzi con il tuo pvoblema. Zu, cavo, pazienta... E mentve pazienti, stvaziati puve: la cuviozità quazi uccide la gente che, a buon divitto, cede al zuo fascino maliavdo. Lo zo pev ezpevienza... 
), levo agli altvi utenti il piaceve di confvontarzi con il tuo pvoblema. Zu, cavo, pazienta... E mentve pazienti, stvaziati puve: la cuviozità quazi uccide la gente che, a buon divitto, cede al zuo fascino maliavdo. Lo zo pev ezpevienza... Ammesso che noi ci si riferisca allo stesso lemma, ti dirò, pps... So esibirne due differenti proof, e né l'uno né l'altro sono più caotici delle corrispettive dimostrazioni del lemma di Euclide per il massimo comun divisore e del lemma di Lucas per i numeri di Fibonacci, per cui... Qui bisognerebbe un pochettino accordarsi sul senso dei qualificativi, temo e suppongo!!! 
Visto che qui sembrano tutti più interessati a sapere il Lemma di Knuth che non a risolvere il problema, ci provo io:
Sia $ a=(2^n-1,2^m-1) $ da qualche prova numerica salta all'occhio che il massimo comun denominatore è $ b=2^{ged(m,n)}-1 $, dimostriamolo:
Intanto è facile vedere che b|a, infatti detto $ c=(m,n) $ abbiamo:
$ 2^n-1=2^{cn_1}-1=(2^c-1)(2^{cn_1-1}+2^{cn_1-2}+...+1) $ e lo stesso per $ 2^m-1 $ dunque $ 2^c-1 $ divide entrambi i termini e quindi divide $ a $.
Ora $ c=xm-yn $ e $ a|(2^n-1) $ dunque $ a|(2^{yn}-1) $ e
$ a|(2^m-1) $ dunque $ a|(2^{mx}-1) $.
Ne segue che $ a|(2^{yn}(2^c-1)) $ ma chiaramente a non divide $ 2^{yn} $ e quindi la tesi.
Ciao
Sia $ a=(2^n-1,2^m-1) $ da qualche prova numerica salta all'occhio che il massimo comun denominatore è $ b=2^{ged(m,n)}-1 $, dimostriamolo:
Intanto è facile vedere che b|a, infatti detto $ c=(m,n) $ abbiamo:
$ 2^n-1=2^{cn_1}-1=(2^c-1)(2^{cn_1-1}+2^{cn_1-2}+...+1) $ e lo stesso per $ 2^m-1 $ dunque $ 2^c-1 $ divide entrambi i termini e quindi divide $ a $.
Ora $ c=xm-yn $ e $ a|(2^n-1) $ dunque $ a|(2^{yn}-1) $ e
$ a|(2^m-1) $ dunque $ a|(2^{mx}-1) $.
Ne segue che $ a|(2^{yn}(2^c-1)) $ ma chiaramente a non divide $ 2^{yn} $ e quindi la tesi.
Ciao
P. Andrea
Ok, adesso che Pixel ha proposto finalmente una soluzione del problema, beh... credo di poter svelare il mistero del lemma di Knuth, enunciandolo per Simo e per chiunque altro gli fosse interessato. 
Lemma di Knuth: per ogni $ m,n\in\mathbb{N} $ ed ogni $ a\in\mathbb{Z} $: $ \gcd(a^m - 1, a^n - 1) = a^{\gcd(m,n)} - 1 $.
Bon, confermo quanto detto all'inizio: questa partita era chiusa già alla prima mano!!!
Lemma di Knuth: per ogni $ m,n\in\mathbb{N} $ ed ogni $ a\in\mathbb{Z} $: $ \gcd(a^m - 1, a^n - 1) = a^{\gcd(m,n)} - 1 $.
Bon, confermo quanto detto all'inizio: questa partita era chiusa già alla prima mano!!!
Uhm... Vediamo se ho capito! Per il lemma di Bezout, esistono $ x, y\in\mathbb{Z} $ tali che: $ mx - ny = c =: \gcd(m,n) $, dico bene?!? Ecco, se questi sono i fatti, lascia che ti sottolinei come gli interi $ x $ ed $ y $ così determinati possono essere pure entrambi negativi... In che modo dunque ti riesce di scrivere una relazione del tipo: $ a \mid (2^{yn}-1) $, se il dividendo potrebbe persino non essere un numero intero?!?Pixel ha scritto: Ora $ c=xm-yn $ e $ a|(2^n-1) $ dunque $ a|(2^{yn}-1) $ e $ a|(2^m-1) $ dunque $ a|(2^{mx}-1) $.
-
Simo_the_wolf
- Moderatore
- Messaggi: 1053
- Iscritto il: 01 gen 1970, 01:00
- Località: Pescara