Divisibilité et décomposition en facteurs premiers
Les nombres
Divisibilité et décomposition en facteurs premiers
Divisibilité dans $\mathbb{Z}$
Définition
Soient $a$ et $b$ deux entiers avec $a \neq 0$. On dit que $a$ divise $b$ (noté $a \mid b$) s'il existe un entier $k$ tel que :
$$b = k \times a$$
On dit aussi que $b$ est un multiple de $a$, ou que $a$ est un diviseur de $b$.
Exemples :
- $3 \mid 12$ car $12 = 4 \times 3$
- $5 \mid 35$ car $35 = 7 \times 5$
- $4 \nmid 10$ car $10 = 2 \times 4 + 2$ (il reste 2)
Critères de divisibilité
| Diviseur | Critère | Exemple |
|---|---|---|
| 2 | Le dernier chiffre est pair (0, 2, 4, 6, 8) | $1\,346$ : oui (6 pair) |
| 3 | La somme des chiffres est divisible par 3 | $612$ : $6+1+2=9$ divisible par 3 |
| 4 | Les deux derniers chiffres forment un multiple de 4 | $1\,324$ : $24 = 4 \times 6$ oui |
| 5 | Le dernier chiffre est 0 ou 5 | $1\,235$ : oui |
| 9 | La somme des chiffres est divisible par 9 | $729$ : $7+2+9=18$ divisible par 9 |
| 10 | Le dernier chiffre est 0 | $1\,230$ : oui |
La division euclidienne
Pour tout entier $a \geq 0$ et tout entier $b > 0$, il existe un unique couple $(q, r)$ tel que :
$$a = b \times q + r \quad \text{avec} \quad 0 \leq r < b$$
- $q$ est le quotient de la division euclidienne.
- $r$ est le reste.
Exemple : $47 = 6 \times 7 + 5$, donc le quotient de $47$ par $6$ est $7$ et le reste est $5$.
En Python : 47 // 6 donne 7 (quotient) et 47 % 6 donne 5 (reste).
PGCD — Plus Grand Commun Diviseur
Définition
Le PGCD de deux entiers $a$ et $b$ (non tous deux nuls) est le plus grand entier qui divise à la fois $a$ et $b$.
Algorithme d'Euclide
On effectue des divisions euclidiennes successives. Le PGCD est le dernier reste non nul.
Exemple : PGCD(48, 18)
Division Quotient Reste $48 = 18 \times 2 + 12$ 2 12 $18 = 12 \times 1 + 6$ 1 6 $12 = 6 \times 2 + 0$ 2 0 Donc $\text{PGCD}(48, 18) = 6$.
PPCM — Plus Petit Commun Multiple
$$\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$$
Exemple : $\text{PPCM}(48, 18) = \frac{48 \times 18}{6} = 144$.
Les nombres premiers
Définition
Un entier $n \geq 2$ est premier si ses seuls diviseurs positifs sont $1$ et $n$ lui-même.
Premiers nombres premiers : $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, \ldots$
Remarques :
- $1$ n'est pas premier (par convention).
- $2$ est le seul nombre premier pair.
Test de primalité
Pour vérifier si $n$ est premier, il suffit de tester la divisibilité par tous les entiers de $2$ à $\sqrt{n}$ :
Si aucun de ces entiers ne divise $n$, alors $n$ est premier.
Exemple : $37$ est-il premier ?
$\sqrt{37} \approx 6{,}08$ → on teste $2, 3, 4, 5, 6$.
Aucun ne divise $37$, donc $37$ est premier.
Décomposition en facteurs premiers
Théorème fondamental de l'arithmétique
Tout entier $n \geq 2$ se décompose de façon unique en un produit de nombres premiers (à l'ordre près).
Méthode pratique
On divise successivement par les nombres premiers $2, 3, 5, 7, 11, \ldots$
Exemple : Décomposons $360$.
Étape Division Résultat 1 $360 \div 2 = 180$ $2$ 2 $180 \div 2 = 90$ $2$ 3 $90 \div 2 = 45$ $2$ 4 $45 \div 3 = 15$ $3$ 5 $15 \div 3 = 5$ $3$ 6 $5 \div 5 = 1$ $5$ Donc : $360 = 2^3 \times 3^2 \times 5$
Application : simplification de fractions
Pour simplifier $\frac{48}{180}$, on décompose :
- $48 = 2^4 \times 3$
- $180 = 2^2 \times 3^2 \times 5$
Le PGCD est $2^2 \times 3 = 12$, donc :
$$\frac{48}{180} = \frac{48 \div 12}{180 \div 12} = \frac{4}{15}$$
À retenir
- $a \mid b$ signifie qu'il existe $k \in \mathbb{Z}$ tel que $b = ka$.
- Les critères de divisibilité permettent de tester rapidement si un nombre est divisible par 2, 3, 5 ou 9.
- L'algorithme d'Euclide calcule le PGCD par des divisions euclidiennes successives.
- Tout entier $\geq 2$ se décompose de manière unique en produit de facteurs premiers.
- Un nombre est premier s'il n'est divisible par aucun entier de $2$ à $\sqrt{n}$.