Arithmétique dans Z : Cours complet, PGCD, Bézout et Gauss

L'arithmétique dans Z est l'étude des propriétés de divisibilité, de congruence et de décomposition des entiers relatifs. C'est l'un des chapitres fondateurs des mathématiques : il est au cœur de la cryptographie moderne (RSA), des codes de vérification (ISBN, IBAN) et de nombreux résultats d'algèbre. Maîtriser l'arithmétique dans Z, c'est comprendre la structure profonde des nombres entiers - comment ils se divisent, comment ils se combinent, et pourquoi certains, les nombres premiers, sont irréductibles.

Ce cours couvre l'intégralité du programme de lycée (Terminale Maths Expertes) et de première année de classe préparatoire (MPSI/PCSI) : divisibilité, division euclidienne, PGCD et algorithme d'Euclide, théorème de Bézout, entiers premiers entre eux, théorème de Gauss, PPCM, nombres premiers, et congruences modulo $n$ .

Table des Matières

L’ensemble ℤ et la relation de divisibilité

Définition de l’ensemble ℤ

L'ensemble des entiers relatifs, noté $\mathbb{Z}$ , est l'ensemble :

\mathbb{Z} = \{\ldots, -3,\, -2,\, -1,\, 0,\, 1,\, 2,\, 3, \ldots\}

La lettre $\mathbb{Z}$ vient de l'allemand Zahlen, qui signifie simplement « nombres ». On a l'inclusion $\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}$ . Tout entier naturel est un entier relatif, mais l'inverse est faux : $-5 \in \mathbb{Z}$ mais $-5 \notin \mathbb{N}$ .

Définition de la divisibilité dans ℤ

Soient $a, b \in \mathbb{Z}$ avec $b \neq 0$ . On dit que $b$ divise $a$ , et on note $b \mid a$ , s'il existe un entier $k \in \mathbb{Z}$ tel que :

a = b \times k

On dit aussi que $a$ est un multiple de $b$ , ou que $b$ est un diviseur de $a$ .

Exemples : $3 \mid 12$ car $12 = 3 \times 4$ . De même $-3 \mid 12$ car $12 = (-3) \times (-4)$ . En revanche, $5 \nmid 13$ car il n'existe aucun entier $k$ tel que $13 = 5k$ .

Propriétés fondamentales de la divisibilité

Soient $a, b, c \in \mathbb{Z}$ . La relation de divisibilité vérifie :

Réflexivité : $a \mid a$ (car $a = a \times 1$ ).
Transitivité : Si $a \mid b$ et $b \mid c$ , alors $a \mid c$ .
Linéarité : Si $a \mid b$ et $a \mid c$ , alors pour tous $\alpha, \beta \in \mathbb{Z}$ :
$a \mid (\alpha b + \beta c)$
Majoration : Si $a \mid b$ et $b \neq 0$ , alors $|a| \leq |b|$ .
Antisymétrie : Si $a \mid b$ et $b \mid a$ , alors $|a| = |b|$ , c'est-à-dire $a = b$ ou $a = -b$ .

La propriété de linéarité est la plus utilisée en exercice : si $a$ divise deux entiers $b$ et $c$ , il divise toute combinaison linéaire entière de $b$ et $c$ . C'est le cœur de nombreuses démonstrations.

La division euclidienne dans ℤ

Énoncé du théorème

Théorème (Division euclidienne) : Soient $a \in \mathbb{Z}$ et $b \in \mathbb{N}^*$ . 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 < b

$q$ est appelé le quotient et $r$ le reste de la division euclidienne de $a$ par $b$ .

Explication intuitive

Diviser $a$ par $b$ , c'est « remplir » autant de fois que possible un paquet de taille $b$ avec les éléments de $a$ , et regarder ce qui reste. Le reste est toujours strictement inférieur à $b$ : c'est la condition clé qui assure l'unicité. Si $r = 0$ , alors $b \mid a$ .

Exemple détaillé

Calculons la division euclidienne de $a = -17$ par $b = 5$ :

-17 = 5 \times (-4) + 3 \quad \text{car} \quad 0 \leq 3 < 5

Attention : on ne peut pas écrire $-17 = 5 \times (-3) + (-2)$ , car le reste $-2$ est négatif ; ce n'est pas une division euclidienne valide.

PGCD et algorithme d’Euclide dans ℤ

Définition du PGCD

Soient $a, b \in \mathbb{Z}$ , non tous deux nuls. Le plus grand commun diviseur (PGCD) de $a$ et $b$ , noté $\operatorname{pgcd}(a,b)$ ou $a \wedge b$ , est le plus grand entier positif qui divise à la fois $a$ et $b$ .

Par convention, $\operatorname{pgcd}(0, 0) = 0$ .

Théorème : Algorithme d’Euclide

Théorème : Soient $a, b \in \mathbb{Z}$ avec $b \neq 0$ . Si $r$ est le reste de la division euclidienne de $a$ par $b$ , alors :

\operatorname{pgcd}(a, b) = \operatorname{pgcd}(b, r)

Comment appliquer l’algorithme d’Euclide (exemple pas à pas)

Calculons $\operatorname{pgcd}(252, 84)$ :

\begin{align*} 252 &= 84 \times 3 + 0 \end{align*}

Le reste est $0$ dès la première étape, donc $\operatorname{pgcd}(252, 84) = 84$ .

Calculons maintenant $\operatorname{pgcd}(600, 124)$ :

\begin{align*} 600 &= 124 \times 4 + 104 \\ 124 &= 104 \times 1 + 20 \\ 104 &= 20 \times 5 + 4 \\ 20 &= 4 \times 5 + 0 \end{align*}

Le dernier reste non nul est $4$ , donc $\operatorname{pgcd}(600, 124) = 4$ .

Explication intuitive de l’algorithme d’Euclide

L'algorithme repose sur une idée simple : tout diviseur commun de $a$ et $b$ divise également le reste $r = a - bq$ . Donc l'ensemble des diviseurs communs de $(a, b)$ est exactement le même que celui de $(b, r)$ . On remplace ainsi le problème par un problème équivalent mais plus petit, jusqu'à tomber sur un reste nul.

Théorème de Bézout et entiers premiers entre eux

Définition : entiers premiers entre eux

Deux entiers $a$ et $b$ sont dits premiers entre eux (ou copremiers) si $\operatorname{pgcd}(a, b) = 1$ .

Exemples : $\operatorname{pgcd}(8, 15) = 1$ , donc $8$ et $15$ sont premiers entre eux. En revanche, $\operatorname{pgcd}(6, 9) = 3 \neq 1$ .

Théorème de Bézout

Théorème de Bézout : Soient $a, b \in \mathbb{Z}$ , non tous deux nuls. Il existe des entiers $u, v \in \mathbb{Z}$ tels que :

au + bv = \operatorname{pgcd}(a, b)

En particulier :

\operatorname{pgcd}(a, b) = 1 \iff \exists\, u, v \in \mathbb{Z},\quad au + bv = 1

Preuve de la relation de Bézout via l’algorithme d’Euclide (remontée)

La démonstration consiste à remonter les étapes de l'algorithme d'Euclide pour exprimer le PGCD comme combinaison linéaire de $a$ et $b$ . Reprenons l'exemple $\operatorname{pgcd}(600, 124) = 4$ :

\begin{align*} 4 &= 104 - 20 \times 5 \\ &= 104 - (124 - 104 \times 1) \times 5 \\ &= 104 \times 6 - 124 \times 5 \\ &= (600 - 124 \times 4) \times 6 - 124 \times 5 \\ &= 600 \times 6 - 124 \times 29 \end{align*}

Donc $600 \times 6 + 124 \times (-29) = 4 = \operatorname{pgcd}(600, 124)$ . Un couple de Bézout est $(u, v) = (6, -29)$ .

Attention : ce couple n'est pas unique.

Corollaire important

Si $\operatorname{pgcd}(a, b) = d$ , $a' = a/d$ , $b' = b/d$ , alors $\operatorname{pgcd}(a', b') = 1$ . En divisant par le PGCD, on rend deux entiers premiers entre eux.

Théorème de Gauss

Énoncé

Théorème de Gauss : Soient $a, b, c \in \mathbb{Z}$ . Si $a \mid bc$ et $\operatorname{pgcd}(a, b) = 1$ , alors :

a \mid c

Explication intuitive

Si $a$ divise le produit $bc$ mais ne « partage aucun facteur » avec $b$ (puisque $\operatorname{pgcd}(a,b)=1$ ), alors tous les facteurs de $a$ doivent forcément se trouver dans $c$ . C'est l'image d'une « pression » qui ne peut s'exercer que sur $c$ .

Démonstration

Puisque $\operatorname{pgcd}(a, b) = 1$ , par Bézout il existe $u, v \in \mathbb{Z}$ tels que $au + bv = 1$ . En multipliant les deux membres par $c$ :

auc + bvc = c

Or $a \mid auc$ (trivial) et $a \mid bc$ (hypothèse), donc $a \mid bvc$ . Par linéarité, $a \mid (auc + bvc) = c$ .

Application classique : simplification dans une fraction

Supposons que $\dfrac{p}{q}$ est irréductible, c'est-à-dire $\operatorname{pgcd}(p, q) = 1$ . Si $q \mid np$ pour un certain entier $n$ , le théorème de Gauss assure que $q \mid n$ . C'est le fondement de la preuve que $\sqrt{2}$ est irrationnel.

PPCM dans ℤ

Définition

Soient $a, b \in \mathbb{Z}^*$ . Le plus petit commun multiple (PPCM) de $a$ et $b$ , noté $\text{ppcm}(a,b)$ ou $a \vee b$ , est le plus petit entier strictement positif divisible à la fois par $a$ et par $b$ .

Relation fondamentale PGCD-PPCM

Pour tous $a, b \in \mathbb{Z}^*$ :

|ab| = \operatorname{pgcd}(a,b) \times \text{ppcm}(a,b)

Cette formule est très pratique : pour calculer le PPCM, il suffit de calculer le PGCD (par Euclide), puis de diviser $|ab|$ par ce PGCD.

Exemple : $a = 12$ , $b = 18$ . $\operatorname{pgcd}(12, 18) = 6$ . Donc $\text{ppcm}(12, 18) = \dfrac{12 \times 18}{6} = 36$ .

Nombres premiers et décomposition en facteurs premiers

Définition d’un nombre premier

Un entier naturel $p \geq 2$ est dit premier s'il possède exactement deux diviseurs positifs : $1$ et lui-même.

Les premiers nombres premiers sont : $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \ldots$

Remarque : $1$ n'est pas un nombre premier (il n'a qu'un seul diviseur positif).

Infinité des nombres premiers (preuve d’Euclide)

Théorème : Il existe une infinité de nombres premiers.

Preuve (par l'absurde) : Supposons qu'il n'existe qu'un nombre fini de nombres premiers $p_1, p_2, \ldots, p_n$ . Considérons l'entier :

N = p_1 \times p_2 \times \cdots \times p_n + 1

$N \geq 2$ , donc $N$ admet un diviseur premier $q$ . Ce $q$ doit figurer dans la liste $\{p_1, \ldots, p_n\}$ . Mais alors $q$ divise $p_1 \cdots p_n$ , donc $q$ divise $N - p_1 \cdots p_n = 1$ : impossible. Contradiction.

Théorème fondamental de l’arithmétique

Tout entier $n \geq 2$ s'écrit de manière unique (à l'ordre des facteurs près) comme produit de facteurs premiers :

n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times \cdots \times p_k^{\alpha_k}

où $p_1 < p_2 < \cdots < p_k$ sont des nombres premiers et $\alpha_i \in \mathbb{N}^*$ .

Exemple : $360 = 2^3 \times 3^2 \times 5$ . Et $756 = 2^2 \times 3^3 \times 7$ . Donc :

\operatorname{pgcd}(360, 756) = 2^{\min(3,2)} \times 3^{\min(2,3)} = 2^2 \times 3^2 = 36

\text{ppcm}(360, 756) = 2^{\max(3,2)} \times 3^{\max(2,3)} \times 5 \times 7 = 2^3 \times 3^3 \times 5 \times 7 = 7560

Congruences modulo n dans ℤ

Définition

Soit $n \in \mathbb{N}^*$ , $n \geq 2$ . On dit que deux entiers $a$ et $b$ sont congrus modulo $n$ , et on note $a \equiv b \pmod{n}$ , si $n \mid (a - b)$ , c'est-à-dire s'il existe $k \in \mathbb{Z}$ tel que :

a - b = kn

De façon équivalente, $a \equiv b \pmod{n}$ si et seulement si $a$ et $b$ ont le même reste dans la division euclidienne par $n$ .

Propriétés des congruences

La congruence modulo $n$ est une relation d'équivalence (réflexive, symétrique, transitive). De plus, elle est compatible avec les opérations arithmétiques :

Si $a \equiv b \pmod{n}$ et $c \equiv d \pmod{n}$ , alors :

Addition : $a + c \equiv b + d \pmod{n}$
Multiplication : $ac \equiv bd \pmod{n}$
Puissance : $a^k \equiv b^k \pmod{n}$ pour tout $k \in \mathbb{N}$

Explication intuitive : l’horloge comme modèle

Les congruences fonctionnent comme une horloge. Sur une horloge à 12 heures, $14 \equiv 2 \pmod{12}$ : 14h et 2h correspondent à la même position de l'aiguille. De même, $25 \equiv 1 \pmod{12}$ . Les congruences permettent de « raisonner en cycles ».

Exemple d’application : reste d’une puissance

Calculons le reste de $3^{100}$ dans la division euclidienne par $7$ .

On cherche d'abord le cycle des puissances de $3$ modulo $7$ :

\begin{align*} 3^1 &\equiv 3 \pmod{7} \\ 3^2 &\equiv 2 \pmod{7} \\ 3^3 &\equiv 6 \pmod{7} \\ 3^4 &\equiv 4 \pmod{7} \\ 3^5 &\equiv 5 \pmod{7} \\ 3^6 &\equiv 1 \pmod{7} \end{align*}

Le cycle est de longueur $6$ . Or $100 = 6 \times 16 + 4$ , donc :

3^{100} = (3^6)^{16} \times 3^4 \equiv 1^{16} \times 4 \equiv 4 \pmod{7}

Le reste est $4$ .

Conclusion : ce qu’il faut retenir sur l’arithmétique dans ℤ

L'arithmétique dans Z repose sur quelques piliers solidement liés entre eux. La division euclidienne est le point de départ : elle permet de définir le PGCD et de le calculer efficacement via l'algorithme d'Euclide. Le théorème de Bézout donne une caractérisation algébrique des entiers premiers entre eux et permet de résoudre les équations diophantiennes. Le théorème de Gauss est l'outil clé pour les raisonnements de divisibilité lorsque deux entiers sont premiers entre eux. Enfin, les congruences modulo $n$ fournissent un cadre élégant et puissant pour calculer des restes, notamment dans les grandes puissances. Tous ces outils sont indispensables en prépa et constituent le socle de la théorie des nombres.

Pour approfondir :

Résumé de cours : L'arithmétique dans Z sur BibMath
Complément : Arithmétique modulaire (Wikipédia)