•ARITHMETIQUE•

L’arithmétique est un des secteurs scientifiques les plus anciens et les plus féconds. Fondée
essentiellement par les pythagoriciens pour qui tout était nombre, elle a connu de grands pro-
grès sous l’impulsion de Fermat, Euler, Lagrange, Gauss et Legendre.
Longtemps considérée comme la branche la plus abstraite et la moins utile des mathéma-
tiques, elle connaît aujourd’hui de nombreuses applications en informatique, en électronique
et en cryptographie. Voici de façon presque détaille le plan du chapitre :

temadjoarthur@[Link] [Link] TEMADJO Arthur

 •Table des matières•
I NUMERATION . . . . . . . . . . . . . . . . . . . . . . . . . . 2
I.1 Division euclidienne dans N . . . . . . . . . . . . . . . . 2
I.2 Ordre dans N . . . . . . . . . . . . . . . . . . . . . . . 2
I.3 Système de numération . . . . . . . . . . . . . . . . . . 3
II DIVISIBILITE DANS Z . . . . . . . . . . . . . . . . . . . . . . 4
II.1 Division euclidienne . . . . . . . . . . . . . . . . . . . . 4
II.2 Multiple d’un entier . . . . . . . . . . . . . . . . . . . . 4
II.3 Congruence modulo n . . . . . . . . . . . . . . . . . . . 5
III PDCD et PPCM . . . . . . . . . . . . . . . . . . . . . . . . . 7
III.1 PPCM . . . . . . . . . . . . . . . . . . . . . . . . . . 7
III.2 PGCD . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
III.3 Recherche du pgcd . . . . . . . . . . . . . . . . . . . . 8
IV NOMBRES PREMIERS ENTRE EUX . . . . . . . . . . . . . . 8
IV.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . 8
IV.2 Théorème de Bezout . . . . . . . . . . . . . . . . . . . 8
IV.3 Théorème de Gauss . . . . . . . . . . . . . . . . . . . . 9
IV.4 Equations du type ax + by = c . . . . . . . . . . . . . . 10
V NOMBRES PREMIERS . . . . . . . . . . . . . . . . . . . . . . 11

temadjoarthur@[Link] [Link] TEMADJO Arthur

I1 Arithmétique Tle C Edition du 2 juillet 2014 2

I NUMERATION

I.1 Division euclidienne dans N

u r
Définition
r h
t couple (q, r) d’en-
A
Soit a et b deux entiers naturels non nuls. Il existe un unique

O a et b est appelée la divi-

tiers naturels tels que a = bq + r avec 0 ≤ r < b.
J
sion euclidienne de a par b. A D
L’opération qui permet de trouver q et r connaissant

M
TE
a est le dividende, b est le diviseur, q le quotient et r le reste.
Exemple :
23 = 7 × 3 + 2 ; 15 = 7 × 2 + 1 ; 10 = 10 × 1 + 0

I.2 Ordre dans N

Dans N, il est défini une relation notée ≤ par : ∀(a, b) ∈ N2, (a ≤ b ⇐⇒

∃c ∈ N, b = a + c).
Cette relation est une relation d’ordre car elle possède les caractéristiques
suivantes :
Propriété1
∀a, b, c ∈ N, on a :
• a ≤ a. On dit que la relation ≤ est réflexive.
• si a ≤ b et b ≤ a, alors a = b. On dit que la relation ≤ est antisymétrique.
• si a ≤ b et b ≤ c, alors a ≤ c. On dit que la relation ≤ est transitive.
De plus deux entiers naturels a et b sont toujours comparables, c’est à dire on
a toujours a ≤ b ou b ≤ a ; on dit alors que ≤ dans est une relation d’ordre
total.
Propriété2
Toute partie non vide de N admet un plus petit élément.
Exemple :

temadjoarthur@[Link] [Link] TEMADJO Arthur

I1 Arithmétique Tle C Edition du 2 juillet 2014 3

- 0 est le plus petit élément de N.

- Le plus petit élément de l’ensemble {5n + 2, n ∈ N} est 2.

I.3 Système de numération

On appelle système de numération un mode de représentation de tous les

entiers naturels à l’aide d’un nombre fini de symboles. Ces symboles sont ap-
pelés chiffres.
Théorème
Soit b un entier naturel supérieur ou égal à 2.
p
Tout entier naturel x non nul peut s’écrire de façon unique x = ∑ akbk, où les
k=0
ak sont des entiers naturels tels que 0 ≤ ak < b et a p 6= 0.
Il convient d’écrire x = a pa p−1 · · · a2a1a0b. Cette écriture est appelée écriture
de x en base b.
Par convention, les écritures sans "barre" sont en base 10.
Comment écrire un nombre en base b ?
Soit x = a pa p−1 · · · a2a1a0b.
Cette écriture équivaut aussi à x = a pb p + a p−1b p−1 + · · · + a2b2 + a1b + a0.
? x = b(a pb p−1 + a p−1b p−2 + · · · + a2b + a1) + a0. Donc q0 = a pa p−1 · · · a2a1b et
a0 sont respectivement le quotient et le reste de la division euclidienne de x par
b.
? On a q0 = b(a pb p−2 + a p−1b p−3 + · · · + a2) + a1. Donc q1 = a pa p−1 · · · a2b et
a1 sont respectivement le quotient et le reste de la division euclidienne de x par
b.
on peut ainsi déterminer de proche en proche l’écriture de x en base b.
Exemple
Ecrire le nombre 432 en base 7.
4
Ecrire le nombre 423 en base 10.
Remarque
Dévélopper un entier naturel x suivant les puissances de b revient à mettre x
sous la forme x = a pb p + a p−1b p−1 + · · · + a1b + a0.
temadjoarthur@[Link] [Link] TEMADJO Arthur
II 1 Arithmétique Tle C Edition du 2 juillet 2014 4

Exemple
Dévélopper 2837 suivant les puissances de 5.

II DIVISIBILITE DANS Z

II.1 Division euclidienne

Théorème
Soit a ∈ Z et b ∈ Z∗, il existe un unique entier relatif q et un unique entier
naturel r tels qu a = bq + r où 0 ≤ r < |b|
Exemple
47 = 9 × 5 + 2 ; −47 = 5 × (−10) + 3 ; 47 = (−5)(−9) + 2.
 
Attention !  Le reste d’une division euclidienne est toujours positif. Donc


éviter d’écrire par exemple −47 = 5(−9) − 2.

II.2 Multiple d’un entier

Soit n ∈ Z. On appelle multiple de n tout entier relatif x tel que x = kn où

k ∈ Z. C’est à dire le reste de la division euclidienne de x par n est 0.
On dit aussi que n est un diviseur de x si n 6= 0 ou que n divise x et on note n/x.
Soit n un entier relatif. On note nZ l’ensemble des multiples de n.
Ainsi x ∈ nZ ⇐⇒ ∃k ∈ Z/x = kn
Remarques
• Tout entier relatif est multiple de 1 et -1
• 0 est multiple de tout entier relatif
• ∀x ∈ nZ, ∀y ∈ Z, xy ∈ nZ
Théorème
La relation R définie dans Z par ∀(x, y) ∈ Z2, xRy ⇐⇒ x − y ∈ nZ est une
relation d’équivalence.
Preuve :
? ∀x ∈ nZ, x − x = 0 or 0 ∈ nZ donc xRx (Reflexivité)
? ∀(x, y) ∈ Z2, xRy ⇐⇒ x − y ∈ nZ
temadjoarthur@[Link] [Link] TEMADJO Arthur
II 1 Arithmétique Tle C Edition du 2 juillet 2014 5

⇐⇒ ∃k ∈ Z/x − y = nk
⇐⇒ y − x = −nk = n(−k) = nk0,k0 ∈ Z
⇐⇒ yRx (Symétrie)
? Soit x,y,z trois entiers tels que xRy et yRz.
xRy ⇐⇒ ∃k ∈ Z/x − y = nk
yRz ⇐⇒ ∃k0 ∈ Z/y − z = nk0
Ainsi, (x − y) + (y − z) = nk + nk0 donc x − z = n(k + k0) = nk00, k00 ∈ Z d’où
xRz (Transitivité)

II.3 Congruence modulo n

a) Définition
Soit n ∈ N∗, a et b deux entiers relatifs. On dit que a est congru à b modulo n
si (a − b) est un multiple de n. On note a ≡ b[n].
Exemple : 9 ≡ 1[2] ; 21 ≡ 6[5]
Propriété1 :
La relation de congruence modulo est une relation d’équivalence.
Preuve : il suffit de remplacer dans le théorème ci-dessus R par ≡
Propriété2 :
Soit n un entier naturel non nul, x et y deux entiers relatifs, r et r0 les restes des
divisions euclidiennes de x et y par n. On a : x ≡ y[n] ⇐⇒ r = r0.
Preuve :
On a x = nk + r et y = nk0 + r0.
Donc x − y = (k − k0)n + r − r0, avec −n < r − r0 < n
x ≡ y ⇐⇒ x − y ∈ nZ
⇐⇒ (k − k0)n + r − r0 ∈ nZ
⇐⇒ r − r0 ∈ nZ
⇐⇒ r − r0 = 0 car r − r0 < n
⇐⇒ r = r0
Propriété3 :
Soit n ∈ N∗. Soit (x, y, z,t) ∈ Z4.

temadjoarthur@[Link] [Link] TEMADJO Arthur

II 1 Arithmétique Tle C Edition du 2 juillet 2014 6

- si x ≡ y[n] et z ≡ t[n] alors x + z ≡ y + t[n]

- si x ≡ y[n] et z ≡ t[n] alors xz ≡ yt[n]
Il en résulte que la congruence modulo n est compatible avec l’addition et la
multiplication dans Z.
Preuve
- x ≡ y[n] ⇐⇒ x − y ∈ nZ et z ≡ t[n] ⇐⇒ z − t ∈ nZ
Ainsi, (x − y) + (z − t) ∈ nZ. D’où (x + z) − (y + t) ∈ nZ
Et par conséquent x + z ≡ y + t[n]
- x ≡ y[n] ⇐⇒ ∃k ∈ Z, x = nk + y et z ≡ t[n] ⇐⇒ ∃k0 ∈ Z, z = nk0 + t
xz = (nk + y)(nk0 + t) = n2kk0 + nkt + nyk0 + yt = n(nkk0 + kt + yk0) + yt
Donc xz − yt = n(nkk0 + kt + yk0). D’où xz − yt ∈ nZ et par conséquent xz ≡
yt[n].
Remarque : Si k ∈ Z∗, on a : x ≡ y[n] ⇐⇒ xk ≡ yk [n].
b) Définition
Soit a un entier relatif. On appelle classe d’équivalence de a, l’ensemble des
entiers relatifs qui sont congrus à a modulo n. Il est noté a. Ainsi, a = {x ∈
Z/x ≡ a[n]}.
x ∈ a ⇐⇒ x ≡ a[n]
⇐⇒ ∃k ∈ Z/x − a = kn
⇐⇒ x = kn + a
Ainsi, a = {x ∈ Z/∃k ∈ Z, x = nk + a}
On a :
0 = {x ∈ Z/∃k ∈ Z, x = nk} = nZ
1 = {x ∈ Z/∃k ∈ Z, x = nk + 1}
2 = {x ∈ Z/∃k ∈ Z, x = nk + 2}
...
n − 1 = {x ∈ Z/∃k ∈ Z, x = nk + n − 1}
n = {x ∈ Z/∃k ∈ Z, x = nk + n = n(k + 1) = nk0} = nZ = 0
Il existe n classes d’équivalence. On note Z/nZ l’ensemble des classes d’équi-
valence.
Z/nZ = {0, 1, 2, · · · , n − 1}

temadjoarthur@[Link] [Link] TEMADJO Arthur

III 1 Arithmétique Tle C Edition du 2 juillet 2014 7

Exemple : Z/3Z = {0, 1, 2} ; Z/6Z = {0, 1, 2, 3, 4, 5}

III PDCD et PPCM

Soit a et b deux entiers relatifs non nuls.

III.1 PPCM

Un entier M est un multiple commun de a et b si et seulement si M ∈ aZ ∩ bZ.

Le plus petit élément strictement positif de aZ ∩ bZ est appelé plus petit com-
mun multiple de a et b. On le note ppcm(a, b).
Exemple : ppcm(12, 15) = 60
Propriété
Posons µ = ppcm(a, b). On a donc aZ ∩ bZ = µZ. En effet, si a/M et si b/M
alors µ/M.

Propriétés
• ppcm(a, b) = ppcm(b, a)
• ∀k ∈ N∗, ppcm(ka, kb) = kppcm(a, b)
• µ = ppcm(a, b) =⇒ ∃(u, v) ∈ Z2, µ = au + bv

III.2 PGCD

L’ensemble des diviseurs communs de a et b noté D(a, b) contient 1 et est

fini. Il admet donc un plus grand élément strictement positif.
On appelle plus grand commun diviseur de a et b et on note pgcd(a, b), le
plus grand élément de D(a, b).
Propriétés
• pgcd(a, b) = pgcd(b, a)
• ∀k ∈ N∗, pgcd(ka, kb) = kpgcd(a, b)
• Si δ = pgcd(a, b) alors δ Z = {au + bv; (u, v) ∈ Z2}
• D(a, b) = D(δ )
temadjoarthur@[Link] [Link] TEMADJO Arthur
IV 1 Arithmétique Tle C Edition du 2 juillet 2014 8

III.3 Recherche du pgcd

Théorème : Algorithme d’Euclide

Soit a et b deux entiers relatifs et r le reste de la division euclidienne de a par
b.
? Si r = 0 alors pgcd(a, b) = b
? Si r 6= 0 alors pgcd(a, b) = pgcd(b, r)
Preuve
 Si r = 0 alors b/a =⇒ b/b et b/a. donc pgcd(a, b) = b.
 Si r 6= 0, alors a = bq + r =⇒ r = a − bq.
Soit d un diviseur commun de a et b. on a a = da0 et b = db0. Ainsi, r =
da0 − db0q = d(a0 − b0q). donc d/r. Ainsi, pgcd(a, b) = pgcd(b, r).
Exemple : Trouver le pgcd(12, 48) et pgcd(50, 70).
Propriétés
• Si d/a et d/b alors d divise toute combinaison linéaire de a et b.
En effet, ∀(u, v) ∈ Z2, au + bv = a0du + b0dv = d(a0u + b0v)
• b/a si et seulement si aZ ⊂ bZ
En effet, b/a =⇒ ∀M ∈ aZ, M = ka = ka0b donc M ∈ bZ d’où aZ ⊂ bZ.
Ensuite, aZ ⊂ bZ =⇒ ∀M ∈ aZ, b/M. Or a ∈ aZ donc b/a.
Par conséquent, b/a ⇐⇒ aZ ⊂ bZ

IV NOMBRES PREMIERS ENTRE EUX

IV.1 Définition

Deux entiers relatifs a et b sont dits premiers entre eux si pgcd(a, b) = 1.

pgcd(a, b) = 1 ⇐⇒ D(a, b) = {−1, 1}

IV.2 Théorème de Bezout

Soit a et b deux entiers relatifs non nuls.

pgcd(a, b) = 1 ⇐⇒ ∃(u, v) ∈ Z2, au + bv = 1.

temadjoarthur@[Link] [Link] TEMADJO Arthur

IV 1 Arithmétique Tle C Edition du 2 juillet 2014 9

Exemple :
- Montrer que 23 et 16 sont premiers entre eux
- trouver deux entiers relatifs u et v tels que 23u + 16v = 1

IV.3 Théorème de Gauss

Soient a,b et c trois entiers relatifs. Si a et b sont premiers entre eux et si

a/bc alors a/c. C’est à dire (pgcd(a, b) = 1 et a/bc) =⇒ a/c
Preuve
a/bc =⇒ bc = ka et pgcd(a, b) = 1 =⇒ au + bv = 1
1 = au + bv =⇒ c = cau + cbv
=⇒ c = cau + kav
=⇒ c = a(cu + kv)
=⇒ a/c
Propriétés
Soit a, b et c trois entiers relatifs.
• (pgcd(a, b) = 1 et pgcd(a, c))=⇒ pgcd(a, bc) = 1
En effet, on a : au + bv = 1 et ax + cy = 1.
(au + bv)(ax + cy) = 1 ⇐⇒ a2ux + acy + abvx + bcvy = 1
⇐⇒ a(aux + cy + bvx) + bc(vy) = 1
⇐⇒ aα + bcβ = 1
⇐⇒ pgcd(a, bc) = 1.
Conséquence :
pgcd(a, b) = 1 =⇒ pgcd(a, b2) = 1
=⇒ pgcd(a2, b) = 1
• Si pgcd(a, b) = 1 alors ppcm(a, b) = ab
• Soit a et b deux entiers relatifs non nuls tels que pgcd(a, b) = δ . Il existe
deux entiers relatifs a0 et b0 non nuls et premiers entre eux tels que a = a0δ et
b = b0 δ .
• Si a/c et b/c et si pgcd(a, b) = 1 alors ab/c.
• Si δ = pgcd(a, b) et µ = ppcm(a, b) alors δ µ = |ab|

temadjoarthur@[Link] [Link] TEMADJO Arthur

IV 1 Arithmétique Tle C Edition du 2 juillet 2014 10

Exemple : (
a + b = 20
? Trouver deux entiers naturels a et b tels que :
pgcd(a, b) = 4
Solution 
(  a = 4a0 et b = 4b0
a + b = 20 
⇐⇒ pgcd(a0, b0) = 1
pgcd(a, b) = 4  a0 + b0 = 5


Donc (a0, b0) ∈ {(1, 4); (2, 3); (3, 2); (4, 1)}.
Ainsi, (a, b) ∈ {(4, 16); (8, 12); (12, 8); (16, 4)}(
a + b = 30
? Trouver deux entiers naturels a et b tels que :
pgcd(a, b) = 5

IV.4 Equations du type ax + by = c

Théorème
Soit l’équation (E) : ax + by = c où (a, b) ∈ Z∗ et c ∈ Z.
L’équation (E) admet une solution dans Z2 si et seulement si pgcd(a, b) divise
c.
Théorème
( b) = δ divise c alors l’équation (E) a une infinité de solution de la
Si pgcd(a,
x = x0 − δb t
forme : t ∈ Z où (x0, y0) est une solution particulière de l’équa-
y = y0 + δa t
tion (E)
Preuve
Soit l’équation (E) : ax + by = c et (x0, y0) une solution particulière de (E).
(
ax + by = c
⇐⇒ a(x − x0) + b(y − y0) = 0
ax0 + by0 = c

⇐⇒ δa (x − x0) + δb (y − y0) = 0

⇐⇒ δa (x − x0) = − δb (y − y0)

temadjoarthur@[Link] [Link] TEMADJO Arthur

V1 Arithmétique Tle C Edition du 2 juillet 2014 11

⇐⇒ δa / δb (y − y0) et δb / δa (x − x0) or a
δ et b
δ sont premiers entre

eux. Donc δa /(y − y0) et δb /(x − x0)

a a
δ /(y − y0 ) ⇐⇒ y − y0 = δ t, t ∈Z
⇐⇒ y = y0 + δa t
a b a b a
δ (x − x0 ) = − δ (y − y0 ) ⇐⇒ δ (x − x0 ) = − δ (y0 + δ t − y0 )
⇐⇒ δa (x − x0) = − δb δa t
⇐⇒ x − x0 = − δbt
⇐⇒ x = x0 − δb t
Exemple :
Résoudre dans Z les équations 3x + 8y = 8 et 1045x + 561y = 33.
Trouvons d’abord deux entiers relatifs x0 et y0 tels que 3x0 + 8y0 = 8.
Après division euclidienne, on a :
8 = 3(2) + 2 et 3 = 2(1) + 1
3 = 2(1) + 1 ⇐⇒ 1 = 3 − 2
⇐⇒ 1 = 3 − (8 − 3(2))
⇐⇒ 1 = 3 − 8 + 3(2)
⇐⇒ 1 = 3(3) + 8(−1)
⇐⇒ 8 = 3(24) + 8(−8)
⇐⇒ 3(24) + 8(−8) = 8. Donc x0 = 24 et y0 = −8.
Ainsi, (24, −8) sont des solutions particulières de 3x + 8y = 8.
Comme
 pgcd(3, 8) = 1 alors les solutions

de l’équation sont :
(x, y) ∈ {(24 − 8t, −8 + 3t);t ∈ Z}


V NOMBRES PREMIERS

Définition
Un nombre entier naturel p est premier s’il possède exactement deux diviseurs
positifs qui sont 1 et p.
Propriétés

temadjoarthur@[Link] [Link] TEMADJO Arthur

V1 Arithmétique Tle C Edition du 2 juillet 2014 12

? Soit p un nombre premier. L’ensemble des diviseurs positifs de p est {1, p}.
? Soit p un nombre premier et d un entier relatif. Si d/p alors d ∈ {−p, −1, 1, p}.
? Soit p un nombre premier et a un entier relatif. Si a ne divise pas p, alors
pgcd(a, p) = 1 ou pgcd(a, p) = p.
? Pour tout entier naturel X, il existe un p-uplet (p1, p2, · · · , pn) d’entiers natu-
rels premiers tel que X = pα1 1 pα2 2 · · · pαn n , αi ∈ N. Cette écriture est la décompo-
sition de X en produit de facteurs premiers.
Théorème
Soit X = pα1 1 pα2 2 · · · pαn n la décomposition de X en produit de facteurs premiers.
X admet exactement (α1 + 1)(α2 + 1) · · · (αn + 1) diviseurs positifs.
Exemple
Donner le nombre de diviseurs positifs de 60 et déterminer ces diviseurs.
60 = 22 × 3 × 5. Donc 60 a exactement (2 + 1)(1 + 1)(1 + 1) diviseurs positifs
c’est à dire 12.
(20 + 21 + 22)(30 + 31)(50 + 51) = (1 + 2 + 4)(1 + 3)(1 + 5)
= (1 + 3 + 2 + 6 + 4 + 12)(1 + 5)
= 1+5+3+15+2+10+6+30+4+20+12+60. Ainsi,
les diviseurs positifs de 60 sont : 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

temadjoarthur@[Link] [Link] TEMADJO Arthur