1) ok, est divisible par

2) soit ,
divisible par
divisible par

donc divise

reste à montrer l'inverse

3) divisible par donc n'est pas premier

1/ OK, ce que tu as fait est bon

2/
il est clair que 2^pgcd(a;b) - 1 divise les deux termes d'après le 1/
il reste à prouver que c'est le plus grand diviseur

3/
par contraposition,
a non premier => il existe c tel que c divise a et donc 2^c - 1 divise 2^a - 1 d'après le 1/ ... CQFD

il reste le 2/

merci pour vos 2 réponses

en fait je ne voyais pas bien comment de me servir de la première partie que j'avais démontré mais là je vois

donc si je résume le 3/

on montre par contraposition

on suppose a non premier, donc il existe c tel que c/a donc a=ck

donc 2^a-1= 2^ck-1 qui d'après le 1/ est divisible par 2^c-1 ou par 2^k-1
donc 2^a-1 n'est pas premier

pour le 2/

pour montrer l'égalité il faut donc que je montre que pgcd (2^a-1, 2^b-1) divise 2^pgcd(a,b)-1 et inversement

donc un sens est facile avec le 1/ (celui que dont vous parlez)

soit d= pgcd(a,b)
d/a et d/b donc a=da' et b=b'd

donc 2^a-1= 2^da'-1=(2^d)^a'-1^a'= (2^d-1)(...)
de meme 2^b-1= 2^db'-1=(2^d)^b'-1^b'= (2^d-1)(...)

donc 2^d-1 divise pgcd(2^a-1,2^b-1)

il faut montrer maintenant que pgcd(2^a-1,2^b-1) divise 2^d-1

...

est-ce-que si je fais le cas où a et b sont premiers entre eux et le cas où ils ne le sont pas c'est une bonne piste ?

merci

si on réusiit à montrer que : "a et b premier entre eux => 2^a-1 et 2^b-1 premiers entre eux", alors c'est gagné  

Bonjour,

a = bq + r  donc  2^a-1 = (2^bq -1)2^r + 2^r -1 = (2^b-1)A(b,q) + 2^r-1

où  A(b,q) est un entier.  Donc  pgcd (2^a-1, 2^b-1) =  pgcd (2^b-1), 2^r-1) et je te laisse poursuivre

joli, lolo271  

merci c un grand classique on peut remplacer  2 par n'importe quel entier

désolé j'ai pas tout compris la solution de Lolo271..

2^a-1 = (2^bq -1)2^r + 2^r -1 ça c'est ok

mais je vois pas trop ce que c'est que A(b,q) ?

on factorise (2^bq -1) en (2^b-1)(...)

et donc le A(b,q) correspondrait au polynome (...) de la factorisation . 2^r ??

ensuite je vois bien que le pgcd(2^a-1, 2^b-1)=pgcd(2^b-1,2^r-1)

mais je vois pas que faire de ça... r c'est le reste donc il est unique et < à b non ?

merci par avance

en notant ab le pgcd de a et de b, on a
ab=br
c'est le crible d'Erasthotène qui permet de déterminer ab
et comme (2^a-1)(2^b-1)=(2^b-1)(2^r-1), on a le même crible donc (2^a-1)(2^b-1)=2^(ab)-1

Bonjour,

désolé j'ai eu beau reprendre mon cours je ne vois pas comment de (2^a-1)(2^b-1)=(2^r-1)(2^b-1) (que je comprend) déduire avec le crible que (2^a-1)(2^b-1)=2^ab-1...

rappelle toi que ab = br = etc... et que c'est grâce à cette succession de divisions qu'on obtient le pgcd (lorsque le reste est nul)

il te suffit de rappeler que tu as obtenu   (2a-1)(2b-1)=(2r-1)(2b-1) parce que a = bq+r pour conclure que cette succession d'égalités s'arrêtera lorsque tu auras atteint le pgcd et un reste de 1 donc que auras 2^pgcd-1 1=2¹-1