Prof: Cheikh Haythem

Chapitre 4
Arithmétique dans l’ensemble des entiers
relatifs

4.1 Divisibilité dans  : diviseurs, multiples d’un entier

4.1.1 Diviseurs, multiples d’un entier
Définition 4.1.1(Divisibilité, diviseur, multiple)
Soit a, b   2 . On dit que a divise b et on note a|b s’il existe k   tel que b  k. a.
Dans ce cas, on dit que a est un diviseur de b ou que b est un multiple de a.

Notation 4.1.2 Pour tout a  , on note a l’ensemble des multiples de a.

Exemple 4.1.3
- 21  3  7, donc 21 est un multiple de 3 et 3 est un diviseur de 21.
- 0 est un multiple de tout entier. Tout entier divise 0.
-1 divise tous les entiers.

Nous pouvons remarquer directement un certain nombre de propriétés

élémentaires qui décrivent simplement de la définition.
Propriétés 4.1.4 (Propriétés de la relation de divisibilité)
Soient a, b, c, d 
-a|a.
-Si a|b et b|c alors a|c.
-Si a|b et b|a, alors |a| |b|.
-Si d|a et d|b, alors d|au  bv pour tout u, v  2 .
-Si a|b et c|d, alors ac|bd. En particulier, si: a|b, alors: a k |b k pour tout k  .
-Si d  0, a|b  ad|bd.

Exercice 4.1.5 Soit a, b   2 et n    . Montrer que a  b|a n  b n .

Exercice4.1.6 Soit a, b   2 et n un entier naturel impair. Montrer que

a  b|a n  b n .

Exercice 4.1.7 Soit n    . Soit d un diviseur positif de n. Montrer pour tout a  1

a d  1|a n  1.
4.1.2 Relation de congruence
Définition 4.1.8 (Congruence) Soient a, b   2 et n  . On dit que a et b sont
congrus modulo n si n|b  a i.e. s’il existe k   tel que b  a  kn.
Cette relation se note a  bn. En particulier a  0n signifie que n|a.

1
Théorème 4.1.9 (Propriétés de la relation de congruence)
La relation de congruence est une relation d’équivalence;
-Réflexivité: a  an.
-Transitivité: Si a  bn et b  cn alors a  cn.
-Symétrie: Si a  bn, alors b  an.
 Soient a, b, c, d, n  , si a  bn et c  dn alors :
ac  bdn et a  c  b  dn.
On dit que la relation de congruence est compatible avec les opérations.

Exercice 4.1.10 Soit n  . Etablir les divisibilités suivantes:

(a) 6|5n 3  n (b) 5|2 2n1  3 2n1 (c) 9|4 n  1  6n
4.1.3 Division euclidienne
Théorème 4.1.11 (Théorème de la division euclidienne)
Soient a  et b    , 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.
Par ailleurs : q  E ba  et r  ab.

Théorème 4.1.12 Soient a, b   avec b  0, alors b|a ssi le reste dans la division
euclidienne de a par b est nul.

Exercice 4.1.13 Soit a et b deux entiers naturels avec b non nul.

Montrer que si r est le reste de la division euclidienne de a par b alors 2 r  1 est le
reste de la division euclidienne de 2 a  1 par 2 b  1.

4.2 Plus grand commun diviseur d’un couple d’entiers

4.2.1 Définition et propriétés
Définition 4.2.1 Soit a, b   2 . On appelle diviseur commun de a et b tout entier
qui divise à la fois a et b. On appelle multiple commun de a et b tout entier qui est à la
fois multiple de a et multiple de b.

Théorème et définition 4.2.2 (PGCD de deux entiers)

Si a et b sont deux entiers, alors il existe un unique entier naturel d qui vérifie les
deux conditions suivantes:
(i) d est un diviseur commun de a et b i.e. d|a et d|b ;
(ii) tout diviseur commun de a et b divise d i.e. d   , d  |a et d  |b  d  |d
L’entier d défini plus haut est noté a  b et appelé le plus grand commun diviseur de
a et b.

Proposition 4.2.3. Pour tous entiers a et b non nuls, a  b  0.

Pour tous entiers a et b, a  b  |a|  |b|.

Propriétés 4.2.4 Soit a et b deux entiers .

 Si b divise a alors a  b  |b|.
 a  b  b  a.

2
 Pour tout entier k, ka  kb  |k|a  b.
 a  b  c  a  b  c.
4.2.2 Algorithme d’Euclide
Théorème 4.2.5 (lemme d’Euclide). Soit a  bq  r la division euclidienne de a 
par b   . Alors a  b  b  r. Alors a  b  b  r.

L’algorithme suivant permet de déterminer le pgcd de deux entiers par une

succession de divisions euclidiennes.
Algorithme d’Euclide
On définit une suite r n  de la manière suivante :
1. On pose r 0  a et r 1  b.
2. Pour n  1, r n1 est le reste de la division euclidienne de r n1 par r n .
r n  est une suite strictement décroissante d’entiers naturels (à partir du rang 1) :
elle est donc nulle à partir d’un certain rang. Soit N l’indice du dernier terme non nul.
Le lemme précédent montre que r N  a  b.

Exemple 4.2.6 L’algorithme d’Euclide appliqué à 12642 et 2382 s’écrit

12642  5  2382  732
2382  3  732  186
732  3  186  174
186  1  174  12
174  14  12  6
12  2  6  0.
Le dernier reste non nul est 6 et donc 12642  2382  6.

Théorème 4.2.7 (Relations de Bézout pour deux entiers) Soient a, b  . Il existe

des entiers u, v  pour lesquels: a  b  au  bv. Une telle relation est appelée une
relation de Bézout de a et b.

Remarque 4.2.8 Les entiers u et v ne sont pas uniques.

Par exemple : 4  6  2, 2  4  1  6  1 et 2  4  2  6  1.

4.2.3 Algorithme d’Euclide étendu

L’algorithme d’Euclide étendu est une variante de l’algorithme d’Euclide qui permet,
à partir de deux entiers a et b, de calculer non seulement leur plus grand commun
diviseur (pgcd), mais aussi un couple de coefficients de Bézout, c’est-à-dire deux
entiers u et v tels que au  bv  a  b.
L’idée principale de l’algorithme est d’effectuer les mêmes étapes que pour
l’algorithme d’Euclide, mais en exprimant à chaque itération le reste comme une
combinaison linéaire de a et b. Puisque le dernier reste est le pgcd, celui-ci sera alors
exprimé comme une combinaison linéaire de a et b.
Déroulement de l’algorithme
On note r 0  a et r 1  b. On cherche u et v tels que r 0  r 1  ur 0  vr 1 .
r0  q1r1  r2 r2  u2r0  v2r1

3
r1  q2r2  r3 r3  u3r0  v3r1
...
r 2  q 1 r 1  r  r  ur0  vr1
De cette façon, a  b  r  , u  u  et v  v  .

Exemple 4.2.9
a  150 et b  54.
150  2  54  42
54  1  42  12
42  3  12  6
12  2  6  0
On a donc 150  54  6.
Réécrivons les divisions euclidiennes de l’algorithme d’Euclide standard sous une
autre forme :
42  150  2  54
12  54  1  42
6  42  3  12
On part ensuite du pgcd (c’est-à-dire 6) et on remonte les lignes de la manière
suivante :
6  42  3  12
 42  3  54  1  42
 4  42  3  54
 4  150  2  54  3  54
 4  150  11  54
Et voilà l’identité de Bézout.

Exercice 4.2.10 Soit a et b deux entiers non nuls de pgcd d. Notre but est de
déterminer tous les couples u, v   2 tels que au  bv  d.
(a) Justifier l’existence d’un couple de solution u 0 , v 0 .
(b) Exprimer à partir de u 0 , v 0  tous les couples solutions.

Exercice 4.2.11 Montrer que, pour n  , le pgcd de 2n  4 et 3n  3 divise 6.

4.3 Entiers premiers entre eux

Définition 4.3.1 (Entiers premiers entre eux)
Soient a et b deux entiers relatifs. On dit que a et b sont premiers entre eux si leurs
seuls diviseurs communs sont 1. Autremenr dit, a  b  1.

Proposition 4.3.2 Soient a et b deux entiers relatifs, et soit d  a  b. Si on pose

a  d. a  et b  d. b  , alors a  et b  sont premiers entre eux.

Proposition 4.3.3 (Forme irréductible d’un rationnel)

p
Soit r    . Alors il existe un unique couple p, q       tel que r  q et
p  q  1.

4
Remarque 4.3.4 La forme irréductible de r    est unique seulement si on impose
au dénominateur d’être  0.

Théorème 4.3.5 (théorème de Bézout).

Soient a et b deux entiers relatifs. a et b sont premiers entre eux si et seulement si il
existe deux entiers relatifs u et v tels que au  bv  1.

Remarqe 4.3.6 Contrairement au premier théorème de Bézout, on a bien ici une

équivalence.

Théorème 4.3.7 (théorème de Gauss).

Soient a, b et c trois entiers relatifs .Si a divise bc et si a est premier à b, alors a divise
c.

Proposition 4.3.8 Soient a 1 , . . . , a r    r et n  .

1. Si a 1 , . . . , a r sont tous premiers avec n, alors le produit a 1 . . . a r est également
premier avec n.
2. Si a 1 , . . . , a r sont premiers entre eux deux à deux et divisent n, alors le produit
a 1 . . . a r divise également n.

Exercice 4.3.9 Soient a    et b    premiers entre eux.

Montrer que a  b et ab sont premiers entre eux.

Exercice 4.3.10 Soit a et b deux entiers relatifs. Montrer

a|b  a 2 |b 2 .

Execice 4.3.11 Soit a, b et c trois entiers avec a et c premiers entre eux.

Montrer que a  bc  a  b.

Exercice 4.3.12 Montrer, que pour tout n  , les entiers n, n  1 et 2n  1 sont

premiers entre eux deux à deux, . Que dire des entiers n 2  n et 2n  1 ?

4.4 Plus petit commun multiple de deux entiers

Théorème et définition 4.4.1 (PPCM de deux entiers)
Pour tous entiers a et b il existe un unique entier m positif qui vérifie les deux
conditions suivantes.
-m est un multiple de a et b i.e. a|m et b|m
-tout multiple commun de a et b est un multiple de m i.e. m   ,
a|m  et b|m    m|m  .
L’entier m ainsi défini est le plus petit commun multiple de a et b et est noté a  b.

Proposition 4.4.2 Pour tous entiers a et b, a  b. a  b  |ab|.

Pour tous entiers a et b , a  b  |a|  |b|.

Propriétés 4.4.3 Soit a et b deux entiers .

Si a  0 ou b  0 alors a  b  0 (le seul multiple commun à a et b est 0).

5
Si b divise a alors a  b  |a|.
a  b  b  a.
Pour tout entier k, ka  kb  |k|a  b.

Exercice 4.4.4 Soit d, m     2 . Donner une condition nécessaire et suffisante

xyd
pour qu’il existe x, y   2 solution de xym
xy10
Exercice 4.4.5 Déterminer tous les couples x, y   2 solution de xy100

4.5 Nombres premiers

Définition 4.5.1 (Nombres premiers)
Un entier naturel p  2 est dit premier, si ses seuls diviseurs sont 1 et lui-même.
On note l’ensemble des nombres premiers.

Remarqes 4.5.2
-1 n’est pas considéré comme un nombre premier.
-A l’exception de 2, tous les nombres premiers sont impairs.
-Deux nombres premiers distincts sont premiers entre eux.

Théorème 4.5.3
Tout entier naturel différent de 1 admet au moins un diviseur premier.

Corollaire 4.5.4 L’ensemble des nombres premiers est infini.

Corollaire 4.5.5 Deux entiers sont premiers entre eux si et seulement si ils
n’admettent aucun diviseur premier commun.

Théorème 4.5.6 Soit n un entier naturel supérieur ou égal à 4. n est premier si et

seulement si n n’est divisible par aucun des nombres premiers inférieurs ou égaux à
n.

Exemple 4.5.7 est un nombre premier: en effet, 331  18, . . . Les nombres
premiers inférieurs ou égaux à 331 sont 2, 3, 5, 7, 11, 13 et 17.
331
2
 165, 5 et donc 331 n’est pas divisible par 2.
331
3
 110, 3. . . et donc 331 n’est pas divisible par 3.
331
5
 66, 2 et donc 331 n’est pas divisible par 5.
331
7
 47, 2. . . et donc 331 n’est pas divisible par 7.
331
11
 30, 09. . . et donc 331 n’est pas divisible par 11.
331
13
 25, 4. . . et donc 331 n’est pas divisible par 13.
331
17
 19, 47. . . et donc 331 n’est pas divisible par 17.
Finalement, 331 n’est divisible par aucun nombre premier inférieur ou égal à sa
racine et donc 331 est un nombre premier.

Proposition 4.5.8
Soit p un nombre premier et a  . Alors a et p sont premiers entre eux si et

6
seulement si p ne divise pas a.

Remarqe 4.5.9 En particulier, p est premier avec tous les entiers de 1, . . . , p  1.
Une autre conséquence est que deux nombres premiers distincts sont premiers
entre eux.
Attention ! Il est essentiel que p soit premier.
4 et 10 ne sont pas premiers entre eux mais 4 ne divise pas 10.

Proposition 4.5.10 (Lemme d’Euclide)

Soient p un nombre premier et a, b   2 .
Si p|ab, alors p|a ou p|b.

Remarqe 4.5.11 Cette proposition se généralise par récurrence au cas de plusieurs

entiers;
Si p est un nombre premier, et si a 1 , a 2 , . . . , a n est une famille d’entiers relatifs.
Alors p divise le produit a 1 a 2 . . . a n si et seulement si p divise l’un au moins des a k .

Théorème 4.5.12 (Théorème de Fermat)

Si p est un nombre premier, alors pour tout entier a ona a p  ap.
De plus, si a  p  1, alors a p1  1p.

Exercice 4.5.13 Soit p un nombre premier.

p
(a) Pour tout k  1, . . . , p  1, montrer que le coefficient binomial k
est un
multiple de p.
(b) En déduire que, pour tous entiers a et b, a  b p  a p  b p p.

Exercice 4.5.14 (nombres de Mersenne)

Soient a  1 et n  2. Montrer que si a n  1 est premier, alors a  2 et n et premier.

Exercice 4.5.15 Soient des entiers a  1 et n  1. On veut montrer que si a n  1 est

premier, alors n est une puissance de 2.
1) Montrer qu’il n’est pas possible que n soit un entier impair.
2)Montrer que l’entier n peut s’écrire sous la forme n  2 p 2k  1 avec p, k   2 .
3) Reprendre l’idée du 1) pour conclure que k  0.

Exercice 4.5.16 Montrer que p est irrationnel si p est premier.

4.6 Décomposition en facteurs premiers

Théorème 4.6.1 (décomposition en produit de facteurs premiers)
Tout entier n  2 s’´ecrit n  p 1 1 . p 1 2 . . . . . p mm où :
– m est un entier strictement positif.
– p 1 , p 2 , . . . , p m sont des nombres premiers distincts deux à deux.
– α 1 , α 2 , . . . , α m sont des entiers strictement positifs.
Une telle écriture de n est unique à l’ordre près des facteurs. On l’appelle
décomposition de n en produits de facteurs premiers.

7
Remarque 4.6.2 On peut étendre aux entiers n de  (sauf 1, 0, 1) le principe de la
décomposition en produits de facteurs premiers : il suffit d’écrire
n  ε. p 1 1 . p 1 2 . . . . . p mm , avec ε  1.
Notion de valuation p-adique
Si n est un entier naturel non nul et p un nombre premier, alors l’ensemble
k  /p k |n est non vide (contient 0) et majoré par n (on peut montrer par
récurrence que p n  n), cet ensemble admet donc un maximum .
Définition 4.6.3 Soit p  et n    , on appelle valuation p-adique de n, notée
v p n, le plus grand entier k tel que p k |n. La définition s’étend à , en posant
v p n  v p n si n  0 et v p 0   .

Remarque 4.6.4
– v p n  k  p k |n et p k1  n  q  , n  p k q avec p  q  1.
– v p n  1  p k |n.

Proposition 4.6.5 Pour tout entier n  2, la décomposition de n en produit de

facteurs premiers s’écrit : n   p vp n .
p

Remarque 4.6.6 Seul un nombre fini de valuations sont non nulles (les autres
donnent un facteur égal à 1).

Exemple 4.6.7 1200  2 4  3  5 2 donc ν 2 1200  4, ν 3 1200  1, ν 5 1200  2 et

ν p 1200  0 pour tout p  P\2, 3, 5.

Proposition 4.6.8 (Additivité des valuations p-adiques)

Pour tous p  et a, b   , v p ab  v p a  v p b.

Conséquence 4.6.9 Pour tous p  et a, b  , ν p n k   k. ν p n.
Caractérisation de la divisibilité, du pgcd et du ppcm par les
valuations p-adiques
Proposition 4.6.10
Soit a, b     2 .
(i) a|b  p  , ν p a  ν p b.
(ii) p  , ν p a  b  minν p a, ν p b.
(iii) p  , ν p a  b  maxν p a, ν p b.
(iv) a  b   p minν p a,ν p b .
p
(v) a  b   p maxν p a,ν p b .
p

4.7 PGCD d’un nombre fini d’entiers

Théorème et définition 4.7.1 Soit a 1 , . . . , a r    r , alors il existe un
unique entier naturel d qui vérifie les deux conditions suivantes:
(i) d est un diviseur commun des a i

8
(ii) tout diviseur commun des a i est un diviseur de d.
L’entier d défini plus haut est noté a 1 . . . a r et appelé le plus grand commun
diviseur de a 1 , . . . , a r .

Proposition 4.7.2 (Associativité du PGCD)

Soit a, b, c   3 . Alors a  b  c  a  b  c  a  b  c.

Remarque 4.7.3 Le calcul du PGCD d’une famille finie d’entiers peut être ramené à
des calculs de PGCD de deux entiers.

Exemple 4.7.4 10  12  18  10  12  18  2  18  2.

Proposition 4.7.5 (Propriétés du pgcd)

Soit a 1 , . . . , a r    r .
(i) Pour tout entier k, ka 1  . . . ka r   |k|a 1 . . . a r .
(ii) Pour tout diviseur commun d  0 des a i ,
a1
d
. . .  adr  a 1 ...a|d|
r
.

Théorème 4.7.6 (Relations de Bézout)

r
Soit a 1 , . . . , a r    r . Il existe u 1 , . . . , u r    r tel que  u i a i  a 1 . . . a r .
i1

4.8 Entiers premiers entre eux dans leur ensemble

Définitions 4.8.1 Soit a 1 , . . . , a r    r .
-On dit que a 1 , . . . , a r sont premiers entre eux dans leur ensemble si a 1 . . . a r  1.
-On dit que a 1 , . . . , a r sont premiers entre eux deux à deux si : a i  a j  1 pour tous
i, j  1, . . . , r distincts.

Remarque 4.8.2 Premiers entre eux deux à deux  Premiers entre eux dans leur
ensemble mais la réciproque est fausse.Par exemple, 6, 10, 15 sont premiers entre
eux dans leur ensemble sans être premiers entre eux deux à deux.

Théorème 4.8.3 (Théorème de Bézout)

Soit a 1 , . . . , a r    r . Alors a 1 . . . a r  1 si et seulement si il existe u 1 , . . . , u r    r
r
tel que  u i a i  1.
i1