BURHAN.

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 4

Répéter la division

Devine : Des divisions en cascade

On écrit 252=198×1+54252 = 198 \times 1 + 54, puis 198=54×3+36198 = 54 \times 3 + 36, puis 54=36×1+1854 = 36 \times 1 + 18, et enfin 36=18×2+036 = 18 \times 2 + 0. D'après la propriété précédente, que vaut 252∧198252 \wedge 198 ?

Choisis une réponse : l'explication s'affiche sous ton choix. Tu peux en changer.

Choix A :5454

Faux.

5454 est le premier reste ; or 5454 ne divise pas 198198.

Choix B :3636

Faux.

3636 ne divise pas 5454 : ce n'est pas un diviseur commun.

Choix C :1818

Juste.

Juste : c'est le dernier reste non nul.

Choix D :00

Faux.

00 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 : 252∧198=198∧54=54∧36=36∧18=18∧0=18252 \wedge 198 = 198 \wedge 54 = 54 \wedge 36 = 36 \wedge 18 = 18 \wedge 0 = 18.

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 aa un entier relatif et bb un entier naturel non nul. On pose r0=br_0 = b et on note r1r_1 le reste de la division euclidienne de aa par bb. Pour k≥1k \geq 1, tant que rk≠0r_k \neq 0, on note rk+1r_{k+1} le reste de la division euclidienne de rk−1r_{k-1} par rkr_k.

Il existe un rang m≥1m \geq 1 tel que rm=0r_m = 0, et a∧ba \wedge b est le dernier reste non nul : a∧b=rm−1a \wedge b = r_{m-1}.

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, b=r0>r1>r2>⋯≥0b = r_0 > r_1 > r_2 > \dots \geq 0. Des entiers naturels strictement décroissants à partir de bb sont au plus b+1b + 1. Un reste nul rmr_m apparaît donc, avec 1≤m≤b1 \leq m \leq b.

Étape 2 (PGCD). D'après la propriété « PGCD et division euclidienne » appliquée à la première division, a∧b=r0∧r1a \wedge b = r_0 \wedge r_1. Appliquée à chaque division suivante, elle donne rk−1∧rk=rk∧rk+1r_{k-1} \wedge r_k = r_k \wedge r_{k+1}. De proche en proche, a∧b=rm−1∧rm=rm−1∧0=rm−1a \wedge b = r_{m-1} \wedge r_m = r_{m-1} \wedge 0 = r_{m-1} (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 : rm−1∧0=rm−1r_{m-1} \wedge 0 = r_{m-1}.

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, rk−1>rkr_{k-1} > r_k : chaque quotient est au moins égal à 11.

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 : 198=54×3+36198 = 54 \times 3 + 36 donne le reste 3636, plus grand que la moitié de 5454.

Choix D :Parce que le premier reste divise toujours bb.

Faux.

Pour 252252 et 198198, le premier reste 5454 ne divise pas 198198.

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, b=r0>r1>r2>⋯≥0b = r_0 > r_1 > r_2 > \dots \geq 0. Une telle suite d'entiers naturels ne peut pas continuer indéfiniment : un reste nul apparaît, au plus tard après bb divisions.

Continuer : Calculer un PGCD →

Étape 2 sur 4

Calculer un PGCD

Méthodel'algorithme d'Euclide

  1. Divise aa par bb : a=bq1+r1a = bq_1 + r_1, avec 0≤r1<b0 \leq r_1 < b.
  2. Recommence avec bb et r1r_1, puis avec les deux derniers restes, tant que le reste n'est pas nul.
  3. Lis le PGCD : c'est le dernier reste non nul. Si le premier reste est déjà nul, c'est-à-dire si b∣ab \mid a, alors a∧b=ba \wedge b = b.
  4. Présente une division par ligne, en colonne, pour pouvoir te relire.

ExempleExemple guidé : le PGCD de 1078 et 322

1078=322×3+112322=112×2+98112=98×1+1498=14×7+0\begin{aligned} 1078 &= 322 \times 3 + 112 \\ 322 &= 112 \times 2 + 98 \\ 112 &= 98 \times 1 + 14 \\ 98 &= 14 \times 7 + 0 \end{aligned} Chaque reste est positif ou nul et plus petit que le diviseur de sa ligne. Le dernier reste non nul est 1414 : 1078∧322=141078 \wedge 322 = 14.

Le PGCD résume tous les diviseurs communs. Et il passe à travers un facteur commun. Voyons ces deux faits.

← Étape précédenteContinuer : Deux conséquences →

Étape 3 sur 4

Deux conséquences

PropriétéDiviseurs communs et PGCD

Soient aa et bb deux entiers relatifs non tous les deux nuls, et dd un entier relatif. Alors (d∣a et d∣b)⇔d∣a∧b.\big(d \mid a \text{ et } d \mid b\big) \Leftrightarrow d \mid a \wedge b. Les diviseurs communs à aa et à bb sont exactement les diviseurs de a∧ba \wedge b.

Démonstration

Idée de la preuve. Un diviseur de a∧ba \wedge b divise aa et bb, 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 à aa et bb est un diviseur commun à deux restes consécutifs, donc divise le dernier reste non nul, qui est a∧ba \wedge b. Étapes omises : la réduction au cas b≥1b \geq 1 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 b≥1b \geq 1 et la rédaction, division par division, du passage d'un reste au suivant.

Les diviseurs communs à 10781078 et 322322 sont exactement les diviseurs de 1414 : −14-14, −7-7, −2-2, −1-1, 11, 22, 77 et 1414. Inutile de lister les diviseurs de 10781078 : le PGCD suffit.

PropriétéPGCD et multiplication par un entier

Soient aa et bb deux entiers relatifs non tous les deux nuls, et kk un entier naturel non nul. Alors (ka)∧(kb)=k(a∧b).(ka) \wedge (kb) = k (a \wedge b).

Démonstration

Idée de la preuve. On multiplie par kk chaque division de l'algorithme d'Euclide appliqué à aa et bb : on obtient exactement les divisions de l'algorithme appliqué à kaka et kbkb, car 0≤kr<kb0 \leq kr < kb lorsque 0≤r<b0 \leq r < b. Les restes sont multipliés par kk, donc le dernier reste non nul aussi. Étapes omises : le cas où aa ou bb 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ù aa ou bb est négatif ou nul, et la vérification division par division.

600=120×5600 = 120 \times 5 et 840=120×7840 = 120 \times 7. Donc 600∧840=120×(5∧7)=120×1=120600 \wedge 840 = 120 \times (5 \wedge 7) = 120 \times 1 = 120. Contrôle par l'algorithme : 840=600×1+240840 = 600 \times 1 + 240, puis 600=240×2+120600 = 240 \times 2 + 120, puis 240=120×2+0240 = 120 \times 2 + 0.

← Étape précédenteContinuer : À toi →

Étape 4 sur 4

À toi

À toi : Un PGCD et ses diviseurs

Calcule 2093∧15472093 \wedge 1547 par l'algorithme d'Euclide. Déduis-en les diviseurs communs positifs de 20932093 et 15471547. Écris ta réponse avant de dévoiler la correction.

Besoin d'aide ? Indice 1

Commence par la division de 20932093 par 15471547.

Encore bloqué ? Indice 2

Le deuxième reste est 455455 ; 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

2093=1547×1+5461547=546×2+455546=455×1+91455=91×5+0\begin{aligned} 2093 &= 1547 \times 1 + 546 \\ 1547 &= 546 \times 2 + 455 \\ 546 &= 455 \times 1 + 91 \\ 455 &= 91 \times 5 + 0 \end{aligned} Le dernier reste non nul est 9191 : 2093∧1547=912093 \wedge 1547 = 91. Les diviseurs communs sont les diviseurs de 91=7×1391 = 7 \times 13. Les diviseurs communs positifs sont donc 11, 77, 1313 et 9191.

RemarqueCoin devoir : un PGCD d'expressions en n

En devoir, chaque ligne de l'algorithme doit être une vraie division euclidienne. Exemple : soit nn un entier tel que n≥2n \geq 2. 2n+1=(n+1)×1+n,n+1=n×1+1,n=1×n+0.2n + 1 = (n + 1) \times 1 + n, \quad n + 1 = n \times 1 + 1, \quad n = 1 \times n + 0. Vérifie chaque reste : 0≤n<n+10 \leq n < n + 1, puis 0≤1<n0 \leq 1 < n. Conclus : « le dernier reste non nul est 11, donc (2n+1)∧(n+1)=1(2n + 1) \wedge (n + 1) = 1 ».

← É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)