M1 MEEF SD Maths Arithmétique

Arithmétique

Ces notes ne constituent pas un cours - elles ne sont ni exhaustives, ni rigoureuses, et ne contiennent
que trop peu d’exemples et à peu près aucune preuve. Il ne s’agit que d’une fiche de brefs rappels.

Soient a et b deux entiers relatifs.

Divisibilité
• On dit que a divise b, ou que a est un diviseur de b s’il existe k ∈ Z tel que b = ka. On note a|b.
• On dit alors que b est un multiple de a.
◦ 0 est divisible par tout entier de Z, et ne divise que lui-même.
b est toujours divisible au moins par ±1 et ±b.
Les critères de divisibilité sont à savoir énoncer et démontrer
◦ a|b est une relation d’ordre (non total) sur N, mais pas sur Z
En particulier, si a, b ∈ N, (a|b et b|a) ⇐⇒ a = b
◦ Si c ∈ Z divise a et b, alors c divise au + bv, ∀u, v ∈ Z2 .
Si c ∈ Z divise a et d ∈ Z divise b, alors cd divise ab.

◦ [Théorème de Division Euclidienne. ] Soient (a, b) ∈ Z2 avec b 6= 0. Il existe un unique couple

(q, r) ∈ Z2 tels que 
a = bq + r
(E)
0 ≤ r < |b|.
(preuve à connaitre : unicité par l’absurde ; existence par récurrence, d’abord pour a, b ≥ 0, puis a ≤ 0...)
• On dit que (E) est la division euclidienne de a par b : q s’appelle le quotient et r s’appelle le reste.

pgcd et ppcm
• Le pgcd (plus grand commun diviseur) de a et b, noté a ∧ b ou pgcd(a, b), est le plus grand élément
de {d ∈ N ; d|a et d|b}, avec la convention pgcd(0, 0) = 0.
◦ a ∧ b = b ∧ a = |a| ∧ |b|
(d|a et d|b) ⇐⇒ d|a ∧ b
Si k ∈ Z∗ , alors (ka) ∧ (kb) = |k|(a ∧ b)

◦ Si r est le reste dans la division euclidienne de a par b, alors {diviseurs communs de a et b} =

{diviseurs communs de b et r} ; en particulier, a ∧ b = b ∧ r.
Conséquence : Algorithme d’Euclide pour calculer le pgcd pour a ≥ b ≥ 0.
On pose r0 = a et r1 = b. Pour i ∈ N∗ , si ri 6= 0, on note ri+1 le reste de la division euclidienne de ri−1
par ri . Le dernier reste non nul est le pgcd de a et b.

◦ [Relation de Bézout. ] Il existe (u, v) ∈ Z2 tels que au + bv = a ∧ b.

Attention : Ces coefficients de Bézout ne sont pas uniques : si (u, v) convient, alos (u + kb, v − ka)
convient aussi, pour tout k ∈ Z !
En pratique, on peut déterminer des coefficients de Bézout en ‘remontant’ l’algorithme d’Euclide.

• Le ppcm (plus petit commun multiple) de a et b, noté a ∨ b ou ppcm(a, b), est le plus petit élément
de {m ∈ N ; a|m et b|m}, avec la convention pcm(a, 0) =ppcm(0, a) = 0.
◦ Si k ∈ Z∗ , alors (ka) ∨ (kb) = |k|(a ∨ b)

◦ |ab| = (a ∧ b)(a ∨ b).

-1-
M1 MEEF SD Maths Arithmétique

Nombres premiers entre eux

• a et b sont premiers entre eux si leur pgcd vaut 1, donc si ±1 sont leurs seuls diviseurs communs.

◦ [Théorème de Bézout. ] a ∧ b = 1 ⇐⇒ ∃(u, v) ∈ Z2 ; au + bv = 1.

Remarque : Le sens direct est la relation de Bézout vue plus haut ; le sens indirect est spécifique au
cas a ∧ b = 1 !
Conséquence : Si a ∧ b = 1 et a ∧ c = 1, alors a ∧ bc = 1.

◦ [Théorème de Gauss. ] Soient (a, b, c) ∈ Z3 . Si a|bc et a ∧ b = 1, alors a|c.

Conséquence : Si b|a, c|a et b ∧ c = 1, alors bc|a.

Nombres premiers
• Un entier est premier s’il a exactement 2 diviseurs positifs, qui sont 1 et lui-même.
√
◦ n ≥ 2 n’est pas premier si et seulement s’il admet un diviseur premier inférieur ou égal à n

◦ L’ensemble P des nombres premiers est infini

◦ [Théorème fondamental de l’arithmétique. ] Tout entier n ≥ 2 s’écrit de manière unique comme

n = pα1 1 · · · pαr r
où p1 , · · · , pr sont des nombres premiers et α1 , · · · , αr sont dans N∗ .
• Cette écriture est la décomposition en produit de facteurs premiers de n.

• Soit p ∈ P. La valuation p-adique de n, notée vp (n), est l’exposant de p dans la décomposition de n ;

c’est le plus grand entier k ≥ 0 tel que pk |n. Par définition, vp (n) = 0 si p n’est pas un facteur premier de n.

◦ a divise b si et seulement si vp (a) ≤ vp (b), ∀p ∈ P

◦ Calcul du pgcd : a ∧ b = p∈P pmin(vp (a),vp (b))
Q

◦ Calcul du ppcm : a ∨ b = p∈P pmax(vp (a),vp (b))

Q

Relation de congruence
• Soit n ∈ N. On dit que a et b sont congrus modulo n s’il existe k ∈ Z tel que a − b = kn, autrement
dit, si a et b ont même reste dans la division euclidienne par n. On note a ≡ b [n], ou a ≡n b.

◦ La congruence modulo n définit une relation d’équivalence sur Z, compatible avec les opérations +
et × :  
a ≡ b [n] a + c ≡ b + d [n]
=⇒
c ≡ d [n] a × c ≡ b × d [n]

◦ [Petit théorème de Fermat. ] Si p est un nombre premier et a ∈ Z, alors ap ≡ a [p]. De plus, si p ne

divise pas a, alors ap−1 ≡ 1 [p].

◦ [Théorème des restes chinois. ] Si n, m ≥ 2 sont premiers entre eux alors, pour tout (a, b) ∈ Z2 , le
système

x ≡ a [m]
x ≡ b [n]
admet une solution unique modulo mn.
Remarque : la preuve de l’existence est constructive, donc à connaitre. On sait par la relation de
Bézout qu’il existe (u, v) ∈ Z2 tel que un + vm = 1. Alors x0 = avm + bun est solution.

-2-
M1 MEEF SD Maths Arithmétique

◦ Plus généralement, si n1 , · · · , nm ≥ 2 sont premiers entre eux 2 à 2 alors,Q

pour tout (a1 , · · · , am ) ∈
Zm ,le système de congruences x ≡ ai [ni ] admet une solution unique modulo i ni .

Anneaux (Z/nZ, +, ×)
• Puisque la congruence modulo n définit une relation d’équivalence sur Z, on peut considérer l’en-
semble quotient, que l’on note Z/nZ, dont les éléments sont notés an (la classe de congruence de a) :
 n n n
Z/nZ = 0 , 1 , · · · , n − 1 .

◦ Puisque cette relation est compatible avec les lois internes + et × de l’anneau commutatif Z, ce
quotient hérite d’une structure d’anneau commutatif (Z/nZ, +, ×), avec les lois :
n n n n
an + b = a + b et an × b = a × b .
◦ an est inversible dans Z/nZ si et seulement si k ∧ n = 1
◦ ...donc (Z/nZ, +, ×) est un corps si et seulement si n est premier

◦ [Théorème des restes chinois. ] (reformulation)

Si n, m ≥ 2 sont premiers entre eux, alors l’anneau produit Z/nZ × Z/mZ est isomorphe à Z/nmZ.

Structure additive : le groupe (Z/nZ, +)

n
◦ Le groupe (Z/nZ, +) est cyclique, engendré (additivement !) par 1 .
◦ L’ordre de an (i.e. le plus petit k tel que kn ≡ 0, [n]) est donné par n/(a ∧ n).
Donc Z/nZ est engendré par an si et seulement si a ∧ n = 1.
(donc les générateurs du groupe (Z/nZ, +) sont les éléments inversibles de l’anneau (Z/nZ, +, ×) !)
◦ Tout groupe cyclique G de cardinal fini n est isomorphe à Z/nZ.
De plus, pour tout diviseur d de n, il existe un unique sous-groupe de G cyclique de cardinal d.

Structure multiplicative : le groupe ((Z/nZ)∗ , ×)

• Le groupe des unités d’un anneau (G, +, ×) est le groupe multiplicatif formé par l’ensemble G∗ des
éléments inversibles (pour la loi ×, donc) ; ces éléments sont appelés unités.

◦ L’ensemble (Z/nZ)∗ est formé des a ∈ Z/nZ tels que a ∧ n = 1

Conséquence : les seuls unités de Z/0Z = Z sont ±1
◦ ((Z/nZ)∗ , ×) est un groupe abelien fini (n > 0)

◦ Si n est premier, ((Z/nZ)∗ , ×) est cyclique

-3-