Mathématiques - arithmétique

arithmétique
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: aminovic

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

Posted by: Bouchra

Bonsoir,
essaie avec l'algorithme d'Euclide.

Posted by: sandrine_guillerme

Citation:

Posté par Bouchra

Bonsoir,
essaie avec l'algorithme d'Euclide.

Bonsoir ..

Euh, chui pas sure .. ?

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

Posted by: 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 ?

Posted by: aviateurpilot

$4$ f(n)=2^n-1$
$4$ pgcd(f(a),f(b))=pgcd(2^a(2^{b-a}-1),2^a-1)=pgcd(f(b-a),f(a))$
avec cette methode qui ressemble à $4$ pgcd(x,y)=pgcd(x-y,y)$
on arrive facilement à $4$ pgcd(f(a),f(b))=f(r)$ 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 $f(b-a)$ sauf si $b\ge 0$

Posted by: Bouchra

Citation:

Posté par sandrine_guillerme

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 : $pgcd(c^a-1,c^b-1) = c^{pgcd(a,b)} - 1$
on suppose b>a
$b = q_1 a + r_1$
$a =r_1 q_2 + r_2$
$r_1 = r_2 q_3 + r_3$
...
$r_{n-1} = r_n q_{n+1}$

Via Euclide, on a :
$pgcd(a,b)=pgcd(a,r_1)=...=pgcd(r_n,0)=r_n$

De plus:

$3$ c^b-1 = c^{ q_1 a + r_1 } - 1 = c^{q_1 a} c^{r_1} -1 <br /> = c^{q_1 a} c^{r_1} -1 + c^{r_1} - c^{r_1}$ = ...

Et on montre que $c^{r_1} - 1$ est le reste de la div. eucl. de $c^b-1$ par $c^a-1$

ainsi:
$pgcd(c^a-1,c^b-1)=pgcd(c^a-1,c^{r_1}-1)$
= ....

Et on conclut.

Posted by: sandrine_guillerme

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

Désolée..

Posted by: 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 ..

Posted by: aminovic

ok je vois , merci

Posted by: Bouchra

De rien.
Et au fait bienvenue !