Arithmétique (Résumé). Pr.

Bennis

Théorème de la division Euclidienne. ∀(a, b) ∈ Z × Z∗ , d’entiers ∃!(q, r) tel que a = b · q + r avec 0 ≤ r < |b|.
Ainsi, effectuer la division euclidienne de a par b revient à trouver les entiers q et r satisfaisant les conditions ci-dessus.
On appelle les nombres a, b, q et r respectivement le dividende, le diviseur, le quotient et le reste de la division euclidienne de a par b.
Divisibilité dans Z Nombres premiers
2
Soit (a, b) ∈ Z . S’il existe un entier relatif k tel que a = kb, on dit que : Un entier relatif p est dit premier s’il admet quatre diviseurs : p, −p, 1 et −1.
— b divise a, noté b/a, Théorème. L’ensemble des nombres premiers est infini.
— b est un diviseur de a, Crible d’Ératosthène. Si un entier naturel a n’est pas premier, alors il admet
— a est un multiple de b. un diviseur premier p vérifiant √ p2 ≤ a. En pratique : Si tous les nombres
En particulier, si b ̸= 0, dire que b divise a est équivaut à dire que le reste de premiers p vérifiant p ≤ a ne divisent pas n, alors n est aussi premier.
la division euclidienne de a par b est nul. Le théorème fondamental de l’arithmétique. Tout entier non nul a ̸= 1
L’ensemble des diviseurs d’un entier n est souvent noté D(n) et l’ensemble des et −1 se décompose d’une manière unique en produit de nombres premiers :
multiples de n est noté nZ. a = εpα αn
1 · · · pn tel que les pi sont des nombres premiers positifs différents deux
1

Propriétés de la Divisibilité des Entiers. à deux et tel que ε = 1 si a > 0 ou ε = −1 si a < 0.

Réflexivité : ∀a ∈ Z, a/a - Le nombre des diviseurs positifs de a est : N = (1 + α1 ) · · · (1 + αn ).
β1
Transitivité : ∀a, b, c ∈ Z, (a/b et b/c) ⇒ (a/c) - On calcule le PGCD et le PPCM de a = pα αn
1 · . . . · pn et b = p1 · . . . · pn
1 βn

Combinaison linéaire : ∀a, b, c, k, l ∈ Z, (a/b et a/c) ⇒ (a/kb + lc) comme suit :

Stabilité par passage à l’opposé : ∀a, b ∈ Z, (b/a) ⇔ (b/ − a) ⇔ (−b/ − a) pgcd(a, b) = pmin(α 1
1 ,β1 )
·. . .·pnmin(αn ,βn ) , ppcm(a, b) = p1
max(α1 ,β1 )
·. . .·pmax(α
n
n ,βn )

la divisibilité est antisymétrique sur N : ∀a, b ∈ Z, (b/a et a/b) ⇔ |b| = |a| Propriétés. Pour tout nombre premier p, et ∀a, b ∈ Z :
Produit : ∀a, b, a′ , b′ ∈ Z, (a/b et a′ /b′ ) ⇒ (aa′ /bb′ ) ▶ p ne divise pas x si et seulement si p ∧ x = 1.
En conséquence, ∀a, b ∈ Z, ∀n ∈ N, (a/b) ⇒ (an /bn ) ▶ p/ab si et seulement si p/a ou p/b.
Comparaison et divisibilité : ∀a, b ∈ Z, (a/b et b ̸= 0) ⇒ |a| ≤ |b| En particulier, ∀n ∈ N, p/an si et seulement si p/a.
PGCD de deux entiers PPCM de deux entiers
Définition : Soient a et b deux entiers non tous deux nuls. Le plus grand Définition : Soient a et b des entiers non nuls. Le plus petit commun multiple
commun diviseur de a et b (noté pgcd(a, b) ou a ∧ b) est le plus grand entier de a et b (noté ppcm(a, b) ou a ∨ b) est le plus petit entier positif qui est à la
positif divisant à la fois a et b. fois multiple de a et de b.
Caractérisation : Soit ∆ un diviseur commun de a et b. Alors, ∆ = a ∧ b si Caractérisation : Soit un multiple commun de a et b. Alors, = a ∨ b si et
et seumement si (∀d ∈ Z, d/a et d/b ⇔ d/(a ∧ b)). seumement si (∀m ∈ Z, a/m et b/m ⇔ a ∨ b/m).
Propriétés : a ∧ 1 = 1 ; a ∧ 0 = |a| ; a ∧ b = b ∧ a ; [a/b ⇔ a ∧ b = |a| Propriétés : a ∨ 1 = |a| ; a ∨ 0 = 0 ; a/b ⇔ a ∨ b = |b|
a b 1 a b 1
(ka)∧(kb) = |k|·(a∧b). En conséquence, Si k/a et k/b, alors ∧ = ·(a∧b) ka∨kb = |k|·(a∨b). En conséquence, Si k/a et k/b, alors alors ∨ = ·(a∨b)
k k |k| k k |k|
Deux entiers non nuls sont dits premiers entre eux lorsque a ∧ b = 1.
PGCD et PPCM : (a ∧ b) · (a ∨ b) = |ab|
Proposition : a ∧ b = 1 et a ∧ c = 1 ⇒ a ∧ bc = 1
En particulier : Si a ∧ b = 1, alors a ∨ b = |ab|.
En particulier : a ∧ b = 1 ⇒ an ∧ bm = 1 pour tous m et n de N∗
Théorème : Si a/n et b/n et si a ∧ b = 1, alors ab/n.
Théorème de Bézout Soient a et b des entiers non nuls.
Théorème de Gauss : Si a/bc et a ∧ b = 1, alors a/c.
Pour déterminer le PGCD de deux entiers, on peut utliser l’un des deux alro- ▶ a ∧ b = d =⇒ ∃(u, v) ∈ Z2 : ua + vb = d
rithmes : ▶ a ∧ b = 1 ⇐⇒ ∃(u, v) ∈ Z2 : ua + vb = 1
Algorithme d’Euclide : Soit r le reste de la division euclidienne de a par b, L’égalité ua + vb = 1 est appelée l’identité de Bézout. Pour trouver un exemple
alors a ∧ b = b ∧ r. du couple u, v vérifiant l’identité de Bézout, on peut utiliser : l’algorithme
Formule de la différence : a ∧ b = a ∧ (a − b) d’Euclide ou d’autres méthodes algorithmiques.

1
Arithmétique (Résumé). Pr. Bennis

L’ensemble des classes d’équivalences (Partie 1. Introduction)

L’ensemble Z/2Z et la parité des entiers L’ensemble Z/nZ et reste de la division euclidienne
Un entier n ∈ Z est dit pair (resp., impair) si n = 2k (resp., n = 1 + 2k) pour Nous avons vu que l’ensemble Z est partitionné en termes de parité des entiers,
un certain entier k. Ainsi, l’ensemble des entiers pairs (resp., impairs) sera noté en parties des entiers pairs 2Z et des entiers impairs 1+2Z. Cela peut s’exprimer
2Z (resp., 1 + 2Z). Ces deux ensembles forment une partition de Z car un entier en termes de la division euclidienne par 2, de sorte que 2Z est exactement
est soit pair, soit impair : Z = 2Z ∪ (1 + 2Z) et 2Z ∩ (1 + 2Z) = ∅. l’ensemble des entiers dont le reste de la division euclidienne par 2 est nul,
Ces ensembles sont appelés des classes modulo 2 et forment un nouvel ensemble cependant 1 + 2Z est exactement l’ensemble des entiers dont le reste de la
noté Z/2Z. C’est-à-dire Z/2Z = {2Z, 1 + 2Z} division euclidienne par 2 est égal à 1. Donc, en terme de la division euclidienne,
La classe des entiers pairs 2Z ou celle des entiers impairs peut être représentée la notion de l’anneau Z/2Z peut s’étendre à n’importe quel entier n ∈ N−{0, 1}.
par n’importe quel de ses éléments. Autrement dit, Explicitement, pour un entier r ∈ {0, . . . , n − 1}, les entiers qui ont le même
— si a est un entier pair, on dit que a est un représentant de 2Z. On écrit reste r dans la division euclidienne par n s’écrivent d’une manière unique sous
a = 2Z. la forme r + nq pour un certain q ∈ Z. Cet ensemble sera noté r + nZ et appelé
— si a est un nombre impair, alors on écrit a = 1 + 2Z. la classe de r modulo n. En particulier, pour r = 0, r + nZ n’est que l’ensemble
Ainsi, a = b signifie que a et b ont la même parité. Donc, par exemple : nZ des multiples de n. Donc,
— a = 0 signifie que a est pair.
— a = 1 signifie que a est imppair. Z = nZ ∪ (1 + nZ) ∪ · · · ∪ ((n − 1) + nZ)
En conclusion, Z/2Z ={0, 1}
Lois sur Z/2Z. L’ensemble de ces classes est noté Z/nZ.
Nous savons que la somme de deux entiers ayant la même parité est paire, Maintenant, pour un entier a, on désigne par a+nZ (ou cln (a), ou simplement a
tandis que la somme de deux entiers de parité différente est impaire. De plus, s’il n’y a pas de confusion sur n), l’ensemble des entiers de la forme a + nq pour
le produit de deux entiers est pair si l’un des facteurs est pair. un certain q ∈ Z. On a l’équivalence importante (à montrer !) : a + nZ = r + nZ
Ainsi, on définit les deux lois sur sur Z/2Z : pour tous deux classes a et b, pour un certain r ∈ {0, . . . , n − 1} si et seulement si a ∈ r + nZ, c’est-à-dire, r
— la somme : a + b = a + b est le reste de la division euclidienne de a par n. Ainsi, les assertions suivantes
— le produit : a · b = a · b. sont équivalentes pour tous entiers a et b :
On trouve les tables d’addition et de multiplication de Z/2Z : a = b ⇔ b ∈ a ⇔ a et b ont le même reste dans la division euclidienne par
Addition Multiplication n ⇔ a − b ∈ nZ ⇔ a = b + nk pour un certain k ∈ Z.
+ 0 1 · 0 1
0 0 1 0 0 0 Cette dernière assertion peut également être lue "a est congru à b modulo n"
1 1 0 1 0 1 ou "a et b sont congrus modulo n". On note aussi a ≡ b (mod n) ou a ≡ b[n]
pour signifier que a = b dans Z/nZ.
Muni de ces deux lois, Z/2Z est un corps. Lois sur Z/nZ.
Application. On montre que pour tout n, n 2023
− n est pair. En effet, dans Pour toutes deux classes a et b dans Z/nZ, on définit
Z/2Z, — la somme : a + b = a + b
n 2023 − n = n(n 2022 − 1) = n n 2022 −1 — le produit : a · b = a · b.
Muni de ces deux lois, Z/nZ est un anneau d’élément neure 0 pour l’addition
Donc, dans les deux cas n = 0 ou n = 1, n2023 − n = 0. et 1 pour la multiplication.

k  
∗ k
X k k−i α α−1
Identités remarquables. ∀a, b ∈ Z, ∀α ∈ N , (a + b) = ai · b (Binôme de Newton) (aα − b ) = (a − b)(aα−1 + aα−2 b + · · · + b )
i=0
i
−1
En conséquence, si ak = 0 pour un certain k ∈ (i.e., a est nilpotent), Alors, 1 − a (et donc aussi a − 1) est inversible avec : 1 − a = aα−1 + aα−2 + · · · + 1

2
Arithmétique (Résumé). Pr. Bennis

L’ensemble des classes d’équivalences (Partie 2. opérations et calculs)

L’anneau Z/nZ (plus de propriétés de calcul) La fonction indicatrice d’Euler (Indicateur d’Euler)
On fixe n ∈ N . L’ensemble Z/nZ muni de l’addition et de la multiplication des La fonction indicatrice d’Euler, notée ϕ, est une application sur N∗ telle que
∗

classes d’équivalence est un anneau commutatif. Nous avons aussi les propriétés pour chaque entier n, ϕ(n) est le nombre d’entiers positifs inférieurs ou égaux
suivantes : à n et premiers avec n. Ce nombre ϕ(n) est appelé l’indicateur d’Euler.
Les opposés dans Z/nZ. ∀a ∈ Z, −a = −a. En général, ∀k ∈ Z, ka = ka Donc, ϕ(n) est le nombre d’éléments inversibles de l’anneau Z/nZ, c’est-à-dire
Eléments inversibles dans Z/nZ. ∀a ∈ Z, a est inversible dans Z/nZ si et l’ordre du groupe multiplicatif ((Z/nZ)∗ , ×).
seulement si a∧n = 1. L’inverse de a est obtenu à travers l’identité de Bézout, de Exemples. On a ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = ϕ(4) = ϕ(6) = 2, ϕ(5) = 4. En
−1
sorte que si ua + vn = 1, alors a−1 = u. En particulier, n − 1 = n − 1 = −1. fait, pour tout nombre premier p, ϕ(p) = p − 1.
En conséquence, Z/nZ est un corps si et seulement si n est un nombre premier. Plus généralement, pour tout nombre premier p et tout entier r ≥ 1, on a
r r r−1
Attention ! Lorsque a est inversible, a−1 = a−1 n’a pas de sens, car a−1 ∈ / Z ϕ(p ) = p − p .
sauf pour a = ±1. A part cela, nous bénéficions de toutes les règles de calcul des Pour calculer ϕ(n) pour tout n, on utilise le résultat dont la preuve utilise
∗
puissances avec exposant un entier relatif comme dans Z. Notamment, Lorsque l’isomorphisme f : ∀u, v ∈ N , ϕ(uv) = ϕ(u)ϕ(v).
a a a
a est inversible : (aα )−1 = a−α . En général, (aα )β = aβα ∀β, α ∈ Z. Si n = p1 1 p2 2 . . . pkk est la décomposition en facteurs premiers de n, alors
α α
Attention ! L’égalité a = a n’a de sens que pour α ∈ N. Cette égalité     
est d’une grande utilité dans le calcul des restes des divisions euclidiennes des 1 1 1
ϕ(n) = n 1 − 1− ... 1 −
puissances des entiers. p1 p2 pk

Problème classique : Théorème des restes Chinois Théorèmes classiques

Soient n1 , ...,nk des entiers 2 à 2 premiers entre eux (avec k ≥ 2 un entier). Théorème de Wilson. Soit p > 0 un entier premier. Considérons le groupe
Yk multiplicatif (Z/pZ)∗ = {1, 2, . . . , p − 1}.
∀a1 ,...,ak ∈ Z, ∃! x ∈ Z (unique modulo ni ) solution du système : Chaque élément de ce groupe, à l’exception de 1 et p − 1, possède un inverse
i=1 distinct. En d’autres termes, si a est une classe dans {2, . . . , p − 2} (pour p > 2),
 alors il existe une classe b telle que a·b = 1 dans (Z/pZ)∗ . En multipliant toutes
 x ≡ a1 (mod n1 )
ces classes, on obtient 2 · 3 · · · p − 2 = 1. Ainsi, (p − 1)! = p − 1 = −1.
(S) ...
En termes d’équivalence modulo p, (p − 1)! ≡ −1 (mod p).
x ≡ ak (mod nk )

Théorème d’Euler.
Pour résoudre ce système, on suit les étapes suivantes : Pour tous entiers a et n premier entre eux, aϕ(n) ≡ 1 (mod n).
k Corollaire (Petit Théorème de Fermat). Si p est un nombre premier et a
Y n
On pose n = ni et on considère n̂i = . Alors, ni ∧ n̂i = 1. Donc, d’après est un entier premier avec p, alors ap−1 ≡ 1 (mod p).
i=1
n i En conséquence, pour tout entier α, αp−1 ≡ α (mod p).
le théorème de Bézout, on a une égalité ui ni + vi n̂i = 1 pour certains entiers Corollaire utile pour le chiffrement RSA (Rivest-Shamir-Adleman).
ui et vi . Donc, ei ≡ 1 (mod ni ) et ei ≡ 0 (mod nj ) pour j ̸= i Soient p et q deux nombres premiers distincts, et soit n = pq. Pour tout M ∈ Z,
Xk
On pose x0 = ai ei . Donc x0 est une solution particulière du système (S). Et M (p−1)(q−1) ≡ M (mod n)
i=1
ainsi, les solutions du système (S), sont les entiers x vérifiant x ≡ x0 (mod n). Alors, pour tous les entiers e et d tels que ed ≡ 1 (mod pq), M ed ≡ M (mod n).
Théorème des restes Chinois en termes d’applications. Notez que e ∧ pq = 1. Ainsi, pour un tel e, d s’obtient avec des algorithmes
k
Y tels que l’algorithme d’Euclide. Ce résultat est la clé du chiffrement RSA, de
On pose f : Z/(n1 · · · nk )Z → Z/ni Z avec f (x̄) = (cln1 (x), ..., clnk (x)).
sorte que même si e et n peuvent être déclarés publiquement, l’entier d n’est
i=1
Alors, f est un isomorphisme d’anneaux. pas accessible tant que p et q ne sont pas déclarés et suffisamment grands.