BURHAN.

PGCD de deux entiers : Cours de Mathématiques 1BAC Sciences Mathématiques, chapitre Arithmétique dans ℤ

PGCD de deux entiers : notion du chapitre Arithmétique dans ℤ du programme de maths 1BAC SM, expliquée pas à pas, avec 2 exemples guidés. Pour les élèves de 1BAC Sciences Mathématiques, option française (BIOF).

Notions du cours (13)

Apprendre avec Burhan

PGCD et division euclidienne

Étape 1 sur 2

Le plus grand diviseur commun

Les diviseurs positifs de 2424 sont 11, 22, 33, 44, 66, 88, 1212 et 2424. Ceux de 3636 sont 11, 22, 33, 44, 66, 99, 1212, 1818 et 3636. Les diviseurs communs positifs sont 11, 22, 33, 44, 66 et 1212. Le plus grand est 1212 : c'est le plus grand diviseur commun de 2424 et 3636.

Devine : Avec un nombre négatif

Quel est le plus grand diviseur commun à −18-18 et 3030 ?

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

Choix A :66

Juste.

Juste : les diviseurs de −18-18 sont ceux de 1818.

Choix B :−6-6

Faux.

−6-6 est un diviseur commun, mais 66 est plus grand.

Choix C :1818

Faux.

1818 ne divise pas 3030.

Choix D :22

Faux.

22 est un diviseur commun, mais pas le plus grand.

Voir la correction complète

Les diviseurs de −18-18 sont ceux de 1818. Les diviseurs communs positifs de 1818 et 3030 sont 11, 22, 33 et 66. Le plus grand diviseur commun à −18-18 et 3030 est donc 66.

DéfinitionPGCD de deux entiers

Soient aa et bb deux entiers relatifs non tous les deux nuls. Les diviseurs communs à aa et à bb sont en nombre fini (comparaison des valeurs absolues) et 11 en fait partie. Le plus grand d'entre eux est le plus grand commun diviseur de aa et bb, noté a∧ba \wedge b ou pgcd⁡(a,b)\operatorname{pgcd}(a, b). C'est un entier naturel non nul.

Exemplequelques PGCD

  • (−20)∧(−30)=10(-20) \wedge (-30) = 10 et 13∧26=1313 \wedge 26 = 13.
  • 45∧0=4545 \wedge 0 = 45 : tout entier divise 00, donc les diviseurs communs sont ceux de 4545.
  • 0∧00 \wedge 0 n'est pas défini : tout entier divise 00, il n'y a pas de plus grand diviseur commun.

Un raccourci : 84=60×1+2484 = 60 \times 1 + 24, et 84∧60=60∧24=1284 \wedge 60 = 60 \wedge 24 = 12. Pourquoi est-ce vrai ? Un diviseur commun de 8484 et 6060 divise 84−60=2484 - 60 = 24. Un diviseur commun de 6060 et 2424 divise 60+24=8460 + 24 = 84.

Continuer : PGCD et division euclidienne →

Étape 2 sur 2

PGCD et division euclidienne

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∧r,a \wedge b = b \wedge r, et b∧0=bb \wedge 0 = b.

Démonstration

Étape 1. Écrivons a=bq+ra = bq + r (division euclidienne). Soit dd un diviseur commun à aa et bb. Alors dd divise a×1+b×(−q)a \times 1 + b \times (-q), c'est-à-dire rr (propriétés de la divisibilité).

Étape 2. Soit dd un diviseur commun à bb et rr. Alors dd divise b×q+r×1b \times q + r \times 1, c'est-à-dire aa (propriétés de la divisibilité).

Étape 3. Les deux ensembles de diviseurs communs sont donc égaux : ils ont le même plus grand élément, d'où a∧b=b∧ra \wedge b = b \wedge r (définition du PGCD).

Étape 4. Tout entier divise 00. Les diviseurs communs à bb et 00 sont donc les diviseurs de bb, dont le plus grand est bb (comparaison des valeurs absolues) : b∧0=bb \wedge 0 = b.

À retenirRetenir de la preuve : les deux inclusions

Pour montrer que deux ensembles de diviseurs communs sont égaux, on prouve les deux inclusions. Chacune s'obtient par une combinaison : r=a−bqr = a - bq dans un sens, a=bq+ra = bq + r dans l'autre. Le PGCD ne change donc pas quand on remplace (a,b)(a, b) par (b,r)(b, r).

Vérifie : Une combinaison

Dans l'étape 1 de la preuve, a=bq+ra = bq + r. Quelle combinaison de aa et bb donne rr ?

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

Choix A :a+bqa + bq

Faux.

a+bq=2bq+ra + bq = 2bq + r : ce n'est pas rr.

Choix B :a×b−qa \times b - q

Faux.

Pour a=7a = 7, b=3b = 3 et q=2q = 2, ce nombre vaut 1919, alors que r=1r = 1.

Choix C :a×1+b×(−q)a \times 1 + b \times (-q)

Juste.

Juste : a−bq=ra - bq = r.

Choix D :ab\dfrac{a}{b}

Faux.

Ce quotient n'est pas entier en général : ce n'est pas une combinaison à coefficients entiers.

Voir la correction complète

De a=bq+ra = bq + r, on tire r=a×1+b×(−q)r = a \times 1 + b \times (-q). Les coefficients 11 et −q-q sont des entiers. Un diviseur commun de aa et bb divise donc rr, d'après les propriétés de la divisibilité.

Exempleun PGCD qui dépend de n

Soit nn un entier tel que n>5n > 5. La division euclidienne de n+5n + 5 par nn s'écrit n+5=n×1+5n + 5 = n \times 1 + 5, avec 0≤5<n0 \leq 5 < n. Donc (n+5)∧n=n∧5(n + 5) \wedge n = n \wedge 5. Ce PGCD divise 55 : il vaut 55 si 5∣n5 \mid n, et 11 sinon. Pour n=15n = 15, on trouve 20∧15=520 \wedge 15 = 5.

À toi : Par la division

Soit nn un entier tel que n≥3n \geq 3. Calcule (3n+2)∧n(3n + 2) \wedge n selon les valeurs de nn, à l'aide d'une division euclidienne. Écris ta réponse avant de dévoiler la correction.

Besoin d'aide ? Indice 1

Écris la division euclidienne de 3n+23n + 2 par nn.

Encore bloqué ? Indice 2

Vérifie la condition sur le reste : 0≤2<n0 \leq 2 < n.

Encore bloqué ? Indice 3

Point délicat : n∧2n \wedge 2 dépend de la parité de nn.

Voir la solution complète

Pour n≥3n \geq 3, 3n+2=n×3+23n + 2 = n \times 3 + 2 avec 0≤2<n0 \leq 2 < n : c'est la division euclidienne. D'après la propriété du PGCD et de la division euclidienne, (3n+2)∧n=n∧2(3n + 2) \wedge n = n \wedge 2. Les diviseurs positifs de 22 sont 11 et 22. Donc ce PGCD vaut 22 si nn est pair, et 11 si nn est impair.

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