Divisibilité

Un entier $a$ est divisible par un entier $b$ (non nul) s’il existe un entier $k$ tel que $a = kb$ .

On note $b \mid a$ (« $b$ divise $a$ »).

Exemples : $3 \mid 12$ car $12 = 3 \times 4$ . En revanche, $5 \nmid 13$ .

Division euclidienne

Pour tout entier $a$ et tout entier $b > 0$ , il existe des entiers uniques $q$ (quotient) et $r$ (reste) tels que :

$a = bq + r \quad \text{avec } 0 \leq r < b$

Exemple : $17 = 3 \times 5 + 2$ → quotient $= 5$ , reste $= 2$ .

$b \mid a \iff r = 0$

Critères de divisibilité usuels :

Diviseur	Critère
$2$	Dernier chiffre pair
$3$	Somme des chiffres divisible par 3
$5$	Dernier chiffre $0$ ou $5$
$9$	Somme des chiffres divisible par 9
$10$	Dernier chiffre $0$

Un entier $n \geq 2$ est premier s’il n’admet que deux diviseurs : $1$ et $n$ .

Premiers exemples : $2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots$

$1$ n’est pas un nombre premier.

Tout entier $n \geq 2$ se décompose de manière unique en produit de facteurs premiers.

Exemple : $360 = 2^3 \times 3^2 \times 5$

Méthode : Diviser successivement par les plus petits nombres premiers.

$360 \div 2 = 180 \div 2 = 90 \div 2 = 45 \div 3 = 15 \div 3 = 5$

Le PGCD (plus grand commun diviseur) de $a$ et $b$ : le plus grand entier qui divise à la fois $a$ et $b$ .
Le PPCM (plus petit commun multiple) : le plus petit entier $> 0$ multiple de $a$ et de $b$ .

Depuis la décomposition : PGCD = produit des facteurs communs au minimum, PPCM au maximum.

Exemple : $a = 12 = 2^2 \times 3$ , $b = 18 = 2 \times 3^2$

$\text{PGCD}(12, 18) = 2^1 \times 3^1 = 6 \qquad \text{PPCM}(12, 18) = 2^2 \times 3^2 = 36$

Propriété : $\text{PGCD}(a,b) \times \text{PPCM}(a,b) = a \times b$