Inscription / Connexion Nouveau Sujet
Niveau Prepa (autre)
Partager :

Équation pgcd

Posté par
matheux14
03-04-22 à 21:25

Bonsoir,

Merci d'avance.

Montrer que \forall (n ; m) \in \N² :

\Large{pgcd(2^n -1 ~;~ 2^m - 1) = 2^{pgcd(n ~;~ m)} -1}

Une piste ?

Posté par
GBZM
re : Équation pgcd 03-04-22 à 21:59

Bonsoir,

Quel est le reste dans la division euclidienne de 2^n-1 par 2^m -1 ?

Posté par
matheux14
re : Équation pgcd 03-04-22 à 22:47

2m-n

Posté par
matheux14
re : Équation pgcd 03-04-22 à 22:50

Oups c'est plutôt 2n-m-1.

2n - 1 = 2n-m+(2m -1) + 2n-m -1

Posté par
matheux14
re : Équation pgcd 03-04-22 à 23:03

matheux14 @ 03-04-2022 à 22:50

Oups c'est plutôt 2n-m-1.

2n - 1 = 2n-m(2m -1) + 2n-m -1

Posté par
UnAlgerien39
re : Équation pgcd 03-04-22 à 23:08

Bonjour,

au lieu de + c'est x au deuxième membre de l'égalité
2n - 1 = 2n-m+(2m -1) + 2n-m -1

Posté par
matheux14
re : Équation pgcd 03-04-22 à 23:12

Oui je l'ai corrigé à 23 : 03

Posté par
GBZM
re : Équation pgcd 04-04-22 à 07:18

C'est sur la voie (avec pas mal de coquilles !), mais ce n'est pas encore une division euclidienne.

Posté par
matheux14
re : Équation pgcd 04-04-22 à 12:10

Pourquoi ?

Posté par
GBZM
re : Équation pgcd 04-04-22 à 14:30

Parce que rien ne dit que le "reste" 2^{n-m}-1 est plus petit que le diviseur 2^m-1.



Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Inscription gratuite

Fiches en rapport

parmi 1510 fiches de maths

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !