PGCD signifie Plus Grand Commun Diviseur. On l'appelle aussi PGDC.

• D'abord un rappel sur la division Euclidienne (division avec un quotient entier et un reste entier)
  • exemple : 30 divisé par 8, la division donne : 30 = 8 × 3 + 6
  • le quotient est 3, le reste est 6 et il est inférieur au diviseur 8. Avec la calculatrice,
  • 1) diviser 30 par 8 = 3,75 : le quotient entier est donc 3
  • 2) calculer le reste : 30 − (8 × 3) = 6
• Une remarque : en passant (8 × 3) de l'autre côté du signe égal : 6 = 30 − (8 × 3)
  • comme
    2 divise 30, car : 30 = 2×15
    2 divise 8, car : 8 = 2×4
  • on peut conclure que : 2 divise (30 − 8 × 3), le reste de la division Euclidienne.
  • 6 = 30 − 8 × 3 = 2 × 15 − 2 × 4 × 3 = 2(15 − 4 × 3)
• En conclusion : si a = bq + r : comme r = a − bq, les diviseurs communs à "a" et "b" divisent "r"
  • donc le PGCD de "a" et "b" divise le reste de la division de "a" par "b"
• Algorithme d'Euclide (ou Méthode d'Euclide) pour calculer le PGCD de 2 nombres
  • 1) On divise le plus grand nombre (a) par le plus petit (b), ce qui nous donne un premier reste r
  • 2) On répète ensuite l'opération avec les 2 plus petits nombres : b et r
  • Le même raisonnement conclut que le PGCD divise le nouveau reste
  • 3) On continue jusqu'à ce que le reste soit nul.
  • (remarque : Le PGDC divise 0, car tous les nombres divisent 0 : 0 = b × 0 + 0)
  • Le PGCD est le dernier reste non nul.
• exemple : trouver le PGCD(805,1260)
  • 1260 divisé par 805 : 1260 = 805×1 + 455
  • 805 divisé par 455 : 805 = 455×1 + 350
  • 455 divisé par 350 : 455 = 350×1 + 105
  • 350 divisé par 105 : 350 = 105×3 + 35
  • 105 divisé par 35 : 105 = 35×3 + 0
  • Le PGCD est 35
  • (vérification : 1260=35×36, 805=35×23,
    36=2×2×3×3 et 23 qui est un nombre premier n'ont pas de diviseurs communs)
• Pour trouver le PGCD des petits nombres (quand il faut simplifier une fraction par exemple).
  • On peut décomposer les 2 nombres en facteurs premiers, on obtient :
  • 805=5×7×23
  • 1260=2×2×3×3×5×7
  • le PGDC est le produit des facteurs premiers communs : PGDC = 5×7 = 35
• La décomposition en facteurs premiers n'est intéressante que pour les petits nombres,
  • car on ne va tester que les premiers "nombres premiers" : 2, 3, 5,
  • si on est courageux : 7 et 11
  • mais on ne va pas tous les tester.
  • Rappels :
    • 1) un nombre est divisible par 2 si son dernier chiffre est 0, 2, 4, 6 ou 8
    • 2) un nombre est divisible par 3 si la somme de ses chiffres est divisible par 3
      exemple : 456 est divisible par 3 car 4+5+6 = 15 est divisible par 3 (15= 3×5)
    • 3) un nombre est divisible par 5 si son dernier chiffre est 0 ou 5
• exemple : 28/12 = (2×2×7)/(2×2×3) = 7/3
  • => Quand on simplifie une fraction, on divise le numérateur et le dénominateur par leur PGCD.

retour aux menus :   cours 3ème   math 3ème   math