Christophe Bertault — Mathématiques en MPSI




ARITHMÉTIQUE DES ENTIERS RELATIFS


1 DIVISIBILITÉ ET DIVISION ENTIÈRES

1.1 RELATION DE DIVISIBILITÉ


Définition (Divisibilité, diviseur, multiple)
• Soient a, b ∈ Z. On dit que a divise b, ou que a est un diviseur de b, ou que b est divisible par a, ou que b est un
multiple de a, s’il existe k ∈ Z pour lequel : b = ak. Cette relation se note : a|b.

• Pour tout a ∈ Z, l’ensemble des multiples de a n’est autre que l’ensemble : aZ = ak k∈Z .
Quant à l’ensemble des diviseurs de a, il sera noté div(a) dans ce cours, mais il ne

s’agit pas d’une notation
universelle. Deux remarques en passant : max div(a) = |a| et div(a) = div |a| .



 Explication  Ayez toujours en tête que pour tous a, b ∈ N∗ — on exclut 0, attention : a|b =⇒ a ¶ b.

 
Exemple div(8) = ±1, ±2, ±4, ±8 et div(12) = ±1, ±2, ±3, ±4, ±6, ±12 .



Théorème (Propriétés de la relation de divisibilité) Soient a, b, c, d ∈ Z.
(i) La relation de divisibilité | est une relation d’ordre sur N MAIS elle est seulement réflexive et transitive sur Z car :

a|b et b|a ⇐⇒ |a| = |b| ⇐⇒ a=b ou a = −b.

(ii) Si : d|a et d|b, alors : d (au + bv) pour tous u, v ∈ Z.

(iii) Si : a|b et c|d, alors : ac|bd. En particulier, si : a|b, alors : a k |b k pour tout k ∈ N.


 Explication  Que peut-on dire de a et b quand on sait qu’ils ont les mêmes diviseurs, i.e. : div(a) = div(b) ?
Dans ce cas, en particulier : a|b et b|a, donc : |a| = |b| d’après (i).

Démonstration
(i) Par hypothèse : b = ak et a = bl pour certains k, l ∈ Z, donc : b = bkl.
— Si b = 0 : a = bl = 0 donc : |a| = |b|.
— Si b 6= 0 : kl = 1, donc soit : k = l = 1, soit : k = l = −1, i.e. soit : a = b, soit :
a = −b, i.e. : |a| = |b|.
(ii) Par hypothèse : a = d k et b = d l pour certains
 k, l ∈ Z, donc : au + bv = d(ku + vl) avec :
ku + vl ∈ Z pour tous u, v ∈ Z, donc enfin : d (au + bv).
(iii) Par hypothèse : b = ak et d = cl pour certains k, l ∈ Z, donc : bd = (ac)(kl) avec : kl ∈ Z,
et ainsi : ac|bd. „




1.2 RELATION DE CONGRUENCE MODULO UN ENTIER


 (Relation de congruence modulo un entier) Soient n ∈ N et a, b ∈ Z. On dit que a est congru à b modulo
Définition
n si : n(b − a), i.e. s’il existe un entier k ∈ Z pour lequel : a = b + kn. Cette relation se note : a ≡ b [n].




1
Christophe Bertault — Mathématiques en MPSI




 Explication  Les relations de congruence généralisent la relation de divisibilité : n|a ⇐⇒ a ≡ 0 [n].

Cette petite équivalence est fondamentale dans les deux sens. Grâce à elle, on peut passer du vocabulaire de la divisibilité à
celui des congruences et réciproquement.



Théorème (Propriétés de la relation de congruence modulo un entier) Soient a, a′ , b, b′ ∈ Z et m, n ∈ N.
(i) La relation ≡ [n] est une relation d’équivalence sur Z.
(ii) Somme : Si : a ≡ b [n] et a′ ≡ b′ [n], alors : a + a′ ≡ b + b′ [n].
(iii) Produit : Si : a ≡ b [n] et a′ ≡ b′ [n], alors : aa′ ≡ bb′ [n].
En particulier, si : a ≡ b [n], alors : a k ≡ b k [n] pour tout k ∈ N.
(iv) Multiplication/division par un entier non nul : Si m 6= 0 : a ≡ b [n] ⇐⇒ ma ≡ mb [mn].



Démonstration L’assertion (i) a été prouvée au chapitre « Relations binaires ».
(ii) Par hypothèse, n divise b− a et b′ − a′ , donc aussi (b+ b′ )−(a + a′ ) par somme, donc : a + a′ ≡ b+ b′ [n].
(iii) Remarque : bb′ − aa′ = b(b′ − a′ ) + a′ (b − a). Or par hypothèse, n divise b − a et b′ − a′ , donc aussi
b(b′ − a′ ) + a′ (b − a) = bb′ − aa′ , donc : aa′ ≡ bb′ [n].
 m6=0 
(iv) Enfin : a ≡ b [n] ⇐⇒ n(b − a) ⇐⇒ mnm(b − a) ⇐⇒ ma ≡ mb [mn]. „

Exemple 2345 + 5432 est divisible par 3.
Démonstration 2345 + 5432 ≡ (−1)345 + (−1)432 ≡ −1 + 1 ≡ 0 [3].

Exemple Pour tout n ∈ Z impair : n2 ≡ 1 [8].
Démonstration Soit n ∈ Z impair, disons : n = 2k + 1 pour un certain k ∈ Z.
Alors : n2 = 4k2 + 4k + 1 = 4k(k + 1) + 1. Or k ou k + 1 est pair car ces deux entiers sont consécutifs, donc
k(k+1) est pair aussi : k(k+1) ≡ 0 [2]. A fortiori : 4k(k+1) ≡ 0 [8], et enfin : n = 4k(k+1)+1 ≡ 1 [8].




1.3 INTRODUCTION AUX NOMBRES PREMIERS


Définition (Nombre premier, nombre composé) Soit p ∈ N. On dit que p est premier si : p 6= 1 et si les seuls
diviseurs positifs de p sont 1 et p. On dit que p est composé si : p 6= 1 et si p n’est pas premier.
L’ensemble des nombres premiers est parfois noté P.



 Explication  Il n’est pas inutile de connaître la liste des premiers nombres premiers : 2, 3, 5, 7, 11, 13, 17, 19,
23, 29, 31, 37. . . Nous étudierons plus loin un procédé mécanique — mais coûteux — pour les déterminer tous.

Le résultat suivant est un théorème d’EXISTENCE facile à démontrer. Nous aurons plus tard un théorème d’UNICITÉ, mais
nettement plus difficile à obtenir.


Théorème (Existence de la factorisation première) Tout entier naturel non nul est un produit de nombres premiers.



 Explication  Dans cet énoncé lapidaire, on considère 1 comme le produit de 0 nombre premier et tout nombre
premier comme le produit d’1 nombre premier — soi-même.

Démonstration Par récurrence forte.
• Initialisation : 1 n’est divisible par aucun nombre premier, c’est le produit de zéro d’entre eux.


2
Christophe Bertault — Mathématiques en MPSI



• Hérédité : Soit n ¾ 2. Faisons l’hypothèse que tout entier naturel non nul strictement inférieur à n est un
produit de nombres premiers. Qu’en est-il de n ? Deux cas possibles — soit n est premier, soit n est composé.
Si n est premier, c’est terminé, il est produit de nombres premiers. Et s’il est composé ? Il s’écrit dans ce cas :
n = a b où a et b sont deux diviseurs positifs de n autres que 1 et n. Par hypothèse de récurrence, a et b
sont des produits de nombres premiers, donc n aussi par produit. „



Théorème (Infinité de l’ensemble des nombres premiers) L’ensemble P des nombres premiers est infini.



Démonstration Raisonnons par l’absurde en supposant P fini et notons donc p1 , . . . , p r la liste COMPLÈTE des
nombres premiers. Posons ensuite : N = p1 . . . p r + 1. Cet entier N , au moins égal à 2, est un produit de
nombres premiers d’après le théorème précédent, donc divisible par pk pour un certain k ∈ ¹1, rº. En particulier,
pk divise N − p1 . . . p r = 1, i.e. : pk = 1 — contradiction. „

 Explication  (Crible d’Ératosthène) Le crible d’Ératosthène permet une détermination simple de tous les nombres
premiers inférieurs à un seuil donné et repose sur la remarque suivante. Si un entier n ∈ N∗ est composé et si nous notons p
le plus petit de ses diviseurs premiers, alors : n = pk pour un certain k ∈ N∗ , mais comme alors tout diviseur premier
p
de k est supérieur ou égal à p, en particulier k ¾ p, et donc : n = pk ¾ p2 , i.e. : p ¶ n. En résumé :
p
Tout entier COMPOSÉ n ∈ N∗ possède un diviseur premier inférieur ou égal à n.

Nous pouvons en déduire la liste de tous les nombres premiers inférieurs ou égaux à 100. On part d’une liste des entiers de
2 à 100, dont on va peu à peu rayer les entiers composés et dont ne resteron...