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

Rédac des Sherpas - Mis à jour le 04/07/2022
234124

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$. \]

    \[    $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
  • 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 ! 👩🏻‍🎓