Autour du PGCD

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)