Répondre à la discussion
Affichage des résultats 1 à 2 sur 2

Démonstration de l'algorithme d'Euclide.



  1. #1
    EaGle58

    Démonstration de l'algorithme d'Euclide.


    ------

    Bonjour,

    Je viens de trouver ce site:
    http://www.uel.education.fr/consulta...itre1-6det.htm
    Il y a écrit que rk-1 divise rk-2, mais je ne comprends pas pourquoi c'est le PGCD de a et b.
    Qk divise aussi rk-2 donc pourquoi ce n'est pas le PGCD?

    -----

  2. #2
    supernico999

    Re : Démonstration de l'algorithme d'Euclide.

    Salut
    On a pgcd(r_i+2,_ri+1)=pgcd(r_i+1,r _i) pour tout i.
    Donc comme ils disent, "de proche en proche" on obtient pgcd(a,b)=pgcd(b,r1)=...=pgcd( r_k-2,r_k-1)=r_k-2

    De façon générale, si tu fais la division euclidienne de a par b: a=bq+r avec 0<=r<b alors tu as pgcd(a,b)=pgcd(b,r).
    Ca vient du fait que d divise a et b si et seulement d divise b et r (ça se voit facilement).

Sur le même thème :

Discussions similaires

  1. Complexité de l'algorithme de Shor
    Par Argyre dans le forum Discussions scientifiques
    Réponses: 14
    Dernier message: 19/11/2009, 18h26
  2. [Maths] [TS] Arithmétique : algorithme d'Euclide
    Par kNz dans le forum Exercices pour les concours et examens
    Réponses: 4
    Dernier message: 17/11/2006, 22h06
  3. algorithme d'Euclide, pgcd TS
    Par alpha_diese dans le forum Mathématiques du collège et du lycée
    Réponses: 5
    Dernier message: 16/11/2006, 15h26
  4. Non au système d'Euclide !
    Par FrB dans le forum Discussions scientifiques
    Réponses: 13
    Dernier message: 25/11/2004, 12h05
  5. L'algorithme ultime
    Par boardingman dans le forum Discussions scientifiques
    Réponses: 52
    Dernier message: 30/08/2004, 09h07