Lycée · Terminale · Maths expertes (option Tle)
Arithmétique — divisibilité, PGCD et algorithme d'Euclide
Divisibilité dans $\mathbb{Z}$, division euclidienne, PGCD et PPCM : fondements de l'arithmétique au programme de l'option Maths expertes (Terminale)
À propos de cette page
Ce cours de maths expertes (option tle) en terminale sur « Arithmétique — divisibilité, PGCD et algorithme d'Euclide » suit le programme officiel de maths expertes (option tle) de terminale. Il présente les définitions, les propriétés et les méthodes essentielles, accompagnées d'exemples résolus pour bien comprendre. Au programme : Divisibilité dans $\mathbb{Z}$ : définitions et premières propriétés, Division euclidienne, PGCD — définition et propriétés, Algorithme d'Euclide. Chaque notion est expliquée pas à pas, puis mise en pratique grâce à des exercices interactifs, un QCM et une évaluation corrigée. Idéal pour réviser à son rythme, combler ses lacunes et progresser, en autonomie ou avec un professeur. Cours rédigé par un professeur particulier à Marseille pour aider les élèves de terminale à réussir en maths expertes (option tle).
1
Divisibilité dans $\mathbb{Z}$ : définitions et premières propriétés
Définition. Soient $a, b \in \mathbb{Z}$. On dit que $b$ divise $a$ (ou que $a$ est un multiple de $b$, ou encore que $b$ est un diviseur de $a$) s'il existe un entier $k \in \mathbb{Z}$ tel que $a = kb$. On note $b \mid a$.
On dit aussi que $a$ est divisible par $b$, ou que $b$ est un facteur de $a$.
Exemples.
- $3 \mid 12$ car $12 = 4 \times 3$.
- $7 \mid (-35)$ car $-35 = (-5) \times 7$.
- $5 \nmid 13$ car il n'existe pas d'entier $k$ tel que $13 = 5k$.
- Pour tout $a \in \mathbb{Z}$ : $1 \mid a$, $a \mid a$, $a \mid 0$ et $0 \mid a \Rightarrow a = 0$.
Propriétés fondamentales. Soient $a, b, c \in \mathbb{Z}$.
- Transitivité : si $a \mid b$ et $b \mid c$, alors $a \mid c$.
- Combinaisons linéaires : si $a \mid b$ et $a \mid c$, alors pour tous $u, v \in \mathbb{Z}$ : $a \mid (ub + vc)$.
- Produit : si $a \mid b$, alors $a \mid bc$.
- Si $a \mid b$ et $b \mid a$, alors $a = \pm b$.
Attention ! La divisibilité dans $\mathbb{Z}$ concerne les entiers relatifs : $2 \mid -6$ est vrai car $-6 = (-3) \times 2$. Ne pas confondre avec la division réelle.
Caption : Carte mentale des notions autour de la relation de divisibilité.
2
Division euclidienne
Théorème (Division euclidienne). Soient $a \in \mathbb{Z}$ et $b \in \mathbb{Z}^*$. Il existe un unique couple $(q, r) \in \mathbb{Z} \times \mathbb{N}$ tel que $$a = bq + r \quad \text{avec} \quad 0 \leq r \lt |b|.$$ $q$ est le quotient et $r$ le reste de la division euclidienne de $a$ par $b$.
Le reste $r$ appartient toujours à $\{0, 1, \ldots, |b|-1\}$. En particulier, $b \mid a \Leftrightarrow r = 0$.
Exemples.
- $a = 47$, $b = 7$ : $47 = 7 \times 6 + 5$, donc $q = 6$, $r = 5$.
- $a = -17$, $b = 5$ : $-17 = 5 \times (-4) + 3$, donc $q = -4$, $r = 3$ (attention, $r \geq 0$).
- $a = 36$, $b = 6$ : $36 = 6 \times 6 + 0$, donc $6 \mid 36$.
Cas $a \lt 0$. Quand $a$ est négatif, le reste $r$ doit rester dans $[0,|b|[$. Par exemple pour $a = -17$ et $b = 5$ : on pourrait écrire $-17 = 5 \times (-3) + (-2)$, mais $-2 \lt 0$ donc ce n'est pas la division euclidienne. On corrige en écrivant $-17 = 5 \times (-4) + 3$.
Attention ! L'unicité du couple $(q,r)$ n'est garantie que si $r \in [0, |b|[$. Sans cette contrainte, la décomposition n'est pas unique.
3
PGCD — définition et propriétés
Définition. Soient $a, b \in \mathbb{Z}$, non tous deux nuls. Le Plus Grand Commun Diviseur (PGCD) de $a$ et $b$ est le plus grand entier strictement positif qui divise à la fois $a$ et $b$. On le note $\text{PGCD}(a,b)$ ou $a \wedge b$.
Par convention : $\text{PGCD}(a, 0) = |a|$ pour tout $a \neq 0$.
Exemple par liste de diviseurs. Calculons $\text{PGCD}(24, 36)$.
Diviseurs de $24$ : $1, 2, 3, 4, 6, 8, 12, 24$.
Diviseurs de $36$ : $1, 2, 3, 4, 6, 9, 12, 18, 36$.
Diviseurs communs : $1, 2, 3, 4, 6, 12$. Donc $\text{PGCD}(24, 36) = 12$.
Diviseurs de $24$ : $1, 2, 3, 4, 6, 8, 12, 24$.
Diviseurs de $36$ : $1, 2, 3, 4, 6, 9, 12, 18, 36$.
Diviseurs communs : $1, 2, 3, 4, 6, 12$. Donc $\text{PGCD}(24, 36) = 12$.
Propriétés du PGCD.
- $\text{PGCD}(a,b) = \text{PGCD}(b,a)$ (commutativité).
- $\text{PGCD}(a,b) = \text{PGCD}(|a|,|b|)$ (on peut supposer $a,b \gt 0$).
- $\text{PGCD}(a,b) = \text{PGCD}(a,b-a)$ (et plus généralement $\text{PGCD}(a,b) = \text{PGCD}(a, b \mod a)$).
- Si $d = \text{PGCD}(a,b)$, alors $\frac{a}{d}$ et $\frac{b}{d}$ sont premiers entre eux.
4
Algorithme d'Euclide
Algorithme d'Euclide. Pour calculer $\text{PGCD}(a,b)$ avec $a \geq b \gt 0$, on effectue des divisions euclidiennes successives :
$$a = b q_1 + r_1 \quad (0 \leq r_1 \lt b)$$$$b = r_1 q_2 + r_2 \quad (0 \leq r_2 \lt r_1)$$$$r_1 = r_2 q_3 + r_3 \quad \ldots$$$$\vdots$$$$r_{n-2} = r_{n-1} q_n + 0$$Le dernier reste non nul $r_{n-1}$ est $\text{PGCD}(a,b)$.
$$a = b q_1 + r_1 \quad (0 \leq r_1 \lt b)$$$$b = r_1 q_2 + r_2 \quad (0 \leq r_2 \lt r_1)$$$$r_1 = r_2 q_3 + r_3 \quad \ldots$$$$\vdots$$$$r_{n-2} = r_{n-1} q_n + 0$$Le dernier reste non nul $r_{n-1}$ est $\text{PGCD}(a,b)$.
Principe clé. À chaque étape, $\text{PGCD}(a,b) = \text{PGCD}(b, r_1)$. Cette propriété se prouve : si $d \mid a$ et $d \mid b$, alors $d \mid (a - bq_1) = r_1$, donc tout diviseur commun à $a$ et $b$ divise aussi $r_1$ et $b$, et réciproquement.
Exemple. Calculons $\text{PGCD}(252, 105)$.
$252 = 105 \times 2 + 42$
$105 = 42 \times 2 + 21$
$42 = 21 \times 2 + 0$
Donc $\text{PGCD}(252, 105) = 21$.
$252 = 105 \times 2 + 42$
$105 = 42 \times 2 + 21$
$42 = 21 \times 2 + 0$
Donc $\text{PGCD}(252, 105) = 21$.
Autre exemple. Calculons $\text{PGCD}(1071, 462)$.
$1071 = 462 \times 2 + 147$
$462 = 147 \times 3 + 21$
$147 = 21 \times 7 + 0$
Donc $\text{PGCD}(1071, 462) = 21$.
$1071 = 462 \times 2 + 147$
$462 = 147 \times 3 + 21$
$147 = 21 \times 7 + 0$
Donc $\text{PGCD}(1071, 462) = 21$.
Caption : Étapes de l'algorithme d'Euclide pour calculer PGCD(252, 105).
Attention ! L'algorithme termine toujours car les restes forment une suite strictement décroissante d'entiers naturels : $b \gt r_1 \gt r_2 \gt \cdots \geq 0$. La suite atteint donc 0 en un nombre fini d'étapes.
5
Entiers premiers entre eux
Définition. Deux entiers $a$ et $b$ sont dits premiers entre eux (ou copremiers) si $\text{PGCD}(a,b) = 1$.
Cela ne signifie pas que $a$ ou $b$ est un nombre premier, mais qu'ils n'ont aucun diviseur commun autre que $1$ et $-1$.
Exemples.
- $\text{PGCD}(9, 14) = 1$ car $9 = 3^2$ et $14 = 2 \times 7$ : aucun facteur commun. Donc $9$ et $14$ sont premiers entre eux.
- $\text{PGCD}(8, 15) = 1$ : premiers entre eux.
- $\text{PGCD}(6, 9) = 3 \neq 1$ : non premiers entre eux.
Propriété utile. Si $d = \text{PGCD}(a,b)$, alors en posant $a = da'$ et $b = db'$, les entiers $a'$ et $b'$ sont premiers entre eux : $\text{PGCD}(a',b') = 1$.
Ainsi on peut toujours « réduire » une paire d'entiers pour les rendre premiers entre eux.
Ainsi on peut toujours « réduire » une paire d'entiers pour les rendre premiers entre eux.
À ne pas confondre. « $a$ et $b$ sont premiers entre eux » $\neq$ « $a$ est un nombre premier ». Par exemple, $4$ et $9$ sont premiers entre eux ($\text{PGCD}=1$) mais ni $4$ ni $9$ ne sont des nombres premiers.
6
PPCM et lien avec le PGCD
Définition. Soient $a, b \in \mathbb{Z}^*$. Le Plus Petit Commun Multiple (PPCM) de $a$ et $b$ est le plus petit entier strictement positif qui est multiple à la fois de $a$ et de $b$. On le note $\text{PPCM}(a,b)$ ou $a \vee b$.
Relation PGCD–PPCM. Pour tous entiers $a, b \in \mathbb{Z}^*$ : $$\text{PGCD}(a,b) \times \text{PPCM}(a,b) = |a \times b|.$$
Exemple. $a = 12$, $b = 18$.
$\text{PGCD}(12,18) = 6$ (algorithme d'Euclide : $18 = 12 \times 1 + 6$, $12 = 6 \times 2 + 0$).
$\text{PPCM}(12,18) = \dfrac{12 \times 18}{6} = \dfrac{216}{6} = 36$.
Vérification : $36$ est bien multiple de $12$ ($36 = 12 \times 3$) et de $18$ ($36 = 18 \times 2$).
$\text{PGCD}(12,18) = 6$ (algorithme d'Euclide : $18 = 12 \times 1 + 6$, $12 = 6 \times 2 + 0$).
$\text{PPCM}(12,18) = \dfrac{12 \times 18}{6} = \dfrac{216}{6} = 36$.
Vérification : $36$ est bien multiple de $12$ ($36 = 12 \times 3$) et de $18$ ($36 = 18 \times 2$).
| Propriété | Formule |
|---|---|
| Relation fondamentale | $\text{PGCD}(a,b) \times \text{PPCM}(a,b) = |ab|$ |
| Si premiers entre eux | $\text{PGCD}(a,b)=1 \Rightarrow \text{PPCM}(a,b)=|ab|$ |
| Cas $a \mid b$ | $\text{PGCD}(a,b)=|a|$ et $\text{PPCM}(a,b)=|b|$ |
Caption : Valeurs du PGCD pour quelques paires d'entiers classiques.
7
Applications et méthodes
Méthode : simplifier une fraction. Pour simplifier $\dfrac{a}{b}$, calculer $d = \text{PGCD}(a,b)$, puis $\dfrac{a}{b} = \dfrac{a/d}{b/d}$ est irréductible.
Exemple. $\dfrac{252}{105}$ : $\text{PGCD}(252,105) = 21$, donc $\dfrac{252}{105} = \dfrac{12}{5}$.
Méthode : résoudre un problème de partage. Pour partager $a$ objets en groupes identiques et $b$ autres objets de même façon : la taille de chaque groupe divise $\text{PGCD}(a,b)$. La taille maximale est $\text{PGCD}(a,b)$.
Exemple. On veut répartir $84$ élèves de math et $56$ élèves de français en groupes de même effectif, chaque groupe homogène. La taille maximale des groupes est $\text{PGCD}(84,56)$.
$84 = 56 \times 1 + 28$ ; $56 = 28 \times 2 + 0$. Donc $\text{PGCD}(84,56) = 28$.
On peut former des groupes de $28$ élèves : $3$ groupes math et $2$ groupes français.
$84 = 56 \times 1 + 28$ ; $56 = 28 \times 2 + 0$. Donc $\text{PGCD}(84,56) = 28$.
On peut former des groupes de $28$ élèves : $3$ groupes math et $2$ groupes français.
Méthode : trouver la période d'un phénomène. Deux événements périodiques de périodes $T_1$ et $T_2$ (entiers) se retrouvent simultanément toutes les $\text{PPCM}(T_1,T_2)$ unités de temps.
Exemple. Un signal A se répète toutes les $12$ secondes, un signal B toutes les $18$ secondes. Ils coïncident toutes les $\text{PPCM}(12,18) = 36$ secondes.
À retenir
- Divisibilité : $b \mid a \Leftrightarrow \exists k \in \mathbb{Z},\, a = kb$. Propriétés : transitivité, combinaisons linéaires.
- Division euclidienne : $a = bq + r$ avec $0 \leq r \lt |b|$, unique.
- PGCD : plus grand diviseur commun ; $\text{PGCD}(a,b) = \text{PGCD}(b, a \bmod b)$.
- Algorithme d'Euclide : divisions successives jusqu'au reste nul ; le dernier reste non nul est le PGCD.
- Premiers entre eux : $\text{PGCD}(a,b)=1$.
- PPCM : $\text{PGCD}(a,b) \times \text{PPCM}(a,b) = |ab|$.
- Applications : simplification de fractions, problèmes de partage, coïncidences périodiques.
Bloqué sur ce chapitre ?
Cours particuliers de maths expertes (option tle) à Marseille, en présentiel ou à distance — un prof qui s'adapte à ton rythme et reprend ce qui coince.
Prof de maths à Marseille · Cours particuliers au lycée · Aide aux devoirs