PGCD Du deux nombres Mersennes!!!! urgent!!

démontré ke

Pgcd(2^a -1 , 2^b -1) = 2^d -1

d=pgcd(a,b)

Merciiiii davance !!

au pif....
la division euclidien de a par b donne l'existence d'un nique couple (q,r) tel que 0=<r<b et a=bq+r.

2^a-1=(2^b-1)Q+(2^r-1)

(pour trouver Q il suffit de developper 2^a-2^r)
ainsi de suite,avec le procédé de euclide tu obtient le resutat voulu.

Bjr !

Utilise Le Fait que : Le reste de la division Euclidienne de 2^a -1 Sur 2^b -1 est 2^r -1 ( Facile a demontrer ) .. Ou r est le Reste de la division euclidienne de a sur b ..

Dsl Redouane , J'ai pas vu ton message !!

merciiiiii bcp
mtn je voi!!!^^

dsl rodouane é mouad mééé comment on démontré

Le reste de la division Euclidienne de 2^a -1 Sur 2^b -1 est 2^r -1??

a=bq+r Donc 2^a - 1 = 2^(bq+r) -1 = 2^(bq).2^r -1 = (2^(bq) -1).2^r +2^r -1

Or : x^n - 1 = (x-1)(x^(n-1) + ..... + 1)
--> 2^(bq) - 1= (2^b - 1)(........................)

Donc : 2^a - 1= (2^b - 1)(.................).2^r + 2^r-1

Pose : q=(.................).2^r ===> 2^a - 1= (2^b - 1)q + 2^r-1