Arithmétique

[aminovic]

comment montrer que PGCD((2^a -1),(2^b -1)) = 2^PGCD(a,b) -1 ?

[Bouchra]

Bonsoir,
essaie avec l'algorithme d'Euclide.

[sandrine_guillerme]

Bonsoir,
essaie avec l'algorithme d'Euclide.

Bonsoir ..

Euh, chui pas sure .. ? :hein:

C'est immédiat, non ? C'est même la déf du PGCD non?

[aminovic]

J’ai essayé de monter que chacun des deux divise l’autre …J’ai montrer que 2^PGCD(a,b) -1 divise PGCD((2^a -1),(2^b -1)) mais pour l’inverse j’ai pas pu
et je n sais pas comment utiliser l'algorithme d'Euclideds ds ce cas ?

[aviateurpilot]

avec cette methode qui ressemble à
on arrive facilement à avec r dernier rest non nul dans l'algorithme d'euclide sur a et b
donc r=pgcd(a,b)

N.B: il faut on a pas le droit d'ecrire sauf si

[Bouchra]

C'est immédiat, non ? C'est même la déf du PGCD non?

Je vois pas pourquoi c'est direct ..??

aminovic,
on a même :
on suppose b>a



...


Via Euclide, on a :



De plus:

= ...

Et on montre que est le reste de la div. eucl. de par

ainsi:

= ....

Et on conclut.

[sandrine_guillerme]

Oui j'ai du dire une bêtise ..

Désolée..

[Bouchra]

Mais y a pas à être desoled (comme dirait mon prof de maths..)
N'empêche, il peut y avoir une autre solution dans ce cas particulier c=2 ..

[aminovic]

ok je vois , merci

[Bouchra]

De rien.
Et au fait bienvenue !