Algorithme d'Euclide : Cours de Mathématiques 1BAC Sciences Mathématiques, chapitre Arithmétique dans ℤ
Algorithme d'Euclide : notion du chapitre Arithmétique dans ℤ du programme de maths 1BAC SM, expliquée pas à pas, avec 3 exemples guidés. Pour les élèves de 1BAC Sciences Mathématiques, option française (BIOF).
Notions du cours (13)
Apprendre avec Burhan
L'algorithme d'Euclide
Étape 1 sur 4Répéter la division
Devine : Des divisions en cascade

On écrit , puis , puis , et enfin . D'après la propriété précédente, que vaut ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :
Faux.
est le premier reste ; or ne divise pas .
Choix B :
Faux.
ne divise pas : ce n'est pas un diviseur commun.
Choix C :
Juste.
Juste : c'est le dernier reste non nul.
Choix D :
Faux.
est le dernier reste, et un PGCD n'est jamais nul.
Voir la correction complète
La propriété « PGCD et division euclidienne » s'applique à chaque ligne : .
Pourquoi est-ce vrai ? Chaque division conserve le PGCD. Et les restes sont des entiers naturels qui décroissent strictement : un reste nul finit par apparaître.
ThéorèmeAlgorithme d'Euclide
Soient un entier relatif et un entier naturel non nul. On pose et on note le reste de la division euclidienne de par . Pour , tant que , on note le reste de la division euclidienne de par .
Il existe un rang tel que , et est le dernier reste non nul : .
Démonstration
Étape 1 (arrêt). Chaque reste est positif ou nul et strictement inférieur au diviseur de sa division (division euclidienne) : tant que les restes sont non nuls, . Des entiers naturels strictement décroissants à partir de sont au plus . Un reste nul apparaît donc, avec .
Étape 2 (PGCD). D'après la propriété « PGCD et division euclidienne » appliquée à la première division, . Appliquée à chaque division suivante, elle donne . De proche en proche, (PGCD et division euclidienne).

À retenirRetenir de la preuve : l'algorithme d'Euclide
Deux idées portent la preuve. Le PGCD se conserve d'une division à la suivante. Et une suite d'entiers naturels strictement décroissante est finie : l'algorithme s'arrête. On lit alors le PGCD dans la dernière division : .

Vérifie : L'arrêt

Pourquoi l'algorithme d'Euclide s'arrête-t-il toujours ?
Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.
Choix A :Parce que les quotients finissent par devenir nuls.
Faux.
À partir de la deuxième division, : chaque quotient est au moins égal à .
Choix B :Parce que les restes sont des entiers naturels strictement décroissants.
Juste.
Juste : une telle suite ne peut pas continuer indéfiniment.
Choix C :Parce que chaque reste est au plus la moitié du précédent.
Faux.
C'est faux en général : donne le reste , plus grand que la moitié de .
Choix D :Parce que le premier reste divise toujours .
Faux.
Pour et , le premier reste ne divise pas .
Voir la correction complète
Chaque reste est positif ou nul et strictement inférieur au diviseur de sa division. Tant que les restes sont non nuls, . Une telle suite d'entiers naturels ne peut pas continuer indéfiniment : un reste nul apparaît, au plus tard après divisions.
Étape 2 sur 4Calculer un PGCD
Méthodel'algorithme d'Euclide
- Divise par : , avec .
- Recommence avec et , puis avec les deux derniers restes, tant que le reste n'est pas nul.
- Lis le PGCD : c'est le dernier reste non nul. Si le premier reste est déjà nul, c'est-à-dire si , alors .
- Présente une division par ligne, en colonne, pour pouvoir te relire.

ExempleExemple guidé : le PGCD de 1078 et 322
Chaque reste est positif ou nul et plus petit que le diviseur de sa ligne. Le dernier reste non nul est : .
Le PGCD résume tous les diviseurs communs. Et il passe à travers un facteur commun. Voyons ces deux faits.

Étape 3 sur 4Deux conséquences
PropriétéDiviseurs communs et PGCD
Soient et deux entiers relatifs non tous les deux nuls, et un entier relatif. Alors Les diviseurs communs à et à sont exactement les diviseurs de .
Démonstration
Idée de la preuve. Un diviseur de divise et , par transitivité. Réciproquement, on suit les divisions de l'algorithme d'Euclide : d'après la propriété « PGCD et division euclidienne », un diviseur commun à et est un diviseur commun à deux restes consécutifs, donc divise le dernier reste non nul, qui est . Étapes omises : la réduction au cas et le passage d'une division à la suivante, rédigé de proche en proche.

Exempletous les diviseurs communs
Une preuve esquissée. La preuve est seulement esquissée. Elle omet la réduction au cas et la rédaction, division par division, du passage d'un reste au suivant.
Les diviseurs communs à et sont exactement les diviseurs de : , , , , , , et . Inutile de lister les diviseurs de : le PGCD suffit.

PropriétéPGCD et multiplication par un entier
Soient et deux entiers relatifs non tous les deux nuls, et un entier naturel non nul. Alors
Démonstration
Idée de la preuve. On multiplie par chaque division de l'algorithme d'Euclide appliqué à et : on obtient exactement les divisions de l'algorithme appliqué à et , car lorsque . Les restes sont multipliés par , donc le dernier reste non nul aussi. Étapes omises : le cas où ou est négatif ou nul, et la vérification division par division.

Exemplemettre un facteur en commun
Une preuve esquissée. La preuve est seulement esquissée. Elle omet le cas où ou est négatif ou nul, et la vérification division par division.
et . Donc . Contrôle par l'algorithme : , puis , puis .

Étape 4 sur 4À toi
À toi : Un PGCD et ses diviseurs

Calcule par l'algorithme d'Euclide. Déduis-en les diviseurs communs positifs de et . Écris ta réponse avant de dévoiler la correction.
Besoin d'aide ? Indice 1
Commence par la division de par .
Encore bloqué ? Indice 2
Le deuxième reste est ; continue jusqu'à un reste nul.
Encore bloqué ? Indice 3
Point délicat : les diviseurs communs sont les diviseurs du PGCD ; décompose-le.
Voir la solution complète
Le dernier reste non nul est : . Les diviseurs communs sont les diviseurs de . Les diviseurs communs positifs sont donc , , et .
RemarqueCoin devoir : un PGCD d'expressions en n
En devoir, chaque ligne de l'algorithme doit être une vraie division euclidienne. Exemple : soit un entier tel que . Vérifie chaque reste : , puis . Conclus : « le dernier reste non nul est , donc ».

← É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 ℤ » (1bac · sciences-mathematiques · mathematiques)
