OliForum Matematico

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

Io mi gioco il lemma di Knuth, e chiudo la partita con la vittoria in tasca!!!

e che cos'è il Lemma di Knuth?? Cmq chi vuole (anche tu hit) può fare l'esercizio che si può fare anke usando solo banalissima teoria dei numeri...

Il lemma di Knuth è banalissima (...) Teoria dei Numeri!!!

Per favore, puoi dirmi cos'è questo lemma di knuth allora, mi hai incuriosito!

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...

ho cercato la dimostrazione del lemma di knuth. è abbastanza caotica (e ci metterei un anno a riportarla con il LaTeX), ma non difficile. penso sempre di aver bisogno di un aggiornamento sulla teoria dei numeri, perché so pochissimo...

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

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!!!

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) $.

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?!?

Ehm...sei d'accordo che detti $ m=cm_1 $ e $ n=cn_1 $ con $ n_1\leq m_1 $ esistono numeri naturali x e y tali che $ m_1x-n_1y=1 $?

Sì. Solo mi chiedo perché tu non sia stato altrettanto preciso quand'era necessario...

Ok avete risolto quello più facile... Ora fate l'altro che è più interessante..