1
COURS
Arithmétique dans l’ensemble Z
Ce chapitre est consacré à l’étude de l’arithmétique dans l’ensemble des entiers relatifs Z. Nous
aborderons les notions fondamentales de divisibilité, la division euclidienne, les congruences,
ainsi que les nombres premiers. L’objectif est de maîtriser les outils essentiels que sont l’algo-
rithme d’Euclide, le théorème de Bézout et le théorème de Gauss pour résoudre des problèmes
arithmétiques et des équations diophantiennes.
1 Divisibilité dans Z
Soient a et b deux entiers relatifs.
Définition : On dit que a divise b, et on note a|b, s’il existe un entier relatif k tel que b = ak. On
dit aussi que b est un multiple de a ou que a est un diviseur de b.
Exemples : 7|21 car 21 = 7 × 3. −5|30 car 30 = −5 × (−6). Tout entier non nul divise 0.
Propriétés fondamentales :
• Transitivité : Si a|b et b|c, alors a|c.
• Combinaison linéaire : Si un entier d divise deux entiers a et b, alors pour tous entiers
relatifs u et v, d divise la combinaison linéaire au + bv.
• Si a|b et b|a, alors |a| = |b|, c’est-à-dire a = b ou a = −b.
2 Division Euclidienne
Théorème : Soit a un entier relatif et b un entier naturel non nul. Il existe un unique couple
d’entiers (q, r) tel que :
a = bq + r avec 0 ≤ r < b
q est appelé le quotient et r le reste de la division euclidienne de a par b.
Exemple : La division euclidienne de −50 par 7 s’écrit : −50 = 7 × (−8) + 6. Ici, le quotient
est q = −8 et le reste est r = 6 (on a bien 0 ≤ 6 < 7). Une erreur commune serait d’écrire
−50 = 7 × (−7) − 1, car le reste doit être positif.
3 Congruences
Définition : Soit n un entier naturel non nul. Deux entiers a et b sont dits congrus modulo n si
le reste de leur division euclidienne par n est le même. On note alors :
a≡b (mod n)
Cela est strictement équivalent à dire que n divise la différence a − b.
1
2 COURS 1. ARITHMÉTIQUE DANS L’ENSEMBLE Z
Exemple : 27 ≡ 11 (mod 8) car 27 − 11 = 16, et 8|16.
Propriétés (Compatibilité) : Soient a, b, c, d des entiers et n un entier naturel non nul. Si
a ≡ b (mod n) et c ≡ d (mod n), alors :
• Addition : a + c ≡ b + d (mod n)
• Multiplication : ac ≡ bd (mod n)
• Puissance : Pour tout entier naturel k ≥ 1, ak ≡ bk (mod n)
Ces propriétés sont au cœur de la résolution de nombreux problèmes d’arithmétique, notamment
pour trouver le reste de la division de très grands nombres.
1.4. NOMBRES PREMIERS ET DÉCOMPOSITION 3
4 Nombres premiers et décomposition
Définition : Un entier naturel p est dit premier s’il admet exactement deux diviseurs positifs
distincts : 1 et lui-même.
Liste des premiers nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19, 23, ... Il en existe une
infinité (Théorème d’Euclide). Le nombre 2 est le seul nombre premier pair.
Théorème fondamental de l’arithmétique : Tout entier naturel n ≥ 2 se décompose de
manière unique (à l’ordre près des facteurs) en un produit de nombres premiers.
n = pα1 1 × pα2 2 × · · · × pαk k
où les pi sont des nombres premiers distincts et les αi des entiers naturels non nuls.
Exemple : 588 = 22 × 31 × 72 .
5 PGCD et Théorème de Bézout
Définition (PGCD) : Le Plus Grand Commun Diviseur de deux entiers non nuls a et b, noté
PGCD(a, b) ou a ∧ b, est le plus grand entier positif qui divise à la fois a et b. On le détermine
efficacement grâce à l’algorithme d’Euclide (divisions successives).
Définition (Nombres premiers entre eux) : Deux entiers non nuls a et b sont dits premiers
entre eux (ou copremiers) si PGCD(a, b) = 1.
Théorème de Bézout : Soient a et b deux entiers non nuls. Il existe des entiers relatifs u et v
tels que au + bv = PGCD(a, b).
Identité de Bézout (cas particulier fondamental) : a et b sont premiers entre eux si et
seulement s’il existe des entiers relatifs u et v tels que au + bv = 1.
6 Théorème de Gauss et applications
Théorème de Gauss : Soient a, b, c trois entiers non nuls.
Si a divise le produit bc et que PGCD(a, b) = 1, alors a divise c.
Intuitivement, si a n’a aucun facteur premier en commun avec b, alors tous ses facteurs premiers
doivent se retrouver dans c.
Corollaire : Si un nombre premier p divise un produit ab, alors p divise a ou p divise b.
Application (Équations diophantiennes) : Une équation de la forme ax + by = c, où a, b, c
sont des entiers, admet des solutions entières (x, y) si et seulement si PGCD(a, b) divise c. Le
théorème de Bézout garantit l’existence de solutions, et le théorème de Gauss permet de trouver
l’ensemble de toutes les solutions.
