Comment calculer le PGCD avec l’algorithme d’Euclide ?

Rédac des Sherpas - Mis à jour le 04/07/2022
comment calculer le pgcd avec l'algorithme d'euclide

Tu ne sais pas comment calculer le PGCD de deux nombres facilement ? Euclide, un grand mathématicien de la Grèce Antique, a trouvé une méthode imparable. Dans ce cours, apprends à calculer le PGCD avec l’algorithme d’Euclide.

Théorème : Théorème d’Euclide

Soient deux entiers relatifs a et b. On suppose b \in\mathbb{N}^*. On note q et r le quotient et le reste de la division de a par b. Alors :

    \[    $a \wedge b = b \wedge r$. \]

Démonstration :

Par définition de r et b, on a : a = bq+r. On note \mathscr{A} l’ensemble des diviseurs communs de a et b et \mathscr{R} l’ensemble des diviseurs communs de r et b. Montrons que \mathscr{A} = \mathscr{R} par double inclusion. Soit d \in\mathscr{R}, comme a = bq + r et que d divise r et b, on en déduit que d divise aussi a et donc d \in\mathscr{A}, d’où l’inclusion \mathscr{R} \subset \mathscr{A}. Soit d \in\mathscr{A}, comme r = a-bq et que d divise a et b, on en déduit que d divise aussi r et donc d \in\mathscr{R}, d’où l’inclusion \mathscr{A} \subset \mathscr{R}. En conclusion, \mathscr{A} = \mathscr{R} Ces deux ensembles ont donc le même plus grand élément, soit : a \wedge b = b \wedge r.

Corollaire : L’algorithme d’Euclide

Voici un algorithme qui permet de déterminer le PGCD de deux entiers non nuls a et b. Pour cela, on définit une suite (r_n)_{n\in\mathbb{N}} :
  • On pose r_0 = a et r_1 = b ;
  • Tant que r_k \ne 0, on effectue la division euclidienne de r_{k-1} par r_k et on note r_{k+1} le nouveau reste obtenu.
  • Le PGCD de a et b est le dernier terme de la suite (r_n)_{n\in\mathbb{N}} non nul.

    Remarque :

    Si on note n le premier entier naturel tel que r_n = 0, le théorème d’Euclide nous permet d’écrire que :

        \[    $r_0 \wedge r_1 = r_1 \wedge r_2$ = ... = r_{n-1} \wedge r_n$. \]

    Or, r_{n-1} \wedge r_n = r_{n-1} \wedge 0 = r_{n-1}.

    Exemple :

    Déterminons le PGCD de 2020 et 150 en utilisant l’algorithme d’Euclide :

    r_0 = 2020
    2020 = 150 \times 13 + 70,
    150 = 70 \times 2 + 10,
    70 = 10 \times 7 + 0
    et r_1 = 150
    donc r_2 = 70
    donc r_3 = 10
    donc r_4 = 0
    Le dernier reste non nul est r_3, donc 2020 \wedge 150 = 10
    livre maths mpsi vuibert

    Cet article est extrait de l’ouvrage Maths MPSI-MP2I. Tout-en-un : cours, méthodes, entraînement et corrigés (éditions Vuibert, juin 2021) écrit par E. Thomas, S. Bellec, G. Boutard. ISBN n°9782311408720

    3/5 - (2 votes)
    profile picture
    Rédac des Sherpas
    La Rédac des Sherpas, c'est près de 100 auteurs passionnés d'éducation qui mettent leur expertise à ta disposition pour t'aider à profiter pleinement de tes études. Étudiants, profs particuliers ou spécialistes : avec eux, tu es sûr d'avoir les meilleurs conseils ! ⚡️

    Laisse-nous un commentaire !

    Des questions ? Des bons plans à partager ? Nous validons ton commentaire et te répondons en quelques heures ! 🎉

    ebook

    Notre ebook pour réussir ta prépa

    Télécharge notre guide et découvre comment réussir tes années en prépa grâce à nos conseils et nos méthodes ! 👩🏻‍🎓