Cours d’Algèbre

avec
Exercices Corrigés

Lhoussain El Fadil
Arithmétique des entiers

0.1 Introduction

En mathématiques, un entier naturel est un nombre positif permettant de dénombrer des

objets comptant chacun pour un. Donc de compter des objets semilaires : un objet, deux
objets . . . Un tel nombre entier peut s’écrire avec une suite finie de chiffres en notation
décimale. Chaque nombre entier n a un successeur unique n0 , c’est-à-dire un entier qui lui
est immédiatement supérieur, et la liste des entiers naturels est infinie. La définition, due à
Richard Dedekind, de l’ensemble des entiers naturels ne comprend pas 0 ; plus récemment
une autre définition a été proposée qui inclut 0. Ces deux définitions coexistent encore au-
jourd’hui. L’étude des entiers naturels et de leurs propriétés, constitue dès l’antiquité grecque
une branche des mathématiques appelée arithmétique. La structure des entiers naturels a été
axiomatisée pour la première fois par Peano et Dedekind à la fin du 19em siècle. À cette époque
0 n’était pas considéré comme un entier naturel (et certains auteurs font encore ce choix), ce
qui ne change pas fondamentalement l’axiomatisation. L’ensemble des entiers naturels, qu’il
contient ou non le nombre 0, est noté N. La notation est due à Dedekind en 1888, qui l’utilise
pour l’ensemble des entiers naturels non nuls. Aujourd’hui ce dernier ensemble est également
couramment) noté N∗ . Les entiers naturels s’identifient aux entiers relatifs positifs ou nuls,
ainsi qu’aux réels positifs ou nuls de partie fractionnaire nulle.

0.2 Propriété fondamentale de N

La propriété suivante est essentiel, elle implique en particulier l’existence de la division eucli-
dienne.

Théorème 0.1. Toute partie non vide A de N possède un plus petit élément.

Preuve. Si 0 ∈ A alors c’est fini. Sinon, soit n ∈ A. Donc après un nombre fini de test, on
selection un entier n0 tel que n0 < x pour tout x ∈ A et n0 ∈ A. Alors n0 est le plus petit
élément de A.

2
0.3. DIVISION EUCLIDIENNE 3

0.3 Division euclidienne

Rappelons que si a, b et c sont des entiers naturels non nuls et c = ab, alors c ≥ max(a, b), où
max(a, b) est le plus grand des deux nombres a et b.
En effet, en posant a = 1 + r, on a ab = b + br ≥ b. Donc c ≥ b. Par analogie, c ≥ a.

Théorème 0.2. (Division euclidienne étendue aux entiers relatifs) Soit (a, b) ∈ Z×Z∗ .
Il existe un couple unique (q, r) ∈ Z2 vérifiant : (∗) a = bq + r et 0 ≤ r < |b|.

Preuve. Pour l’existence, on suppose que b > 0 et on pose : A = {k ∈ Z | bk ≤ a}. Cet

ensemble est non vide. En effet, pour a ≥ 0, 0 est dans A et pour a < 0, a est dans A. De
plus il est majoré. En effet, pour a ≥ 0, a majore A et pour a < 0, 0 majore A. Il admet donc
un plus grand élément q qui vérifie : qb ≤ a < (q + 1)b. Il suffit alors de poser r = a − bq.
Pour b < 0 on travaille avec −b et on a l’existence de (q 0 , r0 ) vérifiant : a = −bq 0 + r0 et
0 ≤ r0 < −b. Et il suffit de poser q = −q 0 et r = r0 .
Pour l’unicité, supposons qu’il existe deux couples d’entiers (q, r) et (q 0 , r0 ) vérifiant (∗) avec
q 6= q 0 : On a alors : |r − r0 | = |b(q − q 0 )| ≥ |b| avec r et r0 dans [0, |b|[, ce qui est impossible.
On a donc q = q 0 et r = r0 . Le couple (q, r) vérifiant (∗) est donc unique.

Définition 0.1. La procedure de calcul du couple (q, r) est apelée la division euclidienne de
a par b. q est appelé son quotient et r est son reste.

0.3.1 Applications

Définition 0.2. Soient a, b deux entiers. On dit que b divise a s’il existe k ∈ Z tel que a = bk,
et on écrit b|a. Lorsque b 6= 0, b|a est équivalent à ce que le reste de la division enclidienne
de a par |b| est 0.

Proposition 0.1. Soient a, b, c, d, n des entiers tels que n ≥ 1.

1) Classification des entiers selon le reste de la division enclidienne par un entier naturel
non nul (en particulier, selon leur parité) :
Pour tout entier 0 ≤ r ≤ n − 1, posons Ar = {x ∈ Z, reste de x par n est r} . Alors
{Ar , 0 ≤ r ≤ n − 1} est une partition de Z. En particulier lorsque n = 2, {2Z, 2Z + 1}
est une partition de Z.
2) n|b =⇒ |b| ≥ n.
3) Les diviseurs de 1 sont 1 et −1.
4) Les inversibles de (Z, +, ×) sont 1 et −1.
5) Transitivité : n|b et b|a =⇒ n|a.
6) Addition et soustraction et combinaison linéaire : n|b et n|a =⇒ n|(ca + bd).
7) Multiplication : n|a et b|c =⇒ nb|ac et nk |ak pour tout entier k ≥ 0.

Preuve. 1) Pour tout r = 0, . . . , n − 1, r ∈ Ar . De plus l’unicité du reste de la division

euclidienne entraine que les Ar sont deux à deux disjoints. Finallement, pour chaque entier
4

n ∈ Z, x ∈ Ar , où r est le reste de la division euclidienne de x par n. Donc {Ar , 0 ≤ r ≤ n−1}

est une partition de Z.
2) Si n divise b alors n divise |b|. Posons donc |b| = nq. Comme b 6= 0 alors q ≥ 1. Donc
|b| ≥ nq ≥ n.
3) Soit x un diviseur strictement positif de 1. Alors 1 ≥ x et x = 1. Par suite, les seuls
diviseurs de 1 sont 1 et −1.
4) Tout inversible de (Z, +, ×) est un diviseur de 1. Par suite, il vaut 1 ou −1.
5) b|a =⇒ a = bq pour un certain entier q. De même n|b =⇒ b = nk pour un certain entier k.
Par conséquent a = nkq et kq est un entier.
6) n|a =⇒ a = nk pour un certain entier k. De même n|b =⇒ b = nh pour un certain entier
h. Par conséquent ca + bd = n(ck + dh) et (ck + dh) est un entier.
7) On suppose que n|a et b|c. Alors il existe (k, h) ∈ Z2 tels que a = nk et c = bh. Donc
ac = khnb, ce qui montre que nb|ac. Un raisonnement par récurrence sur k permet de voir
que nk |ak pour tout entier k ≥ 0.

Définition 0.3. Un entier p est dit premier si il est non inversible et ses seuls diviseurs
entiers sont 1, p et leur associé (opposé), c’est-à-dire p admet exactement 4 diviseurs entiers.

Proposition 0.2. Soit p un entier. Alors, les assertions suivantes sont équivalentes :
1) p est premier,
2) Pour tout entiers a et b, p = ab =⇒ |a| = 1 ou |a| = p.

Preuve. Evidente.

Proposition 0.3. Tout entiers n ≥ 2 admet un diviseur premier.

Preuve. Par récurrence sur n.

a) La propriété est evidement réalisée pour n = 2.
b) Soit n ≥ 2 un entier et supposons que pour tout entier 2 ≤ k ≤ n, k est divisible par un
nombre premier.
c) Pour n + 1, s’il est premier alors c’est fini. Sinon, il admet un diviseur propre d (2 ≤ d ≤
n − 1). Donc n + 1 = dk pour un certain entier k compris entre 2 et n. Par hypothèse de
récurrence, k est divisible par un certain nombre entier premier p. Par suite, p divise n+1.

Corollaire 0.1. L’ensemble des nombres premiers est infini.

Preuve. Notons par P l’ensemble des entiers naturels premiers et supposons par l’absurde
qu’il est fini. Comme 2 ∈ P, P est une partie non vide majorée de N. Posons p = max(P).
Soit n = p! + 1. Alors n ≥ 2 est un entier. Donc divisible par un entier premier q ≤ p (puisque
p = max(P)). Donc q divise n et p! et par suite, q divise 1 = n − p!. Absurde.

Proposition 0.4. (Test de primalité)

Soit n ≥ 3 un entier. Pour tester la primalité de n, on suit les étapes suivantes :
0.3. DIVISION EUCLIDIENNE 5

1) Si n est pair alors n n’est pas premier.

√
2) Sinon, soit n = a, .. avec a ∈ N.
a) Testons la divisibilité de n par les nombres premiers compris entre 3 et a.
b) Si on le trouve un diviseur de cette liste alors il n’est pas premier. Sinon il est
premier.

Preuve. 1) Si n est pair alors n est divisible par 2. Comme n ≥ 3, alors n admet au moins
3 diviseurs positives.
√
2) Supposons n impair et soit a la partie entière de n.
Si n n’est pas premier alors n admet un diviseur propre 1 < q < n. Donc n = qk avec
√
(q, k) ∈ N2 . On peut supposer que q ≤ k, alors q 2 ≤ qk = n. Par suite, q ≤ n et q ≤ a.

Donner tous les premiers positifs inferieurs ou égals à 100.

0.3.2 PGDC et PPCM

Rappelons tout d’abord que les sous groupes de (Z, +) sont sous la forme nZ, avec n ∈ N.

Définition 0.4. Soient a et b deux entiers dont l’un d’eux est au moins non nul.
On appelle le plus grand divisur commun de a et b, noté PGCD(a, b), l’unique entier naturel
n tel que aZ + bZ = nZ.
On appelle le plus petit multiple commun de a et b, noté PPCM(a, b), l’unique entier naturel
n tel que aZ ∩ bZ = nZ.

Proposition 0.5. Soient a, b, n, d et M des entiers tels que d, M ≥ 0.

PGCD(a, b) = d ⇐⇒ d|a et d|b et pour tout entier n, n|a et n|b =⇒ n|d.
PPCM(a, b) = M ⇐⇒ a|M et b|M et pour tout entier n, a|n et b|n =⇒ M |n.

Preuve. Posons PGCD(a, b) = d. Donc aZ ⊂ dZ. Par suite a ∈ dZ et d divise a. De même d

divise b. D’autre part, soit n un divseur commun de a et b. Alors aZ ⊂ nZ et bZ ⊂ nZ. par
suite, dZ = aZ + bZ ⊂ nZ et n divise d. Réciproquement, posons D =PGCD(a, b) et montrons
que D = d. Comme aZ + bZ = DZ, D divise à la fois a et b. Par suite, il divise d. D’autre
part, comme d est un diviseur commun de a et b alors aZ ⊂ dZ et bZ ⊂ dZ. Donc DZ ⊂ dZ ;
d divse D. Par conséquent, d = D.
Un raisonnement analogue prouve la deuxième.

Théorème 0.3. (Lemme d’Euclid) Soient p, a et b des entiers naturels.

Si p est premier et p divise ab alors p divise a ou p divise b.

Preuve. Soient p un entier premier et (a, b) ∈ N2 tel que p divise ab. Supposons que p ne
divise ni a ni b. Considérons alors H = {x ∈ N, p divise ax et ne divise pas x}. Comme b ∈ H,
H est une partie non vide de N. Posons d = min(H). Comme p ne divise pas d, d 6= 0. Par la
division euclidienne de p par d, posons p = dq + r avec (q, r) ∈ N2 et 0 ≤ r < d. Donc r 6∈ H,
p divise pa = adq + ar et adq (puisque elle divise ad). Donc p divise ar = adq − pa. Comme
6

r 6∈ H, p divise r. Comme p = dq + r alors 0 ≤ r < p (dq > 0). Par suite r = 0, p = dq et

d ∈ {1, p}. Si d = 1 alors p divise a. Si d = p alors p divise d. Ce qui est absurde.

0.3.3 Théorèmes fondamentales

Théorème 0.4. (Théorème de Bézout)

On dit que deux entiers a et b sont premiers entre eux si PGCD(a, b) = 1.
Deux entiers a et b sont premiers entre eux si et seulement si ∃(u, v) ∈ Z2 tel que au + bv = 1.

Attention Si on remplace 1 par un autre entier d ≥ 2, on n’a pas l’équivalence. Autrement

dit pour un entier d ≥ 2, “PGCD(a, b) = d” n’est pas équivalent à “il existe (u, v) ∈ Z2 tel
que au + bv = d”. Par exemple PGCD(3, 2) = 1 et 4 · 3 − 4 · 2 = 4.

Preuve. Si ∃(u, v) ∈ Z2 tel que au + bv = 1 alors aZ + bZ est un sous groupe de Z qui

contient 1. Par suite, il contient 1Z et aZ + bZ = 1Z.
Réciproquement, si PGCD(a, b) = 1 alors aZ+bZ = 1Z et ∃(u, v) ∈ Z2 tel que au+bv = 1.

Théorème 0.5. (Théorème de Gauss)

Soient a, b, c des entiers. Si a|bc et PGCD(a, b) = 1 alors a|c.

Preuve. Supposons que a|bc et PGCD(a, b) = 1 et montrons que a|c. Comme PGCD(a, b) = 1
alors par le théorème de Bezout, soit (u, v) ∈ Z2 tel que au + bv = 1. Donc c = auc + bvc.
Donc a divise à la fois auc et bvc. Donc divise c.

Lemme 0.1. (Algorithme d’Euclid)

Soient a et b deux entiers strictement positives. Par la division euclidienne a = bq + r. Alors
PGCD(a, b) =PGCD(r, b).

Preuve. Il suffit de montrer que pour tout entier d ≥ 1, d est un diviseur commun de (a, b)
si et seulemnt si d est un diviseur commun de (r, b).

Algorithme d’Euclid : On répete les divisions euclidiennes et chaque fois le diviseur b

devient le dividende ; et le reste r devient le diviseur. On s’arrête lorsque on obtient 0 comme
reste. Le PGCD(a, b) est donc le dernier reste non nul.

Exemple 0.1. Calcul du PGCD(1542, 58)

a b r
1542 58 34 24 10 4 2 0 .
q 26 1 1 2 2 2

Alors, PGCD(1542, 58) = 2.

0.3. DIVISION EUCLIDIENNE 7

Proposition 0.6. Soient a, b, k et d des entiers.

On a
PGCD(ka, kb) = |k|PGCD(a, b)
et si d ≥ 1 est un diviseur commun de a et b alors
a b
d.PGCD( , ) = PGCD(a, b).
d d

Preuve. On traite le cas où ab 6= 0. Posons PGCD(a, b) = d ; d ≥ 1 est un entier et aZ+bZ =

dZ. Par suite, kaZ + kbZ = |k|dZ et |k|d est un entier naturel ; PGCD(ka, kb) = |k|d.
La deuxième est une conséquence de la premieère.

Proposition 0.7. Soient a, b deux entiers. Alors

PGCD(a, b)PPCM(a, b) = |ab|.

Preuve. Si ab = 0 alors le résultat est évident. Sinon, alors montrons d’abord dans un premier
cas que si PGCD(a, b) = 1 alors en posant PPMC(a, b) = M , on a M = |ab|. Comme a divise
M et b divise M et PGCD(a, b) = 1 alors d’après le théorème de Gauss, ab divise M . Par
suite M ≥ |ab|. Comme M est le plus petit multiple commun de a et b alors M = |ab|.
Pour le cas général, posons PGCD(a, b) = d, a1 = ad et b1 = db . Alors PGCD(a1 , b1 ) = 1.
Par suite, PPMC(a1 , b1 ) = |a1 b1 | et PPMC(a, b) = PPMC(da1 , db1 ) = d PPMC(a1 , b1 ) =
d|a1 b1 | = |ab|
d .

0.3.4 Résolution d’une équation diophantienne ax + by = c.

Rappelons tout d’abord qu’une équation diophantienne est une équation polynomiale P (x1 , x2 , ..., xn ) =
0 à coefficients dans Z (ou Q) dont on cherche les solutions entières (ou rationnelles).

Proposition 0.8. Soient a,b et c trois entiers.

L’équation diophantienne ax+by = c admet des solutions si et seulement si PGCD(a, b) divise
c.

Preuve. Posons d =PGCD(a, b). Comme aZ+bZ = dZ, alors ∃(x, y) ∈ Z2 tel que ax+by = c
si et seulement si c ∈ aZ + bZ si et seulement si c ∈ dZ ; d divise c.

Exemple 0.2. L’equation diophantienne 12x + 15y = 4 n’admet pas de solutions puisque
PGCD(12, 15) qui est égal à 3 ne divise pas 4.

0.3.5 Comment résoudre une équation diophantienne ax + by = c ?

1) Par l’algoritme d’Euclid, cherchons une solution (x0 , y0 ) de ax+by = d avec PGCD(a, b) =
d.
c
2) Posons c1 = d et (x1 = c1 x0 , y1 = c1 y0 ) alors (x1 , y1 ) est une solution de ax + by = c.
8

3) Posons encore a0 = ad et b0 = db .
Soit (x, y) une solution de l’équation. Alors ax+by = c et ax1 +by1 = c. Par soustaraction
et simplification par d, on a a0 (x − x1 ) = −b0 (y − y1 ). Comme PGCD(a0 , b0 ) = 1, par
le théorème de Gauss, b0 divise x − x1 et a0 divise y − y1 ; il existe (k, h) ∈ Z2 tel que
x = x1 + b0 k et y = y1 + a0 h. En remplaçant dans l’égalité a0 (x − x1 ) = −b0 (y − y1 ), on
trouve que h = −k.
Par suite, la solution générale de l’équation ax + by = c est (x = x1 + kb0 , y = y1 −
ka0 ), k ∈ Z.

Exemple 0.3. Prenons l’équation diophantienne 31x+12y = m avec m ∈ Z. On a PGCD(31, 12) =

1 et (7, −18) est une solution de l’équation 31x + 12y = 1. Par suite, la solution générale de
l’équation 31x + 12y = m est (x = 7m + 12k, y = −18m − 31k), k ∈ Z.

0.3.6 Systèmes de numérations.

Théorème 0.6. Soient b ≥ 2 un entier. Pour tout entier naturel n, il existe un unique
entier naturel r, une unique suite d’entiers ci , i = 0, . . . , r telle que 0 ≤ ci < b, cr 6= 0 et
n = cr br + · · · + c1 r + c0 qu’on écrira n = cr · · · c0 (b) , appelé l’écriture de n en base b.
cr est appelé le bit dominant et c0 est appelé le bit le plus faible dans n = cr · · · c0 (b) .

Preuve. L’existence et l’unicité découle du fait que les ci sont obtenus suite à des divisions
euclidiennes successives par b.

Exponentiation. Soit (a, n) ∈ N2 . On veut estimer le nombre de multiplications exigiblent

pour calculer la puissance an . La méthode naive, an = a · a · · · a exige n − 1 multiplications. Il
existe une méthode alternative dite rapide. L’idée essentielle qui est à la base de cette méthode
est : si n = c0 + c1 2 + ... + cr 2r , écriture en base deux, alors :
r
an = ac0 (a2 )c1 ...(a2 )cr .

Ensuite vient l’idée astucieuse d’écrire :

an = ((...(acr )2 acr−1 )2 ...)ac1 )2 ac0 .

On lit donc l’écriture en base 2 de n de gauche à droite, on part de puiss := 1 et à chaque étape
s’il y a un 1 dans le développement de n en base 2 on remplace puiss par (puiss ∗ puiss) ∗ a,
sinon on prend juste le carrée, i.e. on remplace puiss par (puiss ∗ puiss).
Par exemple a13 =?, 13 = 1101 en base 2. Donc puiss0 = 1, puiss1 = a , puiss2 = a2 .a,
puiss3 = (a3 )2 = a6 , puiss4 = a(a6 )2 = a13 . Avec cette méthode, combien de multiplications
exige le calcul de an ?

Théorème 0.7. Soient a et n deux entiers supérieurs ou égaux à 2. Si n s’écrit avec r + 1

chiffres en base 2, alors la méthode d’exponentatiation ci-dessus permet de calculer an avec
au plus 2r multiplications.
0.3. DIVISION EUCLIDIENNE 9

Preuve. Soient a et n deux entiers supérieurs ou égaux à 2. Supposons que n s’écrit avec r +1
chiffres en base 2. Il faut r opérations (multiplications) pour calculer tous les carrées, et il faut
au plus r multiplications par a. Par conséquent, la méthode d’exponentatiation (ci-dessus)
permet de calculer an avec au plus 2r multiplications.

Remarque 0.1. Soient a et n deux entiers supérieurs ou égaux à 2. Dans la preuve du

théorème précédent on a vu que si n s’écrit avec r + 1 chiffres en base 2, alors lorsqu’on
veut calculer an , la méthode d’exponentatiation exige r multiplications pour calculer tous les
carrées. Donc pour calculer an , cette méthode exige un nombre de multiplications compris
entre r et 2r.

0.3.7 Valuations p-adiques

Théorème 0.8. Soient p un entier premier et n un entier. Si n 6= 0 alors posons νp (n) la

plus grande puissance de p qui divise n et νp (0) = ∞. Donc νp (n) : Z −→ N ∪ {∞} est une
application qui satisfait les propriétés suivante pour tout (n, m) ∈ Z2 :
1) νp (n) = ∞ ⇐⇒ n = 0.
2) νp (nm) = νp (n) + νp (m).
3) νp (n + m) ≥ min(νp (n), νp (m)).

Définition 0.5. Pour chaque nombre entier premier p, l’application νp est appelée la valuation
p-adique.

Théorème 0.9. (Théorème fondamental de l’arithmetique)

r
Y
Tout entier n tel que |n| ≥ 2 se factorise comme n = ∓ pei i avec pr > · · · > p1 ≥ 2 sont
i=1
des nombres entiers premiers et chaque ei ≥ 1 est un entier. Cette factorisation est unique,
dite la factorisation primaire de n.
Pour chaque entier premier p, posons νp (n) = ep . Si n 6= 0 alors ep = 0 sauf pour un nombre
Y
fini de premiers (sauf pour les diviseurs de n) et n = ∓ pep .
p premier ≥ 2

Preuve. Par récurrence forte.

Théorème 0.10. (Application au calcul du PGCD et PPCM)

Y Y
Soient n et m deux entiers. Posons n = ∓ pνp (n) et m = ∓ pνp (m) .
p premier ≥ 2 p premier ≥ 2
min pmax(νp (n),νp (m)) .
Y Y
(νp (n),νp (m))
Alors PGCD(n, m) = p et PPCM(n, m) =
p premier ≥ 2 p premier ≥ 2

Y
Preuve. Un diviseur quelconque de n s’écrit sous la forme d = ∓ pmp et un
p premier ≥ 2
10 CHAPITRE 3. ARITHMÉTIQUE DES ENTIERS

Y
multiple quelconque de n s’écrit sous la forme M = ∓ pMp avec mp ≤ νp (n) et
p premier ≥ 2
Mp ≥ νp (n). D’où le résultat.

0.3.8 Quelques fonctions arithmétiques

Définition 0.6. Pour tout entier n ≥ 1, posons ϕ(n) le nombre des entiers compris entre 1
et n qui sont premiers avec n, σ(n) le nombre de divseurs entiers strictements positifs de n
et τ (n) la some des divseurs entiers strictements positifs de n.

Théorème 0.11. Pour tout entier n ≥ 1, les applications ϕ, σ et τ de N −→ N sont des

applications multiplicatives, c’est-à-dire pour tous entiers m, n ≥ 1, PGCD(m, n) = 1 implique
f (mn) = f (m)f (n) pour f = σ, τ, ϕ.

Preuve. Pour ϕ, voir un peu plus tard (nous allons voir dans le chapitre suivant que ϕ est
le nombre d’inversibles modulo n).
Pour les deux autres, Qr le résultat se déduit en donnant leurs formules explictes. Soit n ≥ 1 un
ei
entier. Posons n = Qr i=1vi ip la factorisation primaire de n. Un diviseur d de n se factorise donc
comme suit d = i=1 pi avec 0 ≤Qvi ≤ ei est entier pour chaque i = 1, . . . , r. Le nombre des
puissances (v1 , . . . , vr ) est σ(n) = ri=1 (ei + 1). La somme des termes d’une suite géométrique
ei r
ei
X
k pei i +1 − 1 Y pei i +1 − 1
donne τ (pi ) = pi = pour tout i ∈ {1, ..., r}. Par suite, τ (n) = .
pi − 1 pi − 1
k=0 i=1
Soit maintenant m ∈ N un entier premier avec n et posons m = ti=1 qiri sa factorisation
Q
primaire. Comme m et n sont premiers entreQeux, alors pour chaque i = 1, . . . , r et j =
× n = ri=1 pei i × ti=1 qiri est sa factorisation primaire. Par suite
Q
1, . . . , t, pi 6=Q
qj . Par suite mQ
σ(n × m) = ri=1 (ei + 1) × ti=1 (ri + 1) = σ(n)σ(m) et σ est une application multiplicative.
r t
Y pei i +1 − 1 Y qiri +1 − 1
Il est aussi facile de voir que τ (n × m) = × = τ (n)τ (m) et τ est
pi − 1 qi − 1
i=1 i=1
une application multiplicative.

Exercices
Exercice 0.1. Déterminer les entiers positifs a et b sachant que a < 4000 et que la division
euclidienne de a par b donne un quotient de 82 et un reste de 47.

Exercice 0.2. Déterminer le quotient et le reste de la division euclidienne de 22013 + 562 par
4.

Exercice 0.3. Soit n ≥ 1 un entier. Déterminer le reste de la division euclidienne par n de

la somme des n premiers entiers naturels.

Exercice 0.4. Démontrer que sur la droite y = 43 x + 18 , il n’y a pas de points à coordonnées
entières.
EXERCICES 11

Exercice 0.5. Soient a, n et d trois entiers tous ≥ 1. Montrer que si d divise n alors ad − 1
divise an − 1.

Exercice 0.6. L’existence et l’unicité d’une forme irréductible d’un rationnel :

Montrer que tout rationnel x s’écrit sous la forme x = ab avec (a, b) ∈ Z × N∗ et PGCD(a, b) =
1.

Exercice 0.7. Montrer que si p ≥ 2 est un entier premier alors le coefficient binomial Cpk
est un multiple de p pour chaque k = 1, . . . , p − 1.
En déduire que si A est un anneau commutatif de caractéristique p premier alors f : A −→ A
définie par f (x) = xp est un mrphisme d’anneaux.

Exercice 0.8. Un calcul de PGDC.

Soient a et b ≥ 1 deux entiers naturels. Montrer que si d est le PGCD de a et b alors 2d − 1
est le PGCD de 2a − 1 et 2b − 1.

Exercice 0.9. Soit P = an xn + an−1 xn−1 + · · · + a0 ∈ Z[x] un polynôme unitaire.

1) Montrer que si P admet une racine rationnel x = ab (la forme irreductible) alors b|an
a|a0 . En particulier si P est un polynôme unitaire alors toute racine rationnel de P est
entière.
2) Résoudre dans Q, l’equation x3 + x2 − 2x − 8 = 0.

Exercice 0.10. Soient a et b deux rationnels tels que a + b et a × b sont des entiers. Montrer
que a et b sont des entiers.

Exercice 0.11. Montrer que si an − 1 est premier, alors a = 2 et n est premier.

On note Mn = 2n − 1 le nieme nombre de Mersenne. Vérifier que M11 n’est pas premier.

Exercice 0.12. Bonjour, je suis le magicien des mathématiques. Je vais deviner votre date
de naissance. Prenez votre jour de naissance. Multipliez le par 31. Prenez votre mois de
naissance. Multiplier le par 12. Ajoutez ces deux nombres. Combien trouvez-vous ? 811 vous
me dites ? Et bien vous êtes né un 25 mars ! En plus, c’est vrai. Mais comment a-t-il fait ?

Exercice 0.13. Soit f : N2 −→ N, définie par f (x, y) = 2x · 5y .

1) Montrer que f est injective.
2) f est elle surjective.
3) Trouver f −1 ({1}), f −1 ({0}), f −1 ({5}), f −1 ({30}) et f −1 ({48}).

Solutions des exercices

Exercice 0.1. Nous avons a = 82b+47 et a < 4000. Or a < 4000 ⇐⇒ b < 4000−47 82 ⇐⇒ b ≤ 48.
Comme le reste de la division est 47 alors b ≥ 48. De plus 48·82+47 = 3983 avec 3983 < 4000.
Par suite le seul couple qui satsfait les conditions est (a = 3983, b = 48).

Exercice 0.2. On a 22013 + 562 = (22011 + 140) × 4 + 2. Donc le reste de la division euclidienne
de 22013 + 562 par 4 est 2.
12 CHAPITRE 3. ARITHMÉTIQUE DES ENTIERS

Exercice 0.3. La somme des n premiers entiers naturels est égal à n(n+1) 2 .
n(n+1) n+1
Si n est impair, alors 2 = 2 × n. Dans ce cas le reste de la division euclidienne par n
de la somme des n premiers entiers naturels est 0.
Si n est pair, alors n(n+1)
2 = n2 × n + n2 . Comme n2 < n, alors dans ce cas le reste de la division
euclidienne par n de la somme des n premiers entiers naturels est n2 .

Exercice 0.4. Démontrons que sur la droite y = 34 x + 18 , il n’y a pas de points à coordonnées
entières.
Supposons le contraire. Soit donc (x, y) ∈ Z2 une solution. Alors 8y = 6x + 1 et 2(4y − 3x) = 1
et 2 divise 1. Absurde.

Exercice 0.5. Soient a, n et d trois entiers tous ≥ 1. Supposons que d divise n. Alors il existe
q ∈ N tel que n = dq. Par suite an − 1 = (ad )q − 1 = (ad − 1)((ad )q−1 + (ad )q−2 + ... + ad + 1).
Donc ad − 1 divise an − 1.

Exercice 0.6. L’existence et l’unicité d’une forme irréductible d’un rationnel :

Montrons que tout rationnel x s’écrit sous la forme x = ab avec (a, b) ∈ Z×N∗ et PGCD(a, b) =
1. Soit x un rationnel. Alors il existe (m, n) ∈ Z × N∗ tel que x = m n . Soit d =PGCD(m, n),
et soient a = m et b = n
. Alors x = a
avec (a, b) ∈ Z × N ∗ et PGCD(a, b) = 1.
d d b

p!
Exercice ??. Soient p ≥ 2 un entier premier et k = 1, . . . , p − 1. Comme Cpk = k!(p−k)! et
PGCD(p, k!(p − k)!) = 1. Alors k!(p − k)! divise (p − 1)! et p divise le coefficient binomial Cpk
est un multiple de p pour chaque k = 1, . . . , p − 1.
Si A est un anneau commutatif pour tout (a, b) ∈ A2 , (a + b)p = ap + p−1 k k p−k + bp .
P
k=1 Cp a b
Comme A est de caracteristique p alors Cpk = 0. Par suite (a + b)p = ap + bp et f : A −→ A
définie par f (x) = xp est un mrphisme de groupes. Comme l’anneau A est commutatif alors
f est un morphisme d’anneaux.

Exercice 0.8. Un calcul de PGDC.

Soient a et b ≥ 1 deux entiers naturels. Par la division Euclidienne, posons a = bq + r avec
bq −1
0 ≤ r < b. Alors 2a − 1 = 2bq 2r − 1 = 2r (2bq − 1) + 2r − 1 = (2b − 1)H + 2r − 1 avec H = 2r 22b −1
est un entier et 0 ≤ 2r − 1 < 2b − 1. On a encore PGCD(2a − 1, 2b − 1) =PGCD(2b − 1, 2r − 1).
Posons a0 = a, a1 = b et définissons a2 , ..., am comme pour l’algorithme d’Euclide avec
am =PGCD(am−1 , am−2 ) = d. Alors on a PGCD(2a − 1, 2b − 1) =PGCD(2a0 − 1, 2a1 −
1) =PGCD(2a1 − 1, 2a2 − 1) = ... =PGCD(2am − 1, 20 − 1) = 2am − 1 = 2d − 1.

Exercice 0.9. Soit P = an xn + an−1 xn−1 + · · · + a0 ∈ Z[x] un polynôme unitaire.

1) Montrons que si P admet une racine rationnel x = ab (la forme irreductible) alors b|an a|a0 .
En particulier si P est un polynôme unitaire alors toute racine rationnel de P est entiere.
P (a/b) = 0 ⇐⇒ an (a/b)n + an−1 (a/b)n−1 + · · · + a0 = 0. En multipliant par bn , puisque
bn 6= 0, alors P (a/b) = 0 ⇐⇒ a(an an−1 + ban−1 an−2 + · · · + bn−1 a1 ) = −bn a0 . Comme
PGCD(a, b) = 1, d’après le thérème de Gauss, a divise a0 . Aussi P (a/b) = 0 ⇐⇒ an an =
−b(an−1 an−1 + · · · + bn−2 a1 ) + bn−1 a0 ). Comme PGCD(a, b) = 1, d’après le théreme de Gauss,
b divise an .
2) Résolution dans Q, de l’equation x3 + x2 − 2x − 8 = 0.
Puisque an = 1 et a0 = −8 alors les solutions rationnelles candidates sont ∓1, ∓2, ∓4 et ∓8.
EXERCICES 13

Après vérification, 2 est la seule solution rationnel.

Exercice 0.10. Soient a et b deux rationnels tels que a + b et a × b sont des entiers. Montrons
que a et b sont des entiers.
a et b sont les solutions de x2 − Sx + P = 0. Comme le coefficient dominant est 1, alors d’après
l’exercice précédent, les racines sont entières.

Exercice 0.11. Montrons que pour tout entier naturel a ≥ 1, si an − 1 est premier, alors
a = 2.
Du fait que an − 1 = (a − 1)(an−1 + · · · + 1). Si an − 1 est premier, alors a − 1 est inversible,
i.e, a = 2.
Vu la question précédente, les seuls entiers de Mersenne candidats à être premiers sont les
2p − 1 avec p un entier premier.
Le nombre de Mersenne M11 n’est pas premier car M11 = 2047 qui est un multiple de 23.

Exercice 0.12. Soient x le jour de naissance et y le mois de naissance. Alors on a 31x + 12y =
811. D’après l’exemple 0.3 la solution générale de l’équation diophantienne 31x + 12y = m est
(x = 7m + 12k, y = −18m − 31k), k ∈ Z. Donc la solution générale de l’équation 31x + 12y =
811 est (x = 5677 + 12k, y = −14598 − 31k), k ∈ Z. Or
 1−5677
≤ k ≤ 31−5677
 
1 ≤ x ≤ 31 12 12 −473 ≤ k ≤ −471
⇐⇒ 12+14598 1+14598 ⇐⇒
1 ≤ y ≤ 12 −31 ≤ k ≤ −31 −471 ≤ k ≤ −471.

Donc k = −471 et par suite x = 25 et y = 3.

Exercice 0.13. Soit f : N2 −→ N, définie par f (x, y) = 2x · 5y .

0 0
1) Soient (x, y), (x0 , y 0 ) ∈ N2 . Si f (x, y) = f (x0 , y 0 ), alors 2x · 5y = 2x · 5y . Par le théorème
fondamental de l’arithmetique (x, y) = (x0 , y 0 ), et donc f est injective.
2) 3 n’admet pas d’antécédent par f . Par conséquent, f n’est pas surjective.
3) Trouver f −1 ({1}) = f −1 ({20 × 50 }) = {(0, 0)}, f −1 ({0}) = ∅, f −1 ({5}) = f −1 ({20 × 51 }) =
{(0, 1)}, f −1 ({30}) = f −1 ({2 × 3 × 5}) = ∅ et f −1 ({48}) = f −1 ({24 × 3}) = ∅.