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

Utilise le fait que : le reste de 2^a - 1 sur 2^b - 1 est 2^r - 1 .. Ou r est le reste de la division euclidienne de a sur b ..



Ps : Pourquoi tu poste le sujet 2 fois !!

mercii encore !!!

juste de rassuré la rép!!!
!!

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

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

Facile ..


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

2^(r-1) n est pas toujour un reste mais il verifie 2^r-1 congrua 2^a-1 mod 2^b-1

on note : PGCD(a;b) = d
et PGCD( 2^a - 1 , 2^b - 1) = D
on peut démontrer facilement que si m divise n donc ( a ^m - 1 ) divise ( a^n - 1 ) pour tout m;n et a de N.
on a : d / a et d / b
par conséquent : ( 2^d - 1 ) / ( 2^a - 1 ) et ( 2^d - 1 ) / ( 2^b - 1 )
donc ( 2^d - 1 ) / D.
on a d = PGCD(a;b)
donc il existe u et v tel que au+bv = d
on a 2^a = 1 (mod) D et 2^b =1 (mod)D
donc 2^au = 1 (mod) D (1)
et 2^bv =1 (mod)D (2)
en multipliant (1) et (2) on obtient 2^(au+bv) = 1 (mod) D
et alors D / ( 2^d - 1 )
enfin D = ( 2^d - 1 )