Divisibilité, PGCD, PPCM, nombres premiers
Multiples et diviseurs · critères de divisibilité · division euclidienne · nombres premiers · décomposition en facteurs premiers · algorithme d'Euclide · PPCM.
Sur cette page
Comprendre
Le problème qui donne envie de comprendre
Autre situation : deux bus passent toutes les 8 minutes et toutes les 12 minutes, partis ensemble à 8h00. Ils se retrouveront dans 24 minutes, à 8h24. 24, c'est le PPCM. Ces deux outils sont au cœur de la fiche. Pour les comprendre, il faut d'abord la divisibilité, les nombres premiers et la décomposition. Chaque notion en appelle une autre : lisez-les dans l'ordre.
①Divisibilité : est-ce que ça tombe juste ?
Diviser 12 billes entre 4 enfants, ça tombe juste (3 chacun). Diviser 13 billes entre 4 enfants, il en reste une. Cette idée simple est exactement ce que formalise la divisibilité. On dit que b divise a lorsqu'on peut répartir a en groupes de b sans aucun reste, c'est-à-dire s'il existe un entier k tel que a = k × b.
Tester si 4 572 est divisible par 3 en posant la division serait fastidieux. Des critères permettent de répondre en quelques secondes, sans calculer. Ils sont au programme, et le jury peut demander d'en justifier un (notamment par 3 ou par 9).
| Divisible par | Critère | Exemple avec 4 572 |
|---|---|---|
| 2 | chiffre des unités pair (0, 2, 4, 6, 8) | oui (unités = 2) |
| 3 | somme des chiffres divisible par 3 | oui (4+5+7+2 = 18 = 6 × 3) |
| 4 | deux derniers chiffres = multiple de 4 | oui (72 = 18 × 4) |
| 5 | chiffre des unités = 0 ou 5 | non (unités = 2) |
| 9 | somme des chiffres divisible par 9 | oui (18 = 2 × 9) |
| 10 | chiffre des unités = 0 | non (unités = 2) |
Combiner les critères
10 = 9 + 1, 100 = 99 + 1, 1 000 = 999 + 1 : chaque puissance de 10 est un multiple de 9, plus 1. Donc dans 4 572 = 4 × 1 000 + 5 × 100 + 7 × 10 + 2, chaque terme a le même reste par 9 (et par 3) que son chiffre. Le reste de 4 572 par 9 est donc le même que celui de 4 + 5 + 7 + 2 = 18, soit 0. D'où le critère.
②Division euclidienne : quand ça ne tombe pas juste
On vient de voir la divisibilité, le cas où la division tombe juste. Mais 47 billes réparties en groupes de 5, ça donne 9 groupes et il reste 2 billes. Ce reste est celui de la division euclidienne, l'outil fondamental de toute l'arithmétique, et la base de l'algorithme d'Euclide.
Le lien avec la divisibilité : b divise a si et seulement si le reste r = 0.
③Nombres premiers et décomposition en facteurs premiers
Certains entiers sont « indivisibles » : 7 ne s'écrit que 1 × 7. Ce sont les nombres premiers, les briques élémentaires : tout entier supérieur ou égal à 2 est soit premier, soit un produit de nombres premiers. C'est pourquoi on en a besoin pour le PGCD et le PPCM.
Il suffit de tester les diviseurs premiers inférieurs ou égaux à √n. Pourquoi ? Si n avait un diviseur d > √n, alors n ÷ d serait un diviseur inférieur à √n, qu'on aurait déjà trouvé. On teste donc seulement le « petit côté ».
Exemple : 113 est-il premier ? √113 ≈ 10,6, donc tester 2, 3, 5, 7. Aucun ne divise 113, donc 113 est premier.
Puisque les premiers sont les briques de base, tout entier supérieur ou égal à 2 se « décortique » en un produit de ces briques : c'est la décomposition en facteurs premiers. On divise successivement par le plus petit premier qui divise (2, puis 3, puis 5…) jusqu'à tomber sur 1.
Une décomposition unique : le théorème fondamental de l'arithmétique
④PGCD et PPCM : les deux outils du concours
PGCD(a, b) est le plus grand entier qui divise à la fois a et b (on travaille avec des entiers naturels non nuls). Reprenons les 84 feuilles et 126 crayons : le nombre de lots doit diviser 84 et 126, et on en veut le maximum, donc on cherche le PGCD.
Premiers entre eux : a et b sont premiers entre eux quand PGCD(a, b) = 1. Cela ne veut pas dire que chacun est premier : 8 et 15 sont premiers entre eux (PGCD = 1) bien qu'aucun ne soit premier. Application directe : rendre une fraction irréductible en divisant numérateur et dénominateur par leur PGCD (36/48, PGCD = 12, donne 3/4 ; voir la fiche N°3).
PPCM(a, b) est le plus petit entier strictement positif multiple à la fois de a et de b : l'image miroir du PGCD. Pour les deux bus (8 min et 12 min), les multiples de 8 sont 8, 16, 24… ; ceux de 12 sont 12, 24… ; le premier commun est 24.
Pourquoi pas a × b ? 8 × 12 = 96 est bien un multiple commun, mais pas le plus petit. Diviser par le PGCD retire ce que a et b ont déjà en commun.
Les 3 situations où le PPCM est la clé : additionner des fractions à dénominateurs différents (1/8 + 1/12 → dénominateur commun PPCM(8, 12) = 24, soit 3/24 + 2/24 = 5/24) ; les problèmes de conjonction (bus, navettes, carillons, engrenages : deux phénomènes périodiques coïncident au PPCM des périodes) ; trouver le plus petit dénominateur commun.
Piège n°1 : croire que 1 est premier
On croit : « 1 est premier car il n'est divisible que par 1. »
En réalité : 1 est exclu des premiers : un premier a exactement deux diviseurs distincts (1 et lui-même), or 1 n'en a qu'un.
Cette convention garantit l'unicité de la décomposition en facteurs premiers.
Piège n°2 : confondre PGCD et PPCM
On croit : « Pour additionner 1/12 + 1/8, j'utilise le PGCD comme dénominateur commun. »
En réalité : Le dénominateur commun est le PPCM. PPCM(12, 8) = 24, donc 1/12 + 1/8 = 2/24 + 3/24 = 5/24.
PGCD = le plus grand qui divise les deux → fraction irréductible. PPCM = le plus petit multiple commun → dénominateur commun.
Piège n°3 : tester la primalité trop tôt
On croit : « 91 n'est divisible ni par 2, ni par 3, ni par 5, donc 91 est premier. »
En réalité : √91 ≈ 9,5 : il faut tester jusqu'à 9, donc aussi 7. Or 91 = 7 × 13. 91 n'est pas premier.
Tester tous les premiers inférieurs ou égaux à √n. Ne pas s'arrêter à 5.
Piège n°4 : mal lire l'algorithme d'Euclide
On croit : S'arrêter au reste 1, ou lire le quotient de la dernière ligne comme PGCD.
En réalité : On s'arrête quand le reste est 0. Le PGCD est le dernier reste non nul, c'est-à-dire le diviseur de la dernière ligne.
La justification repose sur PGCD(a, b) = PGCD(b, r).
Le mot « PGCD » n'apparaît pas à l'école, mais la notion de diviseur commun s'y construit, et le jury valorise ce lien.
Cycles 2 et 3 : les tables de multiplication font découvrir implicitement la divisibilité (18 est dans la table de 2, 3, 6, 9). Le programme (BOEN 2020) introduit explicitement en cycle 3 les notions de multiple et de diviseur, les critères de divisibilité par 2, 3, 4, 5, 9 et 10, et la simplification de fractions par diviseurs communs visibles (sans PGCD formel).
Justifier un critère dès le CM2 : « 100 = 99 + 1 = 33 × 3 + 1, donc 100 a le même reste que 1 dans la division par 3. » Expliquer pourquoi un critère fonctionne, c'est déjà enseigner le raisonnement. L'arithmétique est un domaine privilégié pour le raisonnement par disjonction de cas, par l'absurde ou par contre-exemple, ce que le jury apprécie.
Méthode
Quatre savoir-faire exigibles au concours
Quelle méthode pour le PGCD ?
Calculer PGCD(48, 36) par l'algorithme d'Euclide.
On donne 12 = 2² × 3 et 18 = 2 × 3². Donner PGCD et PPCM par lecture des décompositions.
Deux phares clignotent toutes les 15 s et toutes les 20 s, ensemble à un instant donné. Au bout de combien de temps coïncident-ils de nouveau ?
101 est-il premier ? Justifier brièvement.