Arithmétique : PGCD et nombres premiers

Multiples et diviseurs

Pour deux entiers $a$ et $b$ (avec $b \neq 0$) :

$a$ est multiple de $b$ si $a = b \times k$ avec $k$ entier. On dit aussi que $b$ divise $a$.

Exemples

• $35$ est multiple de $5$ et de $7$ (car $35 = 5 \times 7$).
• $5$ et $7$ sont des diviseurs de $35$.

Critères de divisibilité

Nombres premiers

Un entier $\geq 2$ est premier s'il a exactement deux diviseurs : $1$ et lui-même.

Premiers nombres premiers : $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, \ldots$

$1$ n'est pas premier ; $2$ est le seul nombre pair premier.

Décomposition en facteurs premiers

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

Méthode

On divise par les premiers successifs ($2, 3, 5, 7\ldots$) jusqu'à obtenir $1$.

Exemple

$60 = 2 \times 30 = 2 \times 2 \times 15 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3 \times 5$

PGCD — plus grand commun diviseur

Le PGCD de deux entiers $a$ et $b$ est le plus grand des diviseurs communs à $a$ et $b$.

Méthode 1 — par décomposition

On décompose $a$ et $b$, puis on prend les facteurs communs avec leur plus petit exposant.

Exemple

$48 = 2^4 \times 3 \qquad 60 = 2^2 \times 3 \times 5$

$\text{PGCD}(48, 60) = 2^2 \times 3 = 12$

Méthode 2 — algorithme d'Euclide

$\text{PGCD}(a, b) = \text{PGCD}(b, r)$, où $r$ est le reste de la division de $a$ par $b$.

On répète jusqu'à obtenir un reste de $0$ : le dernier reste non nul est le PGCD.

Exemple

PGCD$(48, 60)$ :

• $60 = 48 \times 1 + 12$
• $48 = 12 \times 4 + 0$

⇒ PGCD $= 12$.

Fractions irréductibles

Une fraction $\dfrac{a}{b}$ est irréductible si $\text{PGCD}(a, b) = 1$.

Méthode. Pour rendre $\dfrac{a}{b}$ irréductible : on divise numérateur et dénominateur par PGCD$(a, b)$.

Exemple

$\frac{48}{60} = \frac{48 \div 12}{60 \div 12} = \frac{4}{5}$

À retenir

• Premier : exactement $2$ diviseurs ($1$ et lui-même).
• Tout entier $\geq 2$ se décompose uniquement en facteurs premiers.
• PGCD : par décomposition (facteurs communs) ou Euclide (restes successifs).
• Fraction irréductible ⇔ PGCD = $1$.