Cours Stage - PGCD, algorithme d'Euclide

PGCD de 2 entiers et algorithme d'Euclide

Accède gratuitement à cette vidéo pendant 7 jours Profite de ce cours et de tout le programme de ta classe avec l'essai gratuit de 7 jours !

Fiche de cours

PGCD de 2 entiers et algorithme d'Euclide

 

Définition

 

On considère deux entiers $a$ et $b$.

On appelle alors PGCD de $a$ et de $b$ le plus grand des diviseurs communs à $a$ et à $b$.

 

Exemple

Si l'on veut déterminer le PGCD de $8$ et de $12$. Il faut chercher les diviseurs de ces deux entiers

$8$ a pour diviseurs : $\{1;2;4;8\}$

$12$ a pour diviseurs : $\{1;2;3;4;6;12\}$

On en déduit que le plus grand diviseur commun à $8$ et $12$ est $4$.

 

Algorithme d'Euclide

 

Lorsqu'on manipule des entiers relativement grands, comme 1015 et 714 par exemple, on peut trouver leur PGCD en appliquant l'algorithme d'Euclide.

L'algorithme d'Euclide fonctionne de la manière suivante :

  • Si $a$ est un entier alors $PGCD(a,0)=a$
  • Si $a$ et  sont deux entiers (avec $a>b$)  et si $r$ est le reste de la division euclidienne de $a$ par $b$ alors $PGCD(a;b)=PGCD(b;r)$

On commence par écrire la division euclidienne du plus grand des deux entiers par le plus petit.

Ici supposons que $a>b$ :

On écrit a sous la forme : $a =  b\times q  + r$ où r est le reste de la division euclidienne de $a$ par $b$ et $q$ le quotient.

Ensuite, on écrit la division euclid

Il reste 70% de cette fiche de cours à lire
Cette fiche de cours est réservée uniquement à nos abonnés. N'attends pas pour en profiter, abonne-toi sur lesbonsprofs.com. Tu pourras en plus accéder à l'intégralité des rappels de cours en vidéo ainsi qu'à des QCM et des exercices d'entraînement avec corrigé en texte et en vidéo.