L’algorithme d’Euclide : Calculer le PGCD entre deux entiers

Dans cet article, nous allons vous présenter l’algorithme d’Euclide, un algorithme qui permet de calculer le PGCD entre deux entiers

Prérequis

• La division euclidienne
• Le PGCD

La méthode de l’algorithme d’Euclide

Le principe repose sur la propriété suivante : PGCD(a,b) = PGCD(b,r) où r est le reste de la division euclidienne de a par b. On peut supposer que l’on travailler avec des entiers positifs.

On définit cet algorithme par une récurrence double :

• r_0 = a et r_1 = b
• Pour tout n \geq 1, r_{n+1} est le reste de la division euclidienne de r_{n-1} par r_n

D’un point de vue algorithmique, voici comment l’algorithme d’Euclide est défini :

fonction euclide(a, b)
    tant que b ≠ 0
       t := b; 
       b := a modulo b; 
       a := t; 
    retourner a

On vous propose aussi une version récursive

fonction euclide(a, b)
    si b = 0 alors retourner a
    sinon retourner euclide(b, a modulo b)

Application au PGCD

Le PGCD est le dernier reste non nul lorsqu’on applique l’algorithme d’Euclide.

Exemple de calcul de l’algorithme d’Euclide

Calculons le PGCD entre 30 et 21 :

• Tout d’abord, 30 = 21 \times 1 + 9
• Puis, 21 = 9 \times 2 + 3
• Et enfin, 9 = 3\times 3 +0

La méthode en vidéo

Nous vous proposons aussi de voir le calcul en vidéo :

Quelques exercices pour vous entrainer

Calculer les PGCD des nombres suivants :

• 110 et 130
• 264 et 206
• 2040 et 6120
• 152 et 165
• 210 et 330
• 882 et 588