Préparation à l’agrégation interne de mathématiques
Arithmétique dans Z - Résumé de résultats de base
Pour référence : par exemple les livres [Mon06] et [WAC+ 02] pour plus de détails et de démons-
trations.
Sur ce thème, le travail sur un manuel de Terminale S (programme de l’enseignement de spécialité)
peut s’avérer très profitable également.
1 Divisibilité dans Z, congruences
Proposition 1.1.
1. Un sous-ensemble non-vide de N possède un plus petit élément.
2. Un sous-ensemble non-vide et minoré de Z possède un plus petit élément.
3. Quels que soient l’entier naturel b non nul et l’entier naturel a, il existe un entier naturel n tel
que a < nb. (N est archimédien).
Une liste de définitions/vocabulaires :
1. Un entier b divise un entier a (on note b|a) s’il existe un nombre entier k tel que a = b × k.
2. L’ensemble Da des diviseurs positifs d’un entier a est non vide (et fini si a est non nul).
3. L’entier a est premier si Da contient exactement deux éléments (qui sont alors 1 et |a|).
4. L’ensemble des multiples de a est aZ.
5. La notion de diviseur commun, de multiple commun à deux ( ou plus) nombres est naturelle.
6. Deux entiers a et b (ou plus. . . ) sont premiers entre eux si Da ∩ Db = {1}.
Propriété 1.1. Si c divise a et b, alors c divise toutes les combinaisons linéaires αa + βb avec α et
β entiers relatifs.
Propriété 1.2 (Sur l’existence des nombres premiers).
1. Tout nombre entier naturel n > 2 admet pour diviseur un nombre premier.
2. Tout nombre entier naturel n > 2 non premier admet un diviseur premier p vérifiant p2 6 n.
3. L’ensemble des nombres premiers est infini.
Théorème 1 (Division euclidienne). Soient a et b deux entiers avec b 6= 0.
Il existe un unique couple (q; r) (quotient ; reste) d’entiers vérifiant :
a = bq + r et 0 6 r < |b|.
Définition 1.1. Deux entiers relatifs a et b sont dits congrus modulo l’entier n si n divise b − a.
On note a ≡ b (mod n).
Remarque 1.1. Il est équivalent de dire que a et b ont même reste dans la division euclidienne par
n (si n 6= 0).
Propriété 1.3. La congruence est compatible avec les opérations usuelles (+ ; − ; × ; exponentia-
tion).
La congruence modulo n est une relationd’équivalence sur Z constituée de n classes (si n > 0).
L’ensemble quotient est (l’anneau) Z/nZ = 0; 1; . . . ; n − 1 .
1
2 Décomposition, P GCD, P P CM, Euclide, Bézout, Gauss
Théorème 2 (Décomposition en produit de facteurs premiers). Tout entier naturel n > 2
peut s’écrire de façon unique comme un produit :
i=m
Y
n= pαi i = pα1 1 pα2 2 . . . pαmm
i=1
où p1 , p2 , . . . , pm sont des nombres premiers vérifiant 2 6 p1 < p2 < . . . < pm
et α1 , α2 , . . . , αm sont des nombres entiers naturels non nuls.
Les deux définitions suivantes ne sont pas les plus habituelles mais ont l’avantage de ne pas
nécessiter d’hypothèses de non-nullité sur a et b.
Propriété et définition 2.1 (Plus Grand Commun Diviseur). Soient a et b deux entiers
relatifs. Il existe un unique entier naturel δ = P GCD(a; b) = P GCD(b; a) vérifiant :
• δ est un diviseur commun à a et b ;
• tout autre diviseur commun à a et b divise δ.
Si a et b sont non nuls, le nombre P GCD(a; b) est le dernier reste non nul obtenu en appliquant
l’algorithme d’Euclide aux entiers a et b.
Propriété et définition 2.2 (Plus Petit Commun Multiple). Soient a et b deux entiers
relatifs. Il existe un unique entier naturel µ = P P CM (a; b) = P P CM (b; a) vérifiant :
• µ est un multiple commun à a et b ;
• tout autre multiple commun à a et b est un multiple de µ.
Remarque 2.1. Le nombre µ = P P CM (a; b) vérifie aZ ∩ bZ = µZ.
Théorème 3 (Bézout). Soient a et b deux entiers relatifs.
1. il existe des entiers relatifs u et v tels que au + bv = P GCD(a; b).
2. (Corollaire) Les entiers a et b sont premiers entre eux si et seulement s’il existe des entiers
relatifs u et v tels que au + bv = 1.
Propriété 2.1. Soient a, b, c, d et k des entiers relatifs.
1. Si a|c et b|d, alors P GCD(a; b)|P GCD(c; d) et P P CM (a; b)|P P CM (c; d).
2. P GCD(ka; kb) = |k| × P GCD(a; b) et P P CM (ka; kb) = |k| × P P CM (a; b)
3. P GCD(a; b) × P P CM (a; b) = |ab|
Théorème 4 (Gauss). Soient a, b et c trois entiers relatifs.
a | bc
1. ⇐⇒ a | b
P GCD(a; c) = 1
2. Plus généralement : si P GCD(a; c) = 1 alors P GCD(a; bc) = P GCD(a; b).
3. (Corollaire) Un nombre premier p divise ab si et seulement si p divise a ou p divise b.
Références
[Mon06] Jean-Marie Monier. Algèbre MPSI, Cours, méthodes et exercices corrigés, 4eédition.
J’intègre. Dunod, Paris, 2006.
[WAC+ 02] André Warusfel, Paul Attali, Michel Collet, Christian Gautier, and Serge Nicolas.
Arithmétique. Mathématiques, Cours et exercices TS. Vuibert, Paris, 2002.
