Divisibilité et nombres premiers : les briques des entiers

Prends deux entiers, $63$ et $9$. La division $63 \div 9$ tombe juste : $63 = 9 \times 7$, il ne reste rien. On dit alors que $9$ divise $63$.

Dans le cadre de cette leçon, $a$ est un entier naturel et $b$ un entier naturel strictement positif. On dit que $b$ divise $a$ lorsqu’il existe un entier naturel $k$ tel que $a = b \times k$. La division de $a$ par $b$ est alors définie et son reste est nul.

Cette même phrase se lit dans les deux sens, et c'est là que beaucoup d'élèves se perdent :

Pour les nombres strictement positifs et les multiples positifs comparés ici :

Une seule relation, deux mots selon le point de vue. $9$ divise $63$ ; $63$ est divisible par $9$. Le nombre $0$ est aussi un multiple de tout entier naturel positif, car $0 = b \times 0$ ; il ne respecte pas la comparaison de taille réservée aux multiples positifs dans le tableau.

Les critères de divisibilité permettent de répondre sans poser la division :

Pourquoi le critère de $9$ fonctionne-t-il ? Ce n'est pas magique. Décompose $4\,383$ selon la position des chiffres :

Remplace maintenant $1\,000$ par $999 + 1$, $100$ par $99 + 1$ et $10$ par $9 + 1$ :

Les trois premiers morceaux sont des multiples de $9$, quoi qu'il arrive. Il ne reste donc qu'une question : la somme des chiffres, $18$, est-elle un multiple de $9$ ? Oui. Donc $4\,383$ aussi. Et comme $9$ est lui-même un multiple de $3$, le même raisonnement donne le critère de $3$.

Le nombre premier, enfin :

Un entier naturel est premier lorsqu’il possède exactement deux diviseurs positifs distincts : $1$ et lui-même.

$7$ est premier : ses seuls diviseurs sont $1$ et $7$. $12$ ne l'est pas : $1$, $2$, $3$, $4$, $6$, $12$. Et $1$ n'est pas premier : il n'a qu'un seul diviseur, lui-même. Le premier nombre premier est $2$ — c'est aussi le seul qui soit pair, puisque tout autre nombre pair est divisible par $2$ en plus de $1$ et de lui-même.

Tout entier plus grand que $1$ s'écrit comme un produit de nombres premiers, et d'une seule façon (à l'ordre des facteurs près). C'est le théorème fondamental de l'arithmétique ; au collège, on l'admet. Les nombres premiers sont donc aux entiers ce que les briques sont à un mur : on ne peut pas les casser plus petit, et il n'y a qu'une seule façon de bâtir chaque mur.

La méthode, par divisions successives : on divise par le plus petit nombre premier possible, on recommence avec le quotient, jusqu'à obtenir $1$.

On regroupe les facteurs répétés avec un exposant :

Comment savoir qu'un nombre est premier ? On teste les nombres premiers dans l'ordre croissant, et on peut s'arrêter dès que le carré du candidat dépasse le nombre. Pour $149$ : pas divisible par $2$ (impair), ni par $3$ ($1+4+9 = 14$), ni par $5$ (il finit par $9$), ni par $7$ ($7 \times 21 = 147$), ni par $11$ ($11 \times 13 = 143$), ni par $13$ ($13 \times 11 = 143$ et $13 \times 12 = 156$). Or $13^{2} = 169 > 149$ : inutile d'aller plus loin. Pourquoi ? Parce que si $149$ avait un diviseur plus grand que $13$, le facteur qui l'accompagne serait plus petit que $13$ — et on l'aurait déjà trouvé. Donc $149$ est premier.

À quoi sert la décomposition ?

1. Trouver tous les diviseurs. Chaque diviseur se fabrique en piochant dans les briques. Pour $252 = 2^{2} \times 3^{2} \times 7$, on décide, brique par brique, combien on en prend : zéro, un ou deux $2$ ; zéro, un ou deux $3$ ; zéro ou un $7$. Par exemple $2 \times 3 \times 7 = 42$ divise bien $252$, et $2^{2} \times 3^{2} = 36$ aussi. En épuisant tous les choix, on obtient les $18$ diviseurs de $252$ — l’exemple guidé illustre ensuite la recherche par paires sur $36$, qui possède neuf diviseurs positifs.
2. Trouver le plus grand diviseur commun à deux nombres : on garde les facteurs premiers présents dans les deux décompositions, chacun avec son plus petit exposant.
3. Rendre une fraction irréductible : on simplifie par ce plus grand diviseur commun. Une fraction est irréductible quand son numérateur et son dénominateur n'ont plus aucun facteur premier en commun.
4. Faire coïncider deux phénomènes qui se répètent — deux engrenages, deux feux qui clignotent, deux bus qui passent : on cherche cette fois le plus petit multiple commun. On garde alors tous les facteurs premiers des deux décompositions, chacun au plus grand exposant. C'est l'exact symétrique de la règle précédente : plus petit exposant pour un diviseur commun, plus grand exposant pour un multiple commun.

L'exemple type du quatrième usage. Deux ampoules s'allument ensemble à minuit ; l'une se rallume toutes les $153$ s, l'autre toutes les $187$ s. Quand se rallumeront-elles en même temps ? On décompose : $153 = 3^{2} \times 17$ et $187 = 11 \times 17$. On garde tout, au plus grand exposant : $3^{2} \times 11 \times 17 = 1\,683$ s, c'est-à-dire $1\,683 = 28 \times 60 + 3$, soit 28 min 3 s après minuit. Vérification : $1\,683 \div 153 = 11$ et $1\,683 \div 187 = 9$, deux divisions exactes.

Deux remarques honnêtes.

• Tu pourras rencontrer les sigles PGCD, PPCM et l’algorithme d’Euclide. Ici, on explicite les termes et on utilise la décomposition en facteurs premiers ; aucun libellé universel de tout sujet du brevet n’est garanti.
• Les nombres premiers ne s'arrêtent jamais : Euclide a démontré, il y a plus de deux mille ans, qu'il en existe une infinité. Cette infinité n’est pas une affirmation d’impossibilité de toute formule : la leçon établit des méthodes de test et de décomposition, sans traiter toutes les constructions théoriques de nombres premiers.

Énoncé. Rendre la fraction $\dfrac{252}{180}$ irréductible.

1. Décomposer les deux nombres. Divisions successives par le plus petit nombre premier possible.

Contrôle : $4 \times 9 \times 7 = 252$ et $4 \times 9 \times 5 = 180$. Les deux produits retombent bien sur les nombres de départ — cette vérification prend cinq secondes et attrape presque toutes les erreurs.

2. Repérer les facteurs communs. $2$ apparaît dans les deux décompositions, avec l'exposant $2$ des deux côtés. $3$ aussi, avec l'exposant $2$. Le $7$ n'est que dans $252$, le $5$ n'est que dans $180$ : on ne les garde pas.

3. Simplifier. On divise le numérateur et le dénominateur par $36$ :

4. Vérifier que c'est bien irréductible. $7$ est premier, $5$ est premier, et ils sont différents : ils n'ont aucun facteur commun. La fraction ne peut plus être simplifiée. Contrôle numérique : $252 \div 180 = 1{,}4$ et $7 \div 5 = 1{,}4$ — les deux écritures désignent le même nombre.

5. Pour aller au bout : combien $36$ a-t-il de diviseurs ? On les cherche par paires : chaque diviseur trouvé en donne un second.

La dernière paire est faite de deux fois le même nombre : $6$ ne se compte qu'une fois. Les diviseurs de $36$ sont donc $1$, $2$, $3$, $4$, $6$, $9$, $12$, $18$ et $36$ : il y en a neuf. On peut s'arrêter dès que le candidat dépasse $6$, car $6^{2} = 36$ : au-delà, on retrouverait les mêmes paires à l'envers.

Lire la figure (fig.math.prime-factor-tree) : les deux décompositions de l'exemple, présentées comme deux échelles de division posées l'une à côté de l'autre.

• Échelle de gauche, titrée $252$. Cinq lignes ; à chaque ligne, le nombre à gauche d'une barre verticale, le diviseur premier à droite : $252 \mid 2$, puis $126 \mid 2$, puis $63 \mid 3$, puis $21 \mid 3$, puis $7 \mid 7$, et enfin $1$ seul sur la dernière ligne. Une flèche descendante relie chaque nombre au suivant.
• Échelle de droite, titrée $180$, construite de la même façon : $180 \mid 2$, $90 \mid 2$, $45 \mid 3$, $15 \mid 3$, $5 \mid 5$, puis $1$.
• Colonne des diviseurs mise en avant : les facteurs premiers de la colonne de droite de chaque échelle sont encadrés. Les facteurs qui apparaissent dans les deux échelles ($2$, $2$, $3$, $3$) portent en plus un fond hachuré — la couleur seule ne doit jamais porter l'information.
• Sous les deux échelles, trois lignes de bilan : $252 = 2^{2} \times 3^{2} \times 7$ ; $180 = 2^{2} \times 3^{2} \times 5$ ; puis, sur une ligne encadrée, « facteurs communs : $2^{2} \times 3^{2} = 36$ ».
• Tout en bas, la conclusion : $\dfrac{252}{180} = \dfrac{7}{5}$, avec le $36$ barré au numérateur et au dénominateur.

Ce qu'il faut lire. Les deux échelles ont le même début — $2$, $2$, $3$, $3$ — puis divergent : $7$ d'un côté, $5$ de l'autre. C'est exactement ce début commun qui fait le plus grand diviseur commun, et c'est la divergence qui fait la fraction irréductible. Retiens l'image : décomposer, c'est descendre une échelle ; comparer deux nombres, c'est comparer deux échelles marche par marche.

La figure en détail : deux colonnes de calcul côte à côte. La colonne de gauche part de 252 et donne successivement les quotients 126, 63, 21, 7, 1 en divisant par 2, 2, 3, 3, 7. La colonne de droite part de 180 et donne 90, 45, 15, 5, 1 en divisant par 2, 2, 3, 3, 5. Les diviseurs 2, 2, 3, 3 sont présents dans les deux colonnes et sont signalés par un fond hachuré. En bas, trois égalités : 252 égale 2 puissance 2 fois 3 puissance 2 fois 7 ; 180 égale 2 puissance 2 fois 3 puissance 2 fois 5 ; facteurs communs égale 36. Conclusion : 252 sur 180 égale 7 sur 5.