MPSI — CPGE

Arithmétique dans Z
2023-2024

Ce petit résumé est réalisé suivant le programme marocain de la filière MPSI et présente quelques résultats
fondamentaux d’arithmétique, agrémentés de petits exercices d’application. Les détails seront donnés en
classe suite à la demande des élèves. Toute suggestion ou complément est laissé pour la discussion en
classe.

1. Notion de divisibilité dans Z :

Définition 1.: Si a et b sont deux entiers tel que a est non nul, on dit que a divise b, ou que b est divisible
par a, s’il existe un entier q tel que b = aq. On dit encore que a est un diviseur de b, ou que b est un
multiple de a. On note, dans ce cas, a|b, et on note D(b) l’ensemble des diviseurs positifs de b et M(a)
l’ensemble des multiples positifs de a.

Proposition 1.: Voici quelques propriétés :

— Tout entier a ∈ Z∗ divise 0 et est divisible par 1 et a,
— Si a|b et b|c alors a|c,
— Soit m un entier non nul, a|b est équivalent à ma|mb,
— Si a|b et a|c, alors a|bx + cy pour tous entiers x, y. En particulier, a|b − c et a|b + c.

Exercice 1.: Soient x, y des entiers. Montrer que 3x + 2y est divisible par 7 si et seulement si 4x + 5y l’est
aussi.

Définition 2.: (Relation d’association) On dit que deux entiers a et b sont associés si b = ±a, ou encore si a|b
et b|a.

Exercice 2.: 1) Montrer que la relation d’association des entiers est une relation d’équivalence et donner
la classe d’un entier n.
2) Soit (k, k′ ) ∈ Z2 . Montrer que :

kk′ = 1 ⇔ k = k′ = 1 ou k = k′ = −1

2. Théorème de la division euclidienne :

Théorème 1.: (de la division euclidienne) Soit b un entier strictement positif. Tout entier a s’écrit, de manière
unique, sous la forme a = bq + r, où q et r sont des entiers, avec 0 ≤ r < b. On appelle q le quotient et
r le reste de la division euclidienne de a par b.

Remarque 1.: .
— sgn(q) = sgn(a)
— Si b < 0, pour effectuer la division euclidienne de a par b, on effectue la division euclidienne de a par
|b| :
∃!(q ′ , r ′ ) ∈ Z × J0, |b| − 1K /a = q ′ |b| + r ′

puis on prend (q, r) = (sgn(b)q ′ , r ′ ).

Remarque 2.: Le théorème précédent est très important puisqu’il permet de procéder par un raisonnement
par disjonction des cas (où le nombre des cas est fini) en considérant le reste r de la division euclidienne
de a par un certain n ∈ N∗ .
Page 1/7
 MPSI Arithmétique dans Z

Exercice 3.: Soit a un entier quelconque. Déterminer le reste de la division euclidienne de a2 par 4.

Exercice 4.: Montrer que n3 − n est divisible à la fois par 2 et 3.

3. Notion de plus grand commun diviseur :

Définition 3.: (Plus grand commun diviseur) Un entier divisant à la fois l’entier a et l’entier b (non tous les
deux nuls), est appelé diviseur commun de a et b. Le plus grand nombre strictement positif parmi ces
diviseurs communs est appelé le plus grand commun diviseur de a et b, on le note pgcd(a, b) ou a ∧ b.
On dit que a et b sont premiers entre eux si pgcd(a, b) = 1.

Exemple 1.: On a :

D(42) = {1, 2, 3, 6, 7, 14, 21, 42}

D(15) = {1, 3, 5, 15}

donc pgcd(42, 15) = 3.

Remarque 3.: .
— Attention le pgcd est défini pour (a, b) ∈ Z3 ∖ (0, 0), et on a : pgcd(a, b) > 0.
— pgcd(a, b) = |a| ⇔ a|b.

Proposition 2.: On a les propriétés suivantes :

— Pour tout entier c, pgcd(a, b) = pgcd(a, b + ac) = pgcd(a + bc, b),
— Si r est le reste de la division euclidienne de a par b alors pgcd(a, b) = pgcd(b, r).
21n + 4
Exercice 5.: Montrer que pour tout entier naturel n, la fraction est irréductible.
14n + 3
Théorème 2.: (Algorithme d’Euclide) La proposition précédente fournit un algorithme pour calculer le PGCD
de deux entiers a et b.
Supposons a > b > 0. Soit r1 le reste dans la division euclidienne de a par b.
Si r1 = 0, alors pgcd(a, b) = b, sinon, soit r2 le reste dans la division euclidienne de b par r1 .
Si r2 = 0, alors pgcd(a, b) = pgcd(b, r1 ) = r1 , sinon, soit r3 le reste dans la division euclidienne de r1
par r2 etc...
Le processus s’arrête nécessairement car les restes forment une suite d’entiers décroissante et minorée.
Le dernier reste non nul rn est égal au PGCD de a et b. En effet, la proposition précédente montre que
pgcd(a, b) = pgcd(b, r1 ) = pgcd(r1 , r2 ) = ... = pgcd(rn−1 , rn ) = rn .

L’algorithme d’Euclide est un résultat très important puisqu’il a deux conséquences particulièrement importantes :

Corollaire 1.: Si d = pgcd(a, b) alors il existe deux entiers u et v tels que :

au + bv = d.

Remarque 4.: .
— La réciproque est fausse (il suffit de prendre a = b = 2 et u = v = 1).
— Les entiers u et v s’appellent les coefficients de Bézout. Le couple (u, v) des coefficients de Bézout
n’est pas unique. Par exemple :

1 = 3 × 1 + 2 × (−1)
= 3 × (−1) + 2 × 2
= 3 × 3 + 2 × (−4)

— Si a et b sont de signe quelconque, on applique l’algorithme d’Euclide à |a| et |b| et on aura :

∃(u′ , v ′ ) ∈ Z2 / d = |a|u′ + |b|v ′

puis on prend u = sgn(a)u′ et v = sgn(b)v ′ .

Page 2/7
 MPSI Arithmétique dans Z

Corollaire 2.: (Théorème de Bézout) a et b sont premiers entre eux si et seulement si il existe deux entiers
u et v tels que :
au + bv = 1

Exemple 2.: — Déterminons le PGCD de 75 et 55 en utilisant l’algorithme d’Euclide :

75 = 55 × 1 + 20
55 = 20 × 2 + 15
20 = 15 × 1 + 5
15 = 5×3+0

donc pgcd(75, 55) = 5.

— Déterminons, maintenant, des coefficients de Bézout :

5 = 20 − 15 × 1 = 20 − (55 − 20 × 2) × 1 = 75 − 55 − (55 − (75 − 55) × 2) × 1 = 75 × 3 + 55 × (−4)

donc u = 3 et v = −4.

Exemple 3.: — Déterminons le PGCD de 156 et 39 en utilisant l’algorithme d’Euclide :

156 = 39 × 4 + 0

donc pgcd(156, 39) = 39 et des coefficients de Bézout sont : u = 1 et v = −3.

Exemple 4.: — Déterminons le PGCD de 169 et 38 en utilisant l’algorithme d’Euclide :

169 = 38 × 4 + 17
38 = 17 × 2 + 4
17 = 4×4+1
4 = 1×4+0

donc pgcd(169, 38) = 1.

— Déterminons, maintenant, des coefficients de Bézout :

1 = 17 − 4 × 4 = 17 − (38 − 17 × 2) × 4 = 169 − 38 × 4 − (38 − (169 − 38 × 4) × 2) × 4 = 169 × 9 + 38 × (−40)

donc u = 9 et v = −40.

Corollaire 3.: .
— D(a) ∩ D(b) = D(a ∧ b).
— Si d|a et d|b alors pgcd(a, b) = |d| pgcd(a/d, b/d).

Exercice 6.: Soient a et b deux entiers non nuls. Montrer que :



 a = da′

b = db′


′ ′ ∗ 2
∃!(a , b ) ∈ (Z ) /


 a′ ∧ b′ = 1

d=a∧b


Définition 4.: (PGCD de plusieurs entiers) Soit (ak )1≤k≤n une famille d’entiers non tous nuls.
— On définit le PGCD des ak comme étant le plus grand entier strictement positif parmi leurs diviseurs
communs. On le note pgcd(a1 , · · · , an ) ou a1 ∧ · · · ∧ an .
— On dit que les ak sont premiers entre eux si : pgcd(a1 , · · · , an ) = 1.

Exemple 5.: On a :
Page 3/7
 MPSI Arithmétique dans Z

— pgcd(64, 32, 8, 36, 48, 128) = 4

— pgcd(8, 24, 6, 15) = 1

Remarque 5.: (Attention !) Il y a une différence entre ”premiers entre eux” (ou ”premiers entre eux dans
leur ensemble”) et ”premiers entre eux deux à deux”. Par exemple, 2, 6, 9 sont premiers entre eux mais
ils ne sont pas premiers entre eux deux à deux.

Les propriétés du PGCD de deux entiers se généralisent comme suit :

Proposition 3.: .
\n
— D(ak ) = D (pgcd(a1 , · · · , an )).
k=1
— Si au moins deux entiers parmi les ak sont premiers entre eux alors : pgcd(a1 , · · · , an ) = 1.

Théorème 3.: (Théorème de Bézout) .

— Si d = pgcd(a1 , · · · , an ) alors il existe des entiers u1 , · · · , un tels que :

u1 a1 + · · · + un an = d

— Les ak sont premiers entre eux si et seulement si il existe des entiers u1 , · · · , un tels que :

u1 a1 + · · · + un an = 1

Exercice 7.: Soit n ∈ N∗ .

1) Soient a, b1 , · · · , bn des entiers non nuls. Montrer que :
n
Y
a ∧ b1 = · · · = a ∧ bn = 1 ⇔ a ∧ bk = 1
k=1

2) Soit (a, b) ∈ (Z∗ )2 . Montrer que :

a ∧ b = 1 ⇔ an ∧ bn = 1
n
Y
3) Soient a1 , · · · , an des entiers premiers entre eux deux à deux. Pour k ∈ J1, nK, on pose : bk = ai .
i=1,i̸=k
Montrer que les bk sont premiers entre eux.

4. Notion de plus petit commun multiple :

Définition 5.: (Plus petit commun multiple) Un entier à la fois divisible par a et par b (a, b ̸= 0) est appelé
un multiple commun de a et b. Le plus petit nombre strictement positif parmi ces multiples communs est
appelé le plus petit commun multiple de a et b et noté ppcm(a, b) ou a ∨ b.

Remarque 6.: Si b = 0, on note ppcm(a, 0) = 0.

Exemple 6.: On a :

M(18) = {0, 18, 36, 54, 72, 90, · · · }

M(15) = {0, 15, 30, 45, 60, 75, 90, · · · }

donc ppcm(18, 15) = 90.

Définition 6.: (PPCM de plusieurs entiers) On définit le PPCM de plusieurs entiers a1 , · · · , an (̸= 0) comme
étant l’entier m vérifiant :
n
\
m = min M (a) ∖ {0}
k=1

On le note ppcm(a1 , · · · , an ) ou a1 ∨ · · · ∨ an .
Page 4/7
 MPSI Arithmétique dans Z

Exemple 7.: On a :
— ppcm(64, 32, 8, 36, 48, 128) = 384
— ppcm(8, 24, 6, 15) = 120

5. Quelques résultats fondamentaux :

Théorème 4.: (Lemme d’Euclide) Soient a, b et c trois entiers tels que pgcd(a, b) = 1. Alors on a :

a|c et b|c =⇒ ab|c.

Théorème 5.: (Lemme de Gauss) Soient a, b et c trois entiers tels que pgcd(a, b) = 1. Alors on a :

a|bc =⇒ a|c.

Proposition 4.: Soient a et b deux entiers. Alors on a :

— M(a) ∩ M(b) = M(ppcm(a, b)),
— |ab| = pgcd(a, b) × ppcm(a, b),
— pgcd(a, b) = 1 ⇔ ppcm(a, b) = |ab|.

Exercice 8.: (Équation diophantienne) Soit (a, b, c) ∈ Z3 tel que (a, b) ̸= (0, 0). Considérons l’équation d’in-
connue (x, y) :

ax + by = c (1)

Posons d = pgcd(a, b).

(a) Que dire si d ne divise pas c ? Dans le cas contraire, montrer que l’équation (1) est équivalente à
une équation du type :

a′ x + b′ y = c′ (2)

avec pgcd(a′ , b′ ) = 1.
(b) Étant donné une solution particulière (x0 , y0 ) de l’équation (2), résoudre l’équation (1).
(c) Appliquer lorsque a = 189, b = 255 et c = 27.

Exercice 9.: Soit (a, b) ∈ N2 . Étant donné un couple de coefficients de Bézout (u0 , v0 ), trouver tous les
couples de coefficients de Bézout (u, v) ç-à-d les couples vérifiant :

au + bv = d.

Définition 7.: (Nombres premiers) Un entier naturel p > 1 est dit premier s’il possède exactement deux divi-
seurs naturels, à savoir 1 et p.

Exemple 8.: 2, 3, 5, 7, 11, 13, 17, . . . sont des nombres premiers.

Remarque 7.: (Règle importante) Soit n ∈ N tel que n ≥ 2. Si n n’est pas premiers alors le plus petit
√
nombre premier p qui le divise vérifie : p ≤ n.
√
Par contraposée, si tous les nombres premiers p tels que p ≤ n ne divisent pas n, alors n est premier.

Exercice 10.: Parmi les nombres suivants : 67, 77, 87, 97, lesquels sont-ils premiers ?

Remarque 8.: Une méthode pour obtenir les nombres premiers est le crible d’Ératosthène. Pour une des-
cription détaillée du crible suivre le lien.

Proposition 5.: Soient a, b ∈ Z et p un nombre premier. Alors on a :

p|ab ⇔ p|a ou p|b

Page 5/7
 MPSI Arithmétique dans Z

Théorème 6.: (Théorème d’Euclide) L’ensemble des nombres premiers est infini.

Théorème 7.: (Théorème fondamental de l’arithmétique) Tout entier naturel non nul n se décompose de façon
unique en produit de nombres premiers. Autrement dit, n s’écrit :
Y
n= pvp (n)
p∈P

avec P est l’ensemble des nombres premiers et vp (n) le plus grand entier naturel m tel que pm (p premier)
divise n. vp (n) s’appelle la valuation p−adique de n.

Exercice 11.: Calculer v2 (54), v3 (54), v5 (54), v7 (54) et vp (54) avec p ∈ P et p ≥ 11. Décomposer 54 en
produit de nombres premiers.

Exercice 12.: Soient p, q ∈ P et k ∈ N. Calculer vp (q k ).

Proposition 6.: (Propriétés de la valuation) Soit (a, b) ∈ (N∗ )2 . Alors on a :

— ∀p ∈ P, vp (ab) = vp (a) + vp (b),
— a|b ⇔ (∀p ∈ P) vp (a) ≤ vp (b).
Y
Exercice 13.: Soit n = pvp (n) . Donner la décomposition en produit de nombres premiers de tous les
p∈P
diviseurs de n.

Proposition 7.: (PGCD et PPCM) Soit (a, b) ∈ (N∗ )2 . Alors on a :

Y
pgcd(a, b) = pmin(vp (a),vp (b))
p∈P
Y
ppcm(a, b) = pmax(vp (a),vp (b))
p∈P

Exercice 14.: Déterminer pgcd(255, 354) et ppcm(255, 354).

Exercice 15.: Soit a, b ∈ N∗ . Montrer que : a|b ⇔ a2 |b2 .

Exercice 16.: Soit n ∈ N∗ . Montrer que si n est à la fois un carré parfait et un cube parfait, alors il est
la puissance sixième d’un entier.

6. Relation de congruence :
Soit n ∈ N∗ .

Définition 8.: Soit (a, b) ∈ Z2 .

On dit que b est congru modulo n à a et on écrit : b ≡ a [n] ou b ≡n a, si n|b − a.
On note a la classe d’équivalence d’un entier a et Z/nZ l’ensemble des classes d’équivalence.

Exemple 9.: On a :
— a ≡2 0 si a est pair et a ≡2 1 sinon.
— 169 ≡3 1.
— ∀a ∈ Z, a ≡1 0.
— a|b ⇔ b ≡a 0.
— a ∧ b = 1 ⇔ ∃u ∈ Z, ua ≡b 1 ⇔ ∃v ∈ Z, vb ≡a 1.

Théorème 8.: La relation de congruence modulo n est une relation d’équivalence et la classe d’un entier a
s’écrit :
a = {a + kn/ k ∈ Z}
[
De plus, on a : Z = a.
a∈J0,n−1K
Page 6/7
 MPSI Arithmétique dans Z

Proposition 8.: 1) La relation de congruence modulo n est compatible avec la somme et la multiplication
dans Z. Autrement dit, elle vérifie la propriété suivante :

(a ≡n b et c ≡n d) =⇒ (a + c ≡n b + d et ac ≡n bd)

2) Si a ≡n b alors ∀m ∈ N∗ , am ≡n bm
3) Associativité : a + (b + c) ≡n (a + b) + c
4) Commutativité : a + b ≡n b + a et ab ≡n ba
5) Éléments neutres : a + 0 ≡n a et a × 1 ≡n a
6) Symétrie : a + (−a) ≡n 0
7) Distributivité : a(b + c) ≡n ab + ac

Corollaire 4.: Pour a, b ∈ Z, on note a + b = {x + y/ x ∈ a et y ∈ b} et ab = {xy/ x ∈ a et y ∈ b}. Alors

les propriétés précédentes s’énoncent encore :
a + b = a + b; ab = ab ; ∀m ∈ N∗ , am = am
a + (b + c) = (a + b) + c ; a+b = b+a; ab = ba ;
a+0 = a; a1 = a ; a + −a = 0 ;
a(b + c) = ab + ac) ;
7
Exercice 17.: Déterminer le dernier chiffre dans l’écriture décimale de 77 .

Exercice 18.: Soit n ∈ N. Montrer que 5|(3n+1 + 23n+5 ).

Théorème 9.: (Petit théorème de Fermat)

∀a ∈ Z, an ≡n a
avec n ∈ P.

Proposition 9.: Pour n ∈ N tel que n ≥ 2, on a :

n ∤ a =⇒ an−1 ≡n 1


n premier ⇔ ∀a ∈ Z,

Remarque 9.: Les deux résultats précédents s’énoncent encore :

— ∀x ∈ Z/nZ, xn = x
— n premier ⇔ ∀x ∈ Z/nZ, x ̸= 0 =⇒ xn−1 = 1

Exercice 19.: (Théorème de Wilson) Soit n ≥ 2.

n premier ⇔ (n − 1)! ≡n −1

Exercice 20.: 1) Soient a1 , · · · , an des entiers et m1 , · · · , mn des entiers naturels non nuls premiers entre
eux deux à deux. Résoudre le système d’inconnue x ∈ Z suivant :


 x ≡ a1 [m1 ]
..

 .

x ≡ an [mn ]


2) En déduire les solutions du système suivant :


 x ≡3 1


x ≡5 2

 x≡ 3

7

Exercice 21.: Déterminer les triplets (a, b, c) ∈ (N∗ )3 tels que :

ppcm(a, b) = 42; pgcd(a, c) = 3; a + b + c = 29

Exercice 22.: (Formule de Legendre) Soient n ∈ N∗ et p ∈ P. Montrer que :

+∞
X n
vp (n!) = E
k=1
pk

Page 7/7