BURHAN.

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 3

PGCD et PPCM

Vérifie : Le plus grand diviseur commun

Quel est le plus grand entier naturel qui divise à la fois 8484 et 120120 ?

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

Choix A :66

Faux.

66 divise bien 8484 et 120120, mais ce n'est pas le plus grand diviseur commun.

Choix B :840840

Faux.

840840 est le plus petit multiple commun non nul, pas un diviseur commun : il dépasse 8484.

Choix C :44

Faux.

44 est un diviseur commun, mais il oublie le facteur 33, commun aux deux.

Choix D :1212

Juste.

1212 divise 8484 et 120120, et aucun diviseur de 8484 plus grand que 1212 ne divise 120120.

Besoin d'aide ? Indice 1

Liste les diviseurs positifs de 8484, puis garde ceux qui divisent 120120.

Voir la correction complète

Les diviseurs positifs de 8484 sont 11, 22, 33, 44, 66, 77, 1212, 1414, 2121, 2828, 4242 et 8484.

Parmi eux, ceux qui divisent 120120 sont 11, 22, 33, 44, 66 et 1212. Le plus grand est 1212.

En 1BAC, tu as noté ce nombre a∧ba \wedge b : c'est le PGCD. Le plus petit multiple commun non nul se note a∨ba \vee b : c'est le PPCM. Voici les définitions exactes.

DéfinitionPGCD et PPCM

Soient aa et bb deux entiers relatifs non tous les deux nuls. Le plus grand commun diviseur de aa et bb est le plus grand entier naturel qui divise à la fois aa et bb ; on le note a∧ba \wedge b. Si aa et bb sont tous les deux non nuls, le plus petit commun multiple de aa et bb est le plus petit entier naturel non nul qui est à la fois un multiple de aa et un multiple de bb ; on le note a∨ba \vee b.

ExempleQuatre calculs

  • (−18)∧30=6(-18) \wedge 30 = 6 : le signe ne change pas les diviseurs.
  • 18∨30=9018 \vee 30 = 90.
  • 7∧0=77 \wedge 0 = 7, car tout entier divise 00.
  • 8∧15=18 \wedge 15 = 1 : leur seul diviseur commun positif est 11.

Continuer : PGCD et reste →

Étape 2 sur 3

PGCD et reste

Cherche 391∧299391 \wedge 299. On écrit 391=299×1+92391 = 299 \times 1 + 92. Un diviseur commun à 391391 et 299299 divise 391−299=92391 - 299 = 92. À l'inverse, un diviseur commun à 299299 et 9292 divise 299+92=391299 + 92 = 391.

Pourquoi est-ce utile ? On remplace le couple par un couple plus petit, sans changer le PGCD.

PropriétéPGCD et division euclidienne

Soient aa un entier relatif, bb un entier naturel non nul, et rr le reste de la division euclidienne de aa par bb. Les diviseurs communs à aa et bb sont exactement les diviseurs communs à bb et rr. En particulier, a∧b=b∧ra \wedge b = b \wedge r ; si r=0r = 0, alors a∧b=b∧0=ba \wedge b = b \wedge 0 = b.

Démonstration

Étape 1. On écrit a=bq+ra = bq + r (« Division euclidienne dans ℤ »). Si c∣ac \mid a et c∣bc \mid b, alors c∣a−bq=rc \mid a - bq = r (« Propriétés de la divisibilité », point 2).

Étape 2. Si c∣bc \mid b et c∣rc \mid r, alors c∣bq+r=ac \mid bq + r = a (« 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 : a∧b=b∧ra \wedge b = b \wedge r. Si r=0r = 0, les diviseurs communs à bb et 00 sont les diviseurs de bb, dont le plus grand est bb : donc b∧0=bb \wedge 0 = b.

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

On a 1000=7×142+61000 = 7 \times 142 + 6. 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 :1000∧7=7∧61000 \wedge 7 = 7 \wedge 6

Juste.

On garde le diviseur 77 et on remplace 10001000 par le reste 66.

Choix B :1000∧7=1000∧61000 \wedge 7 = 1000 \wedge 6

Faux.

On garde le dividende au lieu du diviseur. D'ailleurs 1000∧6=21000 \wedge 6 = 2, alors que 1000∧7=11000 \wedge 7 = 1.

Choix C :1000∧7=142∧61000 \wedge 7 = 142 \wedge 6

Faux.

142142 est le quotient : il n'intervient pas. Ici 142∧6=2142 \wedge 6 = 2, alors que 1000∧7=11000 \wedge 7 = 1.

Voir la correction complète

Avec a=1000a = 1000, b=7b = 7 et r=6r = 6, la propriété donne 1000∧7=7∧61000 \wedge 7 = 7 \wedge 6. On recommence : 7=6×1+17 = 6 \times 1 + 1, donc 7∧6=6∧1=17 \wedge 6 = 6 \wedge 1 = 1.

← Étape précédenteContinuer : L'algorithme d'Euclide →

Étape 3 sur 3

L'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 (rm,0)(r_m, 0), et rm∧0=rmr_m \wedge 0 = r_m.

PropriétéAlgorithme d'Euclide

Soient aa et bb deux entiers naturels non nuls. On pose r0=ar_0 = a et r1=br_1 = b, puis, 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 \neq 0 et rm+1=0r_{m+1} = 0, et alors a∧b=rm.a \wedge b = r_m. Le PGCD de aa et bb est le dernier reste non nul.

Démonstration

Étape 1 (l'algorithme s'arrête). Tant que les restes sont non nuls, on a b=r1>r2>r3>⋯≥0b = r_1 > r_2 > r_3 > \dots \geq 0, 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 b+1b + 1 termes : un reste finit par être nul.

Étape 2. Soit mm le rang tel que rm≠0r_m \neq 0 et rm+1=0r_{m+1} = 0. Par « PGCD et division euclidienne » appliqué à chaque division, rk−1∧rk=rk∧rk+1r_{k-1} \wedge r_k = r_k \wedge r_{k+1} pour 1≤k≤m1 \leq k \leq m.

Étape 3. De proche en proche (récurrence sur kk), a∧b=r0∧r1=rm∧rm+1=rm∧0=rma \wedge b = r_0 \wedge r_1 = r_m \wedge r_{m+1} = r_m \wedge 0 = r_m.

Méthodel'algorithme d'Euclide en tableau

  1. Ranger : on divise le plus grand entier par le plus petit, sur une ligne du tableau.
  2. Décaler : le diviseur devient le dividende, le reste devient le diviseur.
  3. 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, a∧ba \wedge b est le dernier reste non nul. » Chaque ligne respecte l'encadrement du reste.

ExempleExemple guidé : 391 et 299

dividende diviseur quotient reste
391391 299299 11 9292
299299 9292 33 2323
9292 2323 44 00

Le dernier reste non nul est 2323. D'après l'algorithme d'Euclide, 391∧299=23391 \wedge 299 = 23. 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)