PGCD et algorithme d'Euclide

Lessons and exercises follow the school system and stay in its language.Les leçons et les exercices suivent le système scolaire et restent dans sa langue.Lektionen und Übungen folgen dem Schulsystem und bleiben in seiner Sprache.

À propos de cette leçon

Terminale, mathématiques expertes › PGCD, Bézout et Gauss

Pour obtenir un PDF, choisis « Enregistrer au format PDF » dans la fenêtre d'impression.

Sources et crédits

Leçon originale de sedifier.

Rédigé avec l'aide d'une IA ; chaque réponse est vérifiée par notre moteur de calcul. Pas encore relu par un enseignant.

Cette leçon : CC BY-SA 4.0, © sedifier · Tous les crédits

PGCD et algorithme d'Euclide

PGCD, Bézout et Gauss. PGCD, algorithme d'Euclide, Bézout, Gauss, équation diophantienne, chiffrement

Échauffement

Trois questions rapides sur des leçons déjà vues.

  1. Quel est le reste de la division euclidienne de 1414 par 3 ?
  2. Quel est le reste de la division euclidienne de −10-10 par 4 ?
  3. On sait que 9 divise xx et yy. Quel nombre 9 divise-t-il toujours ?
    1. 7x+4y7x + 4y
    2. x+1x + 1
    3. xy\dfrac{x}{y}

Découvrir

Quel est le plus grand diviseur commun à 12 et 18 ?

  1. 66
  2. 3636

L'idée clé

L'algorithme d'Euclide répète des divisions euclidiennes.

PGCD(a;b)=PGCD(b;r)\mathrm{PGCD}(a ; b) = \mathrm{PGCD}(b ; r), où rr est le reste de la division de aa par bb. Le PGCD est le dernier reste non nul.

aa et bb sont premiers entre eux si PGCD(a;b)=1\mathrm{PGCD}(a ; b) = 1.

Exemple corrigé

Calcule PGCD(252;105)\mathrm{PGCD}(252 ; 105).

PGCD(105;42)\mathrm{PGCD}(105 ; 42)
252 = 105 × 2 + 42.
PGCD(42;21)\mathrm{PGCD}(42 ; 21)
105 = 42 × 2 + 21.
2121
42 = 21 × 2 + 0.

À toi, guidé

À toi : calcule PGCD(35;14)\mathrm{PGCD}(35 ; 14).

77
35 = 14 × 2 + 7, 14 = 7 × 2.

Entraînement ★

  1. Calcule PGCD(21;24)\mathrm{PGCD}(21 ; 24).
  2. Calcule PGCD(350;400)\mathrm{PGCD}(350 ; 400).
  3. Calcule PGCD(14;16)\mathrm{PGCD}(14 ; 16).

Attention !

Entraînement ★★

  1. Les nombres 55 et 66 sont-ils premiers entre eux ?
    1. Oui, toujours
    2. Seulement s'ils sont premiers
    3. Non
  2. Les nombres 22 et 33 sont-ils premiers entre eux ?
    1. Oui, toujours
    2. Seulement s'ils sont premiers
    3. Non
  1. Calcule PGCD(12;4)\mathrm{PGCD}(12 ; 4).
  1. Dans l'algorithme d'Euclide pour 1717 et 7, on remplace le couple par (7 ; rr). Que vaut rr ?

Bilan

Trois questions pour vérifier que c'est acquis.

  1. Calcule PGCD(21;24)\mathrm{PGCD}(21 ; 24).
  2. Calcule PGCD(350;400)\mathrm{PGCD}(350 ; 400).
  3. Calcule PGCD(14;16)\mathrm{PGCD}(14 ; 16).

Fiche résumé

PGCD

  • PGCD(a;b)=PGCD(b;r)\mathrm{PGCD}(a ; b) = \mathrm{PGCD}(b ; r).
  • Dernier reste non nul.

Attention : ne confonds pas avec le dernier quotient.

Il reste une étape facultative : un défi. Tente-le, ou termine la leçon maintenant.

Défi ★★★

  1. Calcule PGCD(108;162)\mathrm{PGCD}(108 ; 162).
Sources et crédits

Leçon originale de sedifier.

Rédigé avec l'aide d'une IA ; chaque réponse est vérifiée par notre moteur de calcul. Pas encore relu par un enseignant.

Cette leçon : CC BY-SA 4.0, © sedifier · Tous les crédits