Accueil » Publications » Le Bulletin Vert » Spécial journées » Autour du PGCD
  APMEP   Autour du PGCD

Article du bulletin 483

- 9 mars 2016 -

Henri Lombardi

Résumé de l’article

L’auteur définit d’abord l’anthyphérèse, algorithme qui unifie l’algorithme d’Euclide (qui aboutit au PGCD) et l’algorithme des fractions continues (qui n’aboutit que si longueur et largeur sont commensurables). Puis il énonce deux théorèmes : Théorème 1 : Si a et b sont 2 entiers >0, le plus grand diviseur commun g>0 de a et b est multiple de tout autre diviseur commun et théorème 2 : Si a et b sont 2 entiers >0, il existe un entier g>0 de la forme ua+vb (avec u et v entiers relatifs), qui divise a et b. (L’égalité g= ua+bv s’appelle relation de Bezout entre les entiers a et b). Il démontre le deuxième théorème par la méthode abstraite classique puis par algorithme et compare les deux preuves, la deuxième ayant l’avantage de fournir le solution. Une étude plus approfondie montre que la preuve classique cache aussi un algorithme et permet aussi d’obtenir la solution.

Plan de l’article

  • 1. L’anthyphérèse
  • 2. Le théorème du pgcd
  • 3. Une preuve abstraite classique
  • 4. Une preuve par algorithme
  • 5. Comparaison des deux preuves
  • 6. La preuve classique cache-t-elle un algorithme ? OUI !

Télécharger l’article en pdf dans son intégralité

(Article mis en ligne par Armelle BOURGAIN)
 Accueil   Plan du site   Haut de la page   Page précédente