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 = b \times q + r \quad \text{avec} \quad 0 \leq r < b$$0) s'il existe un entier $$a = b \times q + r \quad \text{avec} \quad 0 \leq r < b$$1 tel que :
$$b = k \times a$$
On dit aussi que $$a = b \times q + r \quad \text{avec} \quad 0 \leq r < b$$2 est un multiple de $$a = b \times q + r \quad \text{avec} \quad 0 \leq r < b$$3, ou que $$a = b \times q + r \quad \text{avec} \quad 0 \leq r < b$$4 est un diviseur de $$a = b \times q + r \quad \text{avec} \quad 0 \leq r < b$$5.
Exemples :
- $$a = b \times q + r \quad \text{avec} \quad 0 \leq r < b$$6 car $$a = b \times q + r \quad \text{avec} \quad 0 \leq r < b$$7
- $$a = b \times q + r \quad \text{avec} \quad 0 \leq r < b$$8 car $$a = b \times q + r \quad \text{avec} \quad 0 \leq r < b$$9
- $$\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$$0 car $$\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$$1 (il reste 2)
Critères de divisibilité
| Diviseur | Critère | Exemple |
|---|---|---|
| 2 | Le dernier chiffre est pair (0, 2, 4, 6, 8) | $$\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$$2 : oui (6 pair) |
| 3 | La somme des chiffres est divisible par 3 | $$\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$$3 : $$\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$$4 divisible par 3 |
| 4 | Les deux derniers chiffres forment un multiple de 4 | $$\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$$5 : $$\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$$6 oui |
| 5 | Le dernier chiffre est 0 ou 5 | $$\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$$7 : oui |
| 9 | La somme des chiffres est divisible par 9 | $$\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$$8 : $$\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$$9 divisible par 9 |
| 10 | Le dernier chiffre est 0 | $$\frac{48}{180} = \frac{48 \div 12}{180 \div 12} = \frac{4}{15}$$0 : oui |
La division euclidienne
Pour tout entier $$\frac{48}{180} = \frac{48 \div 12}{180 \div 12} = \frac{4}{15}$$1 et tout entier $$\frac{48}{180} = \frac{48 \div 12}{180 \div 12} = \frac{4}{15}$$2, il existe un unique couple $$\frac{48}{180} = \frac{48 \div 12}{180 \div 12} = \frac{4}{15}$$3 tel que :
$$a = b \times q + r \quad \text{avec} \quad 0 \leq r < b$$
- $$\frac{48}{180} = \frac{48 \div 12}{180 \div 12} = \frac{4}{15}$$4 est le quotient de la division euclidienne.
- $$\frac{48}{180} = \frac{48 \div 12}{180 \div 12} = \frac{4}{15}$$5 est le reste.
Exemple : $$\frac{48}{180} = \frac{48 \div 12}{180 \div 12} = \frac{4}{15}$$6, donc le quotient de $$\frac{48}{180} = \frac{48 \div 12}{180 \div 12} = \frac{4}{15}$$7 par $$\frac{48}{180} = \frac{48 \div 12}{180 \div 12} = \frac{4}{15}$$8 est $$\frac{48}{180} = \frac{48 \div 12}{180 \div 12} = \frac{4}{15}$$9 et le reste est $\mathbb{Z}$0.
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 $\mathbb{Z}$1 et $\mathbb{Z}$2 (non tous deux nuls) est le plus grand entier qui divise à la fois $\mathbb{Z}$3 et $\mathbb{Z}$4.
Algorithme d'Euclide
On effectue des divisions euclidiennes successives. Le PGCD est le dernier reste non nul.
Exemple : PGCD(48, 18)
Division Quotient Reste $\mathbb{Z}$5 2 12 $\mathbb{Z}$6 1 6 $\mathbb{Z}$7 2 0 Donc $\mathbb{Z}$8.
PPCM — Plus Petit Commun Multiple
$$\text{PPCM}(a, b) = \frac{a \times b}{\text{PGCD}(a, b)}$$
Exemple : $\mathbb{Z}$9.
Les nombres premiers
Définition
Un entier $a$0 est premier si ses seuls diviseurs positifs sont $a$1 et $a$2 lui-même.
Premiers nombres premiers : $a$3
Remarques :
- $a$4 n'est pas premier (par convention).
- $a$5 est le seul nombre premier pair.
Test de primalité
Pour vérifier si $a$6 est premier, il suffit de tester la divisibilité par tous les entiers de $a$7 à $a$8 :
Si aucun de ces entiers ne divise $a$9, alors $b$0 est premier.
Exemple : $b$1 est-il premier ?
$b$2 → on teste $b$3.
Aucun ne divise $b$4, donc $b$5 est premier.
Décomposition en facteurs premiers
Théorème fondamental de l'arithmétique
Tout entier $b$6 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 $b$7
Exemple : Décomposons $b$8.
Étape Division Résultat 1 $b$9 $a \neq 0$0 2 $a \neq 0$1 $a \neq 0$2 3 $a \neq 0$3 $a \neq 0$4 4 $a \neq 0$5 $a \neq 0$6 5 $a \neq 0$7 $a \neq 0$8 6 $a \neq 0$9 $a$0 Donc : $a$1
Application : simplification de fractions
Pour simplifier $a$2, on décompose :
- $a$3
- $a$4
Le PGCD est $a$5, donc :
$$\frac{48}{180} = \frac{48 \div 12}{180 \div 12} = \frac{4}{15}$$
À retenir
- $a$6 signifie qu'il existe $a$7 tel que $a$8.
- 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 $a$9 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 $b$0 à $b$1.