une formule qui sert a calculer le pgcd ! nice exo!

salut !
montrer que

pgdc(a;b)=a+b-ab+2sigma(E(k*a/b)) k varie de 1 à b-1

E c'est la partie entiere ok bonne chance

supposons a=dp et b=dq , d'ou d=PGCD (a,b) et PGCD(p,q)=1
on a pour la pertie entiére :
. 2
P,q premier entre eux , l'ensemble des résidus modulo q , de meme pour qp,(q+1)p,(q+2)p ,......, (2q-1)p !
les residus modulo q ==> 0,1,2,.....,q-1 d'ou leur somme est
q(q-1)/2 , puisque il y a d partie alors la somme est dq(q-1)/2
et la partie décimale : dq(q-1)/2q
d'ou


S= ab-a-b+PGCD(a,b) ==> PGCD(a,b)=a+b-ab-S

BJR à Toutes et Tous !!!

La Formule est belle certes et présente un travail HEURISTIQUE sur le plan mathématique ....
Je ne la connaissais pas du tout .....
Dans la pratique , elle est difficilement mise en oeuvre surtout lorsque a et b sont TRES GRANDS !!
En fait , rien ne vaut l'inusable Algorithme d'EUCLIDE que l'on peut faire à la main ou en Programme Informatique à l'aide de Logiciels de Calcul Symbolique .....

LHASSANE

bien joué master ! oui cette formule a ete decouverte en 1997 par Marcelo pollezzi !

slt , belle methode , mais just une faute de frappe je crois qu'il ya un 2 pour la deuxieme sigma (ligne 2 ) ^^!

En effet, j'avais remarqué ça aussi...
Sinon comme a dit Bison_Fûté cette méthode n'est pas très pratique surtout si les nombres sont très grands, ya pa mieux que l'algorithme d'Euclide, mais cette formule est bien à connaître tout de même...

svp comment

@ ayoub :
a=[a]+{a} (la somme de la partie entiére+parie décimale)
P.S : t'a oublié le 2 !!

oui exactement