PGCD, PPCM et algorithme d'Euclide : Cours de Mathématiques 2BAC Sciences Mathématiques, chapitre Arithmétique dans ℤ
PGCD, PPCM et algorithme d'Euclide : notion du chapitre Arithmétique dans ℤ du programme de maths 2BAC SM, expliquée pas à pas, avec 2 exemples guidés. Pour les élèves de 2BAC SM A et SM B, option française (BIOF).
Notions du cours (11)
Apprendre avec Burhan
PGCD, PPCM et algorithme d'Euclide
Étape 1 sur 3PGCD et PPCM
Vérifie : Le plus grand diviseur commun

Quel est le plus grand entier naturel qui divise à la fois et ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :
Faux.
divise bien et , mais ce n'est pas le plus grand diviseur commun.
Choix B :
Faux.
est le plus petit multiple commun non nul, pas un diviseur commun : il dépasse .
Choix C :
Faux.
est un diviseur commun, mais il oublie le facteur , commun aux deux.
Choix D :
Juste.
divise et , et aucun diviseur de plus grand que ne divise .
Besoin d'aide ? Indice 1
Liste les diviseurs positifs de , puis garde ceux qui divisent .
Voir la correction complète
Les diviseurs positifs de sont , , , , , , , , , , et .
Parmi eux, ceux qui divisent sont , , , , et . Le plus grand est .
En 1BAC, tu as noté ce nombre : c'est le PGCD. Le plus petit multiple commun non nul se note : c'est le PPCM. Voici les définitions exactes.
DéfinitionPGCD et PPCM
Soient et deux entiers relatifs non tous les deux nuls. Le plus grand commun diviseur de et est le plus grand entier naturel qui divise à la fois et ; on le note . Si et sont tous les deux non nuls, le plus petit commun multiple de et est le plus petit entier naturel non nul qui est à la fois un multiple de et un multiple de ; on le note .

ExempleQuatre calculs
- : le signe ne change pas les diviseurs.
- .
- , car tout entier divise .
- : leur seul diviseur commun positif est .

Étape 2 sur 3PGCD et reste
Cherche . On écrit . Un diviseur commun à et divise . À l'inverse, un diviseur commun à et divise .
Pourquoi est-ce utile ? On remplace le couple par un couple plus petit, sans changer le PGCD.
PropriétéPGCD et division euclidienne
Soient un entier relatif, un entier naturel non nul, et le reste de la division euclidienne de par . Les diviseurs communs à et sont exactement les diviseurs communs à et . En particulier, ; si , alors .
Démonstration
Étape 1. On écrit (« Division euclidienne dans ℤ »). Si et , alors (« Propriétés de la divisibilité », point 2).
Étape 2. Si et , alors (« Propriétés de la divisibilité », point 2).
Étape 3. Les deux ensembles de diviseurs communs sont donc égaux ; ils ont le même plus grand élément positif : . Si , les diviseurs communs à et sont les diviseurs de , dont le plus grand est : donc .

Vérifie : Quelle égalité en découle ?

On a . Laquelle de ces égalités découle de la propriété précédente ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :
Juste.
On garde le diviseur et on remplace par le reste .
Choix B :
Faux.
On garde le dividende au lieu du diviseur. D'ailleurs , alors que .
Choix C :
Faux.
est le quotient : il n'intervient pas. Ici , alors que .
Voir la correction complète
Avec , et , la propriété donne . On recommence : , donc .
Étape 3 sur 3L'algorithme d'Euclide
On peut répéter ce remplacement. Les restes diminuent strictement et restent positifs : ils finissent par s'annuler.
Pourquoi le dernier reste non nul est-il le PGCD ? Chaque division conserve le PGCD, jusqu'au dernier couple , et .
PropriétéAlgorithme d'Euclide
Soient et deux entiers naturels non nuls. On pose et , puis, tant que , on note le reste de la division euclidienne de par . Il existe un rang tel que et , et alors Le PGCD de et est le dernier reste non nul.
Démonstration
Étape 1 (l'algorithme s'arrête). Tant que les restes sont non nuls, on a , car chaque reste est strictement inférieur au diviseur (« Division euclidienne dans ℤ »). Une suite strictement décroissante d'entiers naturels ne peut pas avoir plus de termes : un reste finit par être nul.
Étape 2. Soit le rang tel que et . Par « PGCD et division euclidienne » appliqué à chaque division, pour .
Étape 3. De proche en proche (récurrence sur ), .

Méthodel'algorithme d'Euclide en tableau
- Ranger : on divise le plus grand entier par le plus petit, sur une ligne du tableau.
- Décaler : le diviseur devient le dividende, le reste devient le diviseur.
- S'arrêter au premier reste nul, et lire le reste de la ligne précédente.
Rédaction attendue. « D'après l'algorithme d'Euclide, est le dernier reste non nul. » Chaque ligne respecte l'encadrement du reste.

ExempleExemple guidé : 391 et 299
| dividende | diviseur | quotient | reste |
|---|---|---|---|
Le dernier reste non nul est . D'après l'algorithme d'Euclide, . Garde ce tableau : il resservira dans la section suivante.

← Étape précédenteFin de la notion
S'entraîner sur cette notion
Sources du cours
- Référentiel BURHAN du chapitre « Arithmétique dans ℤ » (2bac · sciences-mathematiques · mathematiques)
