Annuler
connectez vous
arithmétique en post-bac
- Arithmétique dans Z - supérieur
- Exercice : le petit théorème de Fermat
- Équations différentielles : un Cours complet avec des exemples
- Généralités sur les matrices, applications linéaires, changement de base, rang d'une matrice - supérieur
- Ensemble et application Partie II
- Un best-of d'exos de probabilités (après le bac)
- Espaces vectoriels et Applications linéaires - supérieur
Inscription / Connexion Nouveau Sujet
Accueil l'île des mathématiques Forum de mathématiquesListe de tous les forums de mathématiques SupérieurOn parle exclusivement de maths, pour le supérieur principalement, les BTS, IUT, prépas... Autre ArithmétiqueTopics traitant de arithmétique [tout]Lister tous les topics de mathématiques
Niveau autre
démonstration lemme du PGCD de Knuth
Posté par Olivier B (invité)
Bonjour,
Comment démontrer que (2^a-1,2^b-1)=2^(a,b)-1 ?
(x,y) signifie bien entendu le PGCD de x et y...
Je dois résoudre cet exercice mais je n'ai vraiment aucune idée de comment procéder... J'ai cherché longtemps mais aucune idée de comment faire..
J'ai trouvé quelques pages sur Google, mais tout ce qu'elles m'ont appris c'est le nom de cette identité (lemme de Knuth), j'ai bien trouvé une démonstration, mais elle est incomplète, en anglais, et assez difficile à comprendre à mon niveau (je suis en 4ème secondaire en Belgique, en France je crois que ça correspond à la 3ème, la classe où on est quand on a 15-16 ans quoi...).
L'énoncé me donne une aide en disant de supposer a plus grand que b et de considérer la division euclidienne de a par b.. mais ça ne m'a pas beaucoup fait avancer.
Voila, si quelqu'un pourrait m'indiquer une piste ça m'aiderait beaucoup... Merci.
Olivier.
Posté par jmg1 (invité)début de réponse
Suggestion: j'ai essayé aussi la piste de la division euclidienne mais j'avoue ne pas avoir trouvé. A défaut j'ai un début de démonstration imparfaite à proposer en utilisant la base 2
2^a-1 s'écrit 1 répété a fois (id pour 2^b)
on voit facilement que 2^(a,b)-1 divise 2^a-1 et 2^b-1 (en effet il y a répétition du motif 1 répété (a,b) fois dans les 2 cas. Exemple:
a=4 b=6
2^a-1= '1111' et 2^b-1='111111' 2^(a,b)-1='11'
il suffit de multiplier 2^(a,b)-1 par '101' at '10101' pour retomber sur 2^a-1 et 2^b-1.
En généralisant si a=(a,b)*p et b=(a,b)*q alors
2^a-1=[2^(a,b)-1]*[somme (i variant de 1 à p) des 2^(i*(a,b)-1)]
formule similaire pour b avec q au lieu de p
il reste à vérifier que 2^(a,b)-1 est le plus grand diviseur...
Bonsoir Olivier B,bonsoir jmg1;
Olivier B,connais-tu l'alghorithme d'euclide pour la détérmination du PGCD de deux entiers ?
Posté par jmg1 (invité)lien sur une démonstration complète
Voila un lien complet utilisant en effet la méthode d'euclide pour la démo du lemme (2nde partie de la démo).
http://les-mathematiques.u-strasbg.fr/phorum/read.php?f=2&loc=0&i=198619&t=198619
Personnellement je trouve que c'est un peu exagéré de considérer ca comme du niveau 15/16 ans...