Maths expertes — Arithmétique
Arithmétique : divisibilité, PGCD, nombres premiers
Divisibilité dans ℤ, division euclidienne, PGCD, algorithme d'Euclide, nombres premiers, décomposition
Résumé synthétiqueFiche en 5 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
L'arithmétique est l'étude des nombres entiers et de leurs relations cachées. Tout part d'une question simple : « qui divise qui ? ». On dit que $a$ divise $b$ s'il existe un entier $k$ tel que $b = ka$. Quand la division ne tombe pas juste, la division euclidienne fournit un quotient et un reste : $a = bq + r$ avec $0 \leq r < b$. De là naissent deux objets majeurs : le PGCD (plus grand diviseur commun), que l'algorithme d'Euclide calcule en quelques divisions, et les nombres premiers, briques élémentaires à partir desquelles tout entier se reconstruit de façon unique (théorème fondamental de l'arithmétique). Ces idées, vieilles de deux mille ans, sont aujourd'hui au cœur de la cryptographie.
La divisibilité est la brique de base : elle dit si un entier « rentre » exactement dans un autre. Ses propriétés (combinaisons, transitivité) permettent de raisonner sans jamais effectuer de division.
- $a$ divise $b$ (noté $a \mid b$) s'il existe $k \in \mathbb{Z}$ tel que $b = ka$.
- Si $a \mid b$ et $a \mid c$, alors $a \mid (b + c)$ et $a \mid (b - c)$.
- Combinaison linéaire : si $a \mid b$ et $a \mid c$, alors $a \mid (\alpha b + \beta c)$ pour tous $\alpha, \beta \in \mathbb{Z}$.
- Transitivité : si $a \mid b$ et $b \mid c$, alors $a \mid c$.
- Si $a \mid b$ et $b \mid a$ (avec $a, b > 0$), alors $a = b$.
Exemple
Montrons que $7 \mid (14n + 21)$ pour tout entier $n$. On a $7 \mid 14n$ (car $14n = 7 \times 2n$) et $7 \mid 21$ (car $21 = 7 \times 3$). Par combinaison, $7 \mid (14n + 21)$.
Piège à éviter
« $a$ divise $b$ » s'écrit $a \mid b$ et signifie $b = ka$ : c'est $a$ le diviseur. Ne le confonds pas avec $\dfrac{a}{b}$ : l'ordre compte, $a \mid b$ n'est pas $b \mid a$.
Quand $a$ n'est pas divisible par $b$, la division euclidienne mesure « ce qui reste ». Elle fournit un couple unique quotient–reste, fondement de l'algorithme d'Euclide et des congruences.
- Pour $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$ : il existe un unique couple $(q\,;r)$ tel que $a = bq + r$ et $0 \leq r < b$.
- $q$ est le quotient, $r$ est le reste de la division de $a$ par $b$.
- $a$ est divisible par $b$ si et seulement si $r = 0$.
- Critères de divisibilité : par $2$ (dernier chiffre pair), par $5$ (dernier chiffre $0$ ou $5$), par $3$ (somme des chiffres divisible par $3$).
Exemple
Division de $157$ par $12$ : $157 = 12 \times 13 + 1$. Le quotient est $13$, le reste $1$. Comme $r = 1 \neq 0$, $157$ n'est pas divisible par $12$.
Piège à éviter
Le reste vérifie toujours $0 \leq r < b$ : il ne peut être ni négatif, ni $\geq b$. Pour $a$ négatif, attention : $-7 = 3 \times (-3) + 2$ (reste $2$), et non $-7 = 3 \times (-2) - 1$.
Le PGCD de deux entiers est le plus grand qui les divise tous deux. Le calculer en listant les diviseurs serait long ; l'algorithme d'Euclide y parvient en quelques divisions, en exploitant une idée géniale : le PGCD se conserve quand on remplace $a$ par le reste de $a$ par $b$.
- $\mathrm{pgcd}(a\,;b)$ est le plus grand diviseur commun de $a$ et $b$.
- Algorithme d'Euclide : $\mathrm{pgcd}(a\,;b) = \mathrm{pgcd}(b\,;r)$ où $r$ est le reste de $a$ par $b$ ; on itère jusqu'à $r = 0$.
- Le PGCD est le dernier reste non nul de l'algorithme.
- $a$ et $b$ sont premiers entre eux si $\mathrm{pgcd}(a\,;b) = 1$.
- Théorème de Bézout : $\mathrm{pgcd}(a\,;b) = 1 \Leftrightarrow$ il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$.
- Relation clé : $a \times b = \mathrm{pgcd}(a\,;b) \times \mathrm{ppcm}(a\,;b)$.
Exemple
Calculons $\mathrm{pgcd}(252\,;198)$ : $252 = 1 \times 198 + 54$, $\ 198 = 3 \times 54 + 36$, $\ 54 = 1 \times 36 + 18$, $\ 36 = 2 \times 18 + 0$. Le dernier reste non nul est $18$, donc $\mathrm{pgcd}(252\,;198) = 18$.
Piège à éviter
Le PGCD est le dernier reste non nul, pas le dernier reste (qui vaut toujours $0$). Dès qu'un reste tombe à $0$, on lit le résultat à la ligne précédente.
Les nombres premiers sont les atomes de l'arithmétique : indivisibles (sauf par $1$ et eux-mêmes), ils servent à construire tous les autres. Savoir tester la primalité et les reconnaître est essentiel.
- $p$ est premier si $p \geq 2$ et que ses seuls diviseurs positifs sont $1$ et $p$.
- Liste : $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, \dots$ ($2$ est le seul premier pair).
- Il existe une infinité de nombres premiers (théorème d'Euclide).
- Test : $n$ est premier s'il n'est divisible par aucun premier $p \leq \sqrt{n}$.
- Le crible d'Ératosthène liste tous les premiers jusqu'à un entier $N$ en rayant les multiples.
Exemple
Testons $97$. On a $\sqrt{97} \approx 9{,}8$, donc il suffit de tester $2, 3, 5, 7$. Aucun ne divise $97$ ($97$ impair, $9 + 7 = 16$ non divisible par $3$, ne finit pas par $0$ ou $5$, $97 = 7 \times 13 + 6$). Donc $97$ est premier.
Piège à éviter
$1$ n'est pas un nombre premier (il n'a qu'un seul diviseur). Et pour tester la primalité, inutile de dépasser $\sqrt{n}$ : au-delà, un diviseur aurait déjà été trouvé en dessous.
Le théorème fondamental de l'arithmétique garantit que tout entier $\geq 2$ s'écrit, de façon unique, comme produit de premiers. Cette « carte d'identité » d'un nombre donne directement ses PGCD et PPCM.
- Théorème : tout entier $n \geq 2$ s'écrit de façon unique $n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \dots \times p_k^{\alpha_k}$.
- On décompose en divisant successivement par les plus petits premiers.
- PGCD par les décompositions : on garde le minimum des exposants de chaque premier commun.
- PPCM par les décompositions : on garde le maximum des exposants de chaque premier.
Exemple
$360 = 2^3 \times 3^2 \times 5$ et $84 = 2^2 \times 3 \times 7$. Pour le PGCD, on garde les premiers communs au plus petit exposant : $2^2 \times 3 = 12$. Pour le PPCM, au plus grand exposant : $2^3 \times 3^2 \times 5 \times 7 = 2\,520$.
Piège à éviter
Pour le PGCD, on prend le minimum des exposants des premiers communs ; pour le PPCM, le maximum sur tous les premiers apparaissant. Inverser les deux est l'erreur la plus fréquente.
Quiz - Arithmétique : divisibilité, PGCD, nombres premiers
10 questions
S'entraîner
Notions clés — Maths expertes
Articles utiles
Questions fréquentes
Les points clés à retenir sur Arithmétique : divisibilité, PGCD, nombres premiers, extraits du quiz de révision.
Le reste de la division euclidienne de $157$ par $12$ est :
Réponse :
$1$
$157 = 12 \times 13 + 1$. Le quotient est $13$ et le reste $1$ (avec bien $0 \leq 1 < 12$).
Que vaut $\mathrm{pgcd}(48\,;36)$ ?
Réponse :
$12$
$48 = 1 \times 36 + 12$, puis $36 = 3 \times 12 + 0$. Le dernier reste non nul est $12$.
Le nombre $51$ est-il premier ?
Réponse :
Non, car $51 = 3 \times 17$
$5 + 1 = 6$ est divisible par $3$, donc $3 \mid 51$ : $51 = 3 \times 17$. Ayant un diviseur autre que $1$ et lui-même, $51$ n'est pas premier.
La décomposition en facteurs premiers de $180$ est :
Réponse :
$2^2 \times 3^2 \times 5$
$180 = 2 \times 90 = 2^2 \times 45 = 2^2 \times 9 \times 5 = 2^2 \times 3^2 \times 5$.