Diviseurs, premiers et PGCD
Un nombre premier a exactement deux diviseurs : 1 et lui-même. Tout entier supérieur à 1 se décompose de façon unique en produit de facteurs premiers.
- Le PGCD de a et b est le plus grand entier qui divise à la fois a et b.
- Avec les décompositions en facteurs premiers : on multiplie les facteurs communs, pris avec le plus petit exposant.
- Algorithme d'Euclide : PGCD(a ; b) = PGCD(b ; r), où r est le reste de la division euclidienne de a par b. Le dernier reste non nul est le PGCD.
- Une fraction est irréductible quand son numérateur et son dénominateur n'ont que 1 pour diviseur commun.
Exercice 1 Avec les facteurs premiers
1. Décomposer 84 et 126 en produits de facteurs premiers.
2. En déduire PGCD(84 ; 126).
Un indice
Divisez successivement par les plus petits nombres premiers : 2, 3, 5, 7…
Voir la correction
1. 84 = 2 × 42 = 2 × 2 × 21 = 2² × 3 × 7 et 126 = 2 × 63 = 2 × 3² × 7.
2. Les facteurs communs sont 2 (exposant 1 au minimum), 3 (exposant 1) et 7 (exposant 1). PGCD(84 ; 126) = 2 × 3 × 7 = 42.
Vérification : 84 = 42 × 2 et 126 = 42 × 3, et 2 et 3 n'ont pas d'autre diviseur commun que 1.
Exercice 2 L'algorithme d'Euclide
Calculer PGCD(252 ; 180) avec l'algorithme d'Euclide.
Un indice
Effectuez des divisions euclidiennes successives jusqu'à obtenir un reste nul.
Voir la correction
252 = 180 × 1 + 72 ; 180 = 72 × 2 + 36 ; 72 = 36 × 2 + 0.
Le dernier reste non nul est 36 : PGCD(252 ; 180) = 36.
Contrôle : 252 = 36 × 7 et 180 = 36 × 5.
Exercice 3 Rendre une fraction irréductible
Écrire la fraction 252/180 sous forme irréductible, en utilisant le résultat de l'exercice précédent.
Un indice
Divisez le numérateur et le dénominateur par leur PGCD.
Voir la correction
Le PGCD de 252 et 180 est 36. On divise numérateur et dénominateur par 36.
252 / 36 = 7 et 180 / 36 = 5, donc 252/180 = 7/5.
La fraction 7/5 est irréductible, car 7 et 5 sont premiers entre eux.
Exercice 4 Partager en lots identiques
Une papeterie dispose de 180 stylos et de 252 gommes. Elle veut former le plus grand nombre possible de lots identiques, en utilisant tous les articles.
Combien de lots peut-elle former ? Que contient chaque lot ?
Un indice
Le nombre de lots doit diviser 180 et 252 : cherchez le plus grand diviseur commun.
Voir la correction
Le nombre de lots est un diviseur commun de 180 et de 252. Pour qu'il soit maximal, c'est PGCD(180 ; 252) = 36.
Chaque lot contient 180 / 36 = 5 stylos et 252 / 36 = 7 gommes.
Contrôle : 36 × 5 = 180 et 36 × 7 = 252. Aucun article n'est inutilisé.
Les erreurs à éviter
- Considérer 1 comme un nombre premier.
- Prendre les facteurs premiers avec le plus grand exposant au lieu du plus petit pour un PGCD.
- S'arrêter à l'avant-dernier reste dans l'algorithme d'Euclide.
- Simplifier une fraction par un diviseur commun qui n'est pas le plus grand et la croire irréductible.
Questions fréquentes
Quelle méthode choisir pour calculer un PGCD ?
L'algorithme d'Euclide est plus rapide pour de grands nombres ; la décomposition en facteurs premiers est utile quand les nombres sont petits et faciles à décomposer.
Que signifie « premiers entre eux » ?
Deux nombres sont premiers entre eux quand leur PGCD vaut 1 : ils n'ont aucun diviseur commun autre que 1.
À quoi servent les nombres premiers ?
Ils sont les briques de tous les entiers, et sont utilisés en cryptographie pour sécuriser les communications.