Mathématiques du primaire et du collège · Grades 1–9

64Arithmétique : diviseurs et nombres premiers

L’arithmétique étudie les nombres entiers et la façon dont ils se divisent les uns les autres. Ses personnages centraux sont les nombres premiers, les briques de base à partir desquelles tout entier s’assemble par multiplication. Le chapitre se termine par le plus grand commun diviseur, l’outil juste pour simplifier les fractions une fois pour toutes. Cette histoire se poursuit, bien plus loin, dans le volume de lycée et au-delà.

64.1 Diviseurs et multiples

Définition 64.1 (Diviseur, multiple)

Soient $a$ et $b$ des entiers positifs. On dit que $b$ divise $a$ (ou que $b$ est un diviseur de $a$ , ou que $a$ est un multiple de $b$ ) lorsque $a = b \times k$ pour un certain entier $k$ — c’est-à-dire lorsque la division de $a$ par $b$ laisse un reste $0$ .

Exemple 64.2

Les diviseurs de $24$ sont $1, 2, 3, 4, 6, 8, 12, 24$ — ils viennent par paires dont le produit est $24$ : $(1,24)$ , $(2,12)$ , $(3,8)$ , $(4,6)$ . Les multiples de $7$ sont $7, 14, 21, 28, \dots$

Proposition 64.3 (Critères de divisibilité)

Un entier est divisible :

par $2$ lorsque son dernier chiffre est pair ( $0, 2, 4, 6, 8$ ) ;
par $5$ lorsque son dernier chiffre est $0$ ou $5$ ;
par $10$ lorsque son dernier chiffre est $0$ ;
par $3$ (resp. $9$ ) lorsque la somme de ses chiffres est divisible par $3$ (resp. $9$ ) ;
par $4$ lorsque ses deux derniers chiffres forment un nombre divisible par $4$ .

Démonstration. Admis à ce niveau. ∎

Exemple 64.4

$7\,215$ se termine par $5$ : divisible par $5$ . Sa somme de chiffres est $7 + 2 + 1 + 5 = 15$ , divisible par $3$ mais pas par $9$ : donc $7\,215$ est divisible par $3$ , pas par $9$ . En effet $7\,215 = 3 \times 5 \times 481$ .

64.2 Nombres premiers

Définition 64.5 (Nombre premier)

Un nombre premier est un entier $\geq 2$ dont les seuls diviseurs sont $1$ et lui-même. Les premiers inférieurs à $30$ sont

2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29 .

Le nombre $1$ n’est pas premier (par convention), et un entier $\geq 2$ qui n’est pas premier s’appelle composé.

Théorème 64.6 (Décomposition en facteurs premiers)

Tout entier $\geq 2$ est un produit de nombres premiers, et cette décomposition est unique à l’ordre des facteurs près.

Démonstration. Admis à ce niveau. ∎

Méthode 64.7 (Décomposer un entier)

Diviser par le plus petit premier possible, de façon répétée, jusqu’à atteindre $1$ :

essayer $2$ tant que le nombre est pair ;
puis essayer $3$ , puis $5$ , puis $7$ , … (seulement des premiers) ;
s’arrêter lorsque le quotient est $1$ ; collecter les facteurs avec exposants.

Il suffit d’essayer les premiers $p$ avec $p^2$ ne dépassant pas le nombre courant : si aucun ne le divise, le nombre lui-même est premier.

Exemple 64.8

Décomposer $360$ , une division à la fois :

360 = 2 \times 180, \quad 180 = 2 \times 90, \quad 90 = 2 \times 45, \quad 45 = 3 \times 15, \quad 15 = 3 \times 5,

donc

360 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^3 \times 3^2 \times 5 .

L’arbre de facteurs de 360 : chaque étape détache le plus petit facteur premier (en rouge). En lisant les feuilles rouges et le 5 final : 360 = 23 × 32 × 5. — L’arbre de facteurs de $360$ : chaque étape détache le plus petit facteur premier (en rouge). En lisant les feuilles rouges et le $5$ final : $360 = 2^3 \times 3^2 \times 5$ .

Théorème 64.9 (Euclide)

Il existe une infinité de nombres premiers.

Démonstration. Supposons qu’il n’y en ait qu’un nombre fini, disons $p_1, p_2, \dots, p_k$ , et considérer

N = p_1 \times p_2 \times \dots \times p_k + 1 .

Diviser $N$ par n’importe quel $p_i$ laisse un reste $1$ , donc aucun $p_i$ ne divise $N$ . Mais $N \geq 2$ a au moins un diviseur premier (Théorème 64.6) — un premier qui n’est pas dans notre liste. Contradiction : aucune liste finie ne peut contenir tous les premiers. ∎

64.3 Le plus grand commun diviseur

Définition 64.10 (PGCD)

Le plus grand commun diviseur de deux entiers positifs $a$ et $b$ , noté $\gcd(a, b)$ , est le plus grand entier divisant les deux. Lorsque $\gcd(a, b) = 1$ , les entiers sont dits premiers entre eux : ils ne partagent aucun diviseur excepté $1$ .

Exemple 64.11

Diviseurs de $18$ : $1, 2, 3, 6, 9, 18$ . Diviseurs de $24$ : $1, 2, 3, 4, 6, 8, 12, 24$ . Diviseurs communs : $1, 2, 3, 6$ ; donc $\gcd(18, 24) = 6$ . Les entiers $15$ et $28$ sont premiers entre eux.

Proposition 64.12 (PGCD à partir des décompositions)

Le PGCD de deux entiers est le produit des premiers apparaissant dans les deux décompositions, chacun pris avec le plus petit de ses deux exposants.

Démonstration. Admis à ce niveau. ∎

Exemple 64.13

$360 = 2^3 \times 3^2 \times 5$ et $84 = 2^2 \times 3 \times 7$ . Premiers communs : $2$ (exposants $3$ et $2$ : garder $2$ ) et $3$ (exposants $2$ et $1$ : garder $1$ ). Donc

\gcd(360, 84) = 2^2 \times 3 = 12 .

Théorème 64.14 (Algorithme d’Euclide)

Si $a = bq + r$ est la division de $a$ par $b$ avec reste $r$ , alors

\gcd(a, b) = \gcd(b, r).

En répétant les divisions jusqu’à ce que le reste soit $0$ , le PGCD de $a$ et $b$ est le dernier reste non nul.

Démonstration. De $a = bq + r$ : tout entier divisant $b$ et $r$ divise $bq + r = a$ ; et de $r = a - bq$ : tout entier divisant $a$ et $b$ divise $r$ . Donc les paires $(a, b)$ et $(b, r)$ ont exactement les mêmes diviseurs communs — en particulier le même plus grand. Puisque les restes décroissent strictement, l’algorithme se termine, et $\gcd(x, 0) = x$ donne le dernier reste non nul. ∎

Exemple 64.15

Calculer $\gcd(1071, 462)$ :

\begin{align*} 1071 &= 462 \times 2 + 147, \\ 462 &= 147 \times 3 + 21, \\ 147 &= 21 \times 7 + 0 . \end{align*}

Le dernier reste non nul est $21$ : $\gcd(1071, 462) = 21$ .

Méthode 64.16 (Simplifier complètement une fraction)

Pour écrire $\dfrac ab$ sous forme irréductible :

calculer $d = \gcd(a, b)$ , par ex. par l’algorithme d’Euclide ;
diviser numérateur et dénominateur par $d$ : $\dfrac ab = \dfrac{a \div d}{b \div d}$ ;
la fraction résultante est irréductible : son numérateur et son dénominateur sont premiers entre eux.

Exemple 64.17

$\dfrac{462}{1071} = \dfrac{462 \div 21}{1071 \div 21} = \dfrac{22}{51}$ , et $\gcd(22, 51) = 1$ : irréductible.

64.4 Exercices

Exercice 64.1 ★

Lister tous les diviseurs de $36$ , de $45$ , et de $17$ .

Solution

Solution de Exercice 64.1.

Diviseurs de $36$ : $1, 2, 3, 4, 6, 9, 12, 18, 36$ . Diviseurs de $45$ : $1, 3, 5, 9, 15, 45$ . Diviseurs de $17$ : $1$ et $17$ seulement ( $17$ est premier).

Exercice 64.2 ★

En utilisant les critères de divisibilité, déterminer si $2\,346$ est divisible par $2$ , par $3$ , par $4$ , par $5$ , par $9$ .

Solution

Solution de Exercice 64.2.

$2\,346$ se termine par $6$ : divisible par $2$ , pas par $5$ . Somme des chiffres $2 + 3 + 4 + 6 = 15$ : divisible par $3$ , pas par $9$ . Les deux derniers chiffres $46$ , et $46 = 4 \times 11 + 2$ n’est pas divisible par $4$ : $2\,346$ n’est pas divisible par $4$ .

Exercice 64.3 ★

Donner la décomposition en facteurs premiers de $72$ , $150$ , $210$ et $121$ .

Solution

Solution de Exercice 64.3.

$72 = 2^3 \times 3^2$ ; $150 = 2 \times 3 \times 5^2$ ; $210 = 2 \times 3 \times 5 \times 7$ ; $121 = 11^2$ .

Exercice 64.4 ★

$101$ est-il premier ? $91$ ? $143$ ? Justifier en utilisant la règle d’arrêt de Méthode 64.7.

Solution

Solution de Exercice 64.4.

$101$ : tester les premiers $p$ avec $p^2 \leq 101$ , c’est-à-dire $2, 3, 5, 7$ . Aucun ne divise $101$ (impair, somme des chiffres $2$ , ne se termine pas par $0/5$ , $101 = 7 \times 14 + 3$ ) : $101$ est premier.

$91 = 7 \times 13$ : pas premier.

$143 = 11 \times 13$ : pas premier.

Exercice 64.5 ★

Calculer $\gcd(48, 60)$ de deux façons : en listant les diviseurs communs, et à partir des décompositions en facteurs premiers.

Solution

Solution de Exercice 64.5.

Diviseurs communs de $48$ et $60$ : diviseurs de $48$ : $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$ ; diviseurs de $60$ : $1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60$ ; les communs sont $1, 2, 3, 4, 6, 12$ , donc $\gcd(48,60) = 12$ .

Par décomposition : $48 = 2^4 \times 3$ et $60 = 2^2 \times 3 \times 5$ ; premiers communs avec plus petits exposants : $2^2 \times 3 = 12$ .

Exercice 64.6 ★★

Utiliser l’algorithme d’Euclide pour calculer $\gcd(255, 154)$ , puis $\gcd(1053, 325)$ . Écrire chaque ligne de division.

Solution

Solution de Exercice 64.6.

$\gcd(255, 154)$ :

\begin{align*} 255 &= 154 \times 1 + 101, \\ 154 &= 101 \times 1 + 53, \\ 101 &= 53 \times 1 + 48, \\ 53 &= 48 \times 1 + 5, \\ 48 &= 5 \times 9 + 3, \\ 5 &= 3 \times 1 + 2, \\ 3 &= 2 \times 1 + 1, \\ 2 &= 1 \times 2 + 0 . \end{align*}

Dernier reste non nul : $\gcd(255, 154) = 1$ (ils sont premiers entre eux).

$\gcd(1053, 325)$ :

\begin{align*} 1053 &= 325 \times 3 + 78, \\ 325 &= 78 \times 4 + 13, \\ 78 &= 13 \times 6 + 0 . \end{align*}

$\gcd(1053, 325) = 13$ .

Exercice 64.7 ★★

Rendre irréductible la fraction $\dfrac{588}{504}$ . (Calculer le PGCD par la méthode de son choix, puis diviser.)

Solution

Solution de Exercice 64.7.

Algorithme d’Euclide : $588 = 504 \times 1 + 84$ ; $504 = 84 \times 6 + 0$ : $\gcd(588, 504) = 84$ . Puis

\frac{588}{504} = \frac{588 \div 84}{504 \div 84} = \frac{7}{6},

qui est irréductible.

Exercice 64.8 ★★

Une fleuriste a $84$ roses et $126$ tulipes et veut faire des bouquets identiques, en utilisant toutes les fleurs, avec autant de bouquets que possible. Combien de bouquets peut-elle faire, et que contient chacun ?

Solution

Solution de Exercice 64.8.

Le nombre de bouquets doit diviser à la fois $84$ et $126$ ; le plus grand possible est $\gcd(84, 126)$ . Décompositions : $84 = 2^2 \times 3 \times 7$ , $126 = 2 \times 3^2 \times 7$ , donc le PGCD est $2 \times 3 \times 7 = 42$ . Elle peut faire $42$ bouquets, chacun contenant $\frac{84}{42} = 2$ roses et $\frac{126}{42} = 3$ tulipes.

Exercice 64.9 ★★

Deux ferries quittent le même quai à 8:00. L’un part toutes les $24$ minutes, l’autre toutes les $36$ minutes. À quelle heure repartent-ils ensemble la prochaine fois ? (Chercher le plus petit multiple commun de $24$ et $36$ ; les décompositions aident.)

Solution

Solution de Exercice 64.9.

On cherche le plus petit multiple commun. $24 = 2^3 \times 3$ et $36 = 2^2 \times 3^2$ ; en prenant chaque premier avec le plus grand exposant : $\operatorname{ppcm} = 2^3 \times 3^2 = 72$ . Les ferries repartent ensemble $72$ minutes après 8:00, à 9:12.

Exercice 64.10 ★★★

Soit $n$ un entier positif.

Montrer que $\gcd(n, n+1) = 1$ (les entiers consécutifs sont toujours premiers entre eux).
En déduire que la fraction $\dfrac{n}{n+1}$ est toujours irréductible.

Solution

Solution de Exercice 64.10.

1. Tout diviseur commun $d$ de $n$ et $n+1$ divise aussi leur différence $(n+1) - n = 1$ , donc $d = 1$ : $\gcd(n, n+1) = 1$ .

2. Une fraction est irréductible exactement lorsque son numérateur et son dénominateur sont premiers entre eux, ce qui est le cas pour $n$ et $n + 1$ par le point 1.