Résumé de cours et méthodes : Arithmétique
Chniti Chokri
February 23, 2021
1 Division euclidienne
Soient a et b deux entiers relatifs. On dit que a divise b, ou que a est un diviseur de b s’il existe
k ∈ Z tel que b = ka. On dit encore que b est un multiple de a.
Théorème 1 Théorème (division euclidienne) : Soient (a, b) ∈ Z2 avec b 6= 0. Il existe un unique
couple (q, r) ∈ Z2 tels que
a = bq + r
0 ≤ r < |b|.
q s’appelle le quotient et r s’appelle le reste.
2 pgcd,ppcm
Si a et b sont deux entiers relatifs dont l’un au moins est non-nul, alors le pgcd de a et b, noté
a ∧ b, est le plus grand diviseur commun de a et b. Cette définition se généralise à plus de deux
entiers, en supposant toujours qu’au moins un est non-nul.
Si a = b = 0, on pose a ∧ b = 0.
On a (d|a et d|b) ⇐⇒ d|a ∧ b.
Si a, b, k ∈ (Z\{0})3 , alors (ka) ∧ (kb) = |k|(a ∧ b).
Algorithme d’Euclide : Si r est le reste dans la division euclidienne de a par b, alors on a
a ∧ b = b ∧ r.
On en déduit l’algorithme suivant pour calculer le pgcd pour a ≥ b ≥ 0. On pose r0 = aetr1 = 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.
Si a et b sont deux entiers relatifs, le ppcm de a et b, noté a ∨ b, est le plus petit multiple commun
positif de a et b.
Proposition 1 : Pour tout couple d’entiers relatifs (a, b), on a
|ab| = (a ∧ b)(a ∨ b).
1
5 CONGRUENCES
3 Nombres premiers entre eux
On dit que deux entiers relatifs sont premiers entre eux si leur pgcd vaut 1.
Théorème 2 Théorème de Bézout : Soient (a, b) ∈ Z2 . On a
a ∧ b = 1 ⇐⇒ ∃(u, v) ∈ Z2 , au + bv = 1.
Théorème 3 Théorème de Gauss : Soient (a, b, c) ∈ Z3 . On suppose que a|bc et a ∧ b = 1, alors
a|c.
Conséquence : Si b|a, c|a et b ∧ c = 1, alors bc|a.
4 Nombres premiers
Un entier p ≥ 2 est dit premier si ses seuls diviseurs positifs sont 1 et p.
L’ensemble des nombres premiers est infini.
Théorème 4 Théorème fondamental de l’arithmétique : Tout entier n ≥ 2 s’écrit de manière
unique n = pα1 1 · · · pαr r où p1 < p2 < · · · < pr sont des nombres premiers et α1 , . . . , αk sont dans
N∗ . On dit que n = pα1 1 · · · pαr r est la décomposition en produit de facteurs premiers de n.
Si n ≥ 2 et p est un nombre premier, on appelle valuation p-adique de n, et on note vp (n), le
plus grand entier k ≥ 0 tel que pk |n. La valuation p-adique de n est l’exposant de p dans la
décomposition en produit de facteurs premiers de n.
Application au calcul du pgcd et du ppcm : si a, b ≥ 2 se décomposent sous la forme
a = pα1 1 · · · pαr r
b = pβ1 1 · · · pβr r
où les pi sont des nombres premiers et αi , βi ∈ N, alors
min(α1 ,β1 )
a ∧ b = p1 · · · pmin(α
r
r ,βr )
max(α1 ,β1 )
a ∨ b = p1 · · · pmax(α
r
r ,βr )
.
5 Congruences
Soient a et b deux entiers relatifs et n un entier naturel. On dit que a et b sont congrus modulo
n s’il existe k ∈ Z tel que a − b = kn. On note
a ≡ b [n].
La relation ”être congrue modulo n”, qui est une relation d’équivalence, est compatible avec les
opérations +, × :
a ≡ b [n] a + c ≡ b + d [n]
=⇒
c ≡ d [n] a × c ≡ b × d [n]
Théorème 5 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].
Chniti 2
6 MÉTHODES
6 Méthodes
6.1 Calculer le reste an dans la division par k
– on commence par rechercher un entier m ≥ 1 tel que am ≡ 1 [k] (on pourra calculer les
puissances successives, ou utiliser le petit théorème de Fermat).
– si n ≡ r [m], alors n = qm + r et an ≡ (am )q ar [m] ≡ ar [r].
– il reste à calculer le reste de ar dans la division par k.
6.2 Calculer le pgcd de deux entiers a et b
– On peut utiliser l’algorithme d’Euclide .
– On peut utiliser la décomposition en facteurs premiers des entiers concernés.
– On peut utiliser la définition.
6.3 Résoudre une équation de Bézout ax + by = c
– On commence par calculer d = a ∧ b.
– Si d ne divise pas c, alors puisque d|ax + by, l’équation ne peut pas avoir de solutions. Sinon,
on peut tout diviser par d. Cela revient à supposer que a et b sont premiers entre eux, ce
que nous supposerons désormais.
– On cherche un couple d’entiers (u, v) tel que au + bv = 1. On sait qu’un tel couple existe par
le théorème de Bézout, et on le détermine par l’algorithme d’Euclide étendu.
– On pose x0 = cu et y0 = cv. Alors (x0 , y0 ) est une solution particulière de ax+by=c.
– Soit (x, y) une solution. Alors on retranche ax0 + by0 = c à ax + by = c, et on trouve
a(x − x0 ) = −b(y − y0 ).
– Puisque a ∧ b = 1, ceci entraı̂ne a|y − y0 et donc y = y0 + ak, k ∈ Z. On reporte alors ceci
dans l’équation a(x − x0 ) = −b(y − y0) pour exprimer x en fonction de x0 et k.
– Réciproquement, on doit trouver que les solutions trouvées conviennent.
Chniti 3
