Accélérer l'algorithme d'Euclide

[Anonyme]

a et b désignent deux nombres entiers naturels tel que a>b.La division euclidienne de a par b donne l'existence d'un unique couple (q;r) de nombres entiers naturels tel que a=bq+r avec 0Dans la division de a par b,on nomme r le reste par défaut et r'=b(q+1)-a,le reste par excès.
Ainsi r+r'=b

a)Démonter que les diviseurs communs à a et b sont les mêmes que les diviseurs communs à a et r'.
b)En déduire un algorithme qui permet d’accélérer celui d’Euclide.
c)Avec c'est deux algorithmes,déterminer: PGCD(435,548
d)Démontrer qu'avec ce nouvel algorithme,chaque reste est inférieur ou égal à la moitié du précédent.
e)k désigne l'exposant de la plus haute puissance de 2 inférieure ou égale a b.Démontrer que le nombre d'étapes de l'algorithme est inférieur ou égal à k+1.

J'ai réussi a faire la a) mais je n'arrive pas a faire la suite.Si quelqu'un pouvait m'aider,merci :)

[Ben314]

Bonsoir.
Tu as du voir en cours que la méthode "normale" pour l'algo. d’Euclide, c'est de constater que les diviseurs de a et b sont les mêmes que les diviseurs communs à a et r.
Çà permet de dire que pgcd(b,a)=pgcd(a,r) [puis on recommence en divisant a par r et ainsi de suite]

Là, vu ce que tu vient de montrer, ça veut dire qu'on a aussi pgcd(b,a)=pgcd(a,r')
Donc on pourrait faire tout l'algo. en prenant les r' à la place des r (mais on y gagnerais quoi ?)
Ou, à la limite, le plus malin, c'est sans doute de prendre des fois r et des fois r' pour essayer de gagner du temps.
A un moment donné, lequel vaut il mieux prendre ?

(si tu veut essaye sur 2 ou 3 exemple "concret" pour voir)

[Anonyme]

Bonsoir.
Tu as du voir en cours que la méthode "normale" pour l'algo. d’Euclide, c'est de constater que les diviseurs de a et b sont les mêmes que les diviseurs communs à a et r.
Çà permet de dire que pgcd(b,a)=pgcd(a,r) [puis on recommence en divisant a par r et ainsi de suite]

Là, vu ce que tu vient de montrer, ça veut dire qu'on a aussi pgcd(b,a)=pgcd(a,r')
Donc on pourrait faire tout l'algo. en prenant les r' à la place des r (mais on y gagnerais quoi ?)
Ou, à la limite, le plus malin, c'est sans doute de prendre des fois r et des fois r' pour essayer de gagner du temps.
A un moment donné, lequel vaut il mieux prendre ?

(si tu veut essaye sur 2 ou 3 exemple "concret" pour voir)

J'ai pas compris compris lorsque vous dites '' des fois r et des fois r' "