Division euclidienne


Ressources mathématiques > Capes > Fiches de révision pour l'écrit >
Accéder à mon compte > Accéder à ma feuille d'exercices >


Arithmétique des entiers
Division euclidienne
Soient aa et bb deux entiers relatifs. On dit que aa divise bb, ou que a est un diviseur de bb
s'il existe k ∈ ℤ k ∈ Z tel que b = kab = ka. On dit encore que bb est un multiple de aa.

Théorème (division euclidienne) : Soient (a, b) ∈ ℤ2 (a, b) ∈ Z 2 avec b ≠ 0 b ≠ 0. Il
existe un unique couple (q, r) ∈ ℤ2 (q, r) ∈ Z 2 tels que


{ 0 ≤ r < |b|.
a = bq + r



{ a = bq + r
0 ≤ r < |b|.

qq s'appelle le quotient et r r s'appelle le reste.
Démonstration (vidéo)



pgcd,ppcm
Si aa et bb sont deux entiers relatifs dont l'un au moins est non-nul, alors le pgcd de aa et bb
, noté a ∧ ba ∧ b, est le plus grand diviseur commun de aa et bb. 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 a = b = 0, on pose a ∧ b = 0 a ∧ b = 0.
On a (d|a et d|b) ⟺ d|a ∧ b (d | a et d | b) ⟺ d | a ∧ b.
Si a, b, k ∈ (ℤ∖{0})3 a, b, k ∈ (Z∖{0}) 3, alors (ka) ∧ (kb) = |k|(a ∧ b) (ka) ∧ (kb) = | k | (a ∧ b).
Algorithme d'Euclide : Si r r est le reste dans la division euclidienne de aa par bb, alors on a

a ∧ b = b ∧ r.
a ∧ b = b ∧ r.

On en déduit l'algorithme suivant pour calculer le pgcd pour a ≥ b ≥ 0 a ≥ b ≥ 0. On pose
r 0 = a r 0 = a et r 1 = b r 1 = b. Pour i ∈ ℕ ∗ i ∈ N ∗ , si r i ≠ 0r i ≠ 0, on note r i+1 r i + 1 le reste
de la division euclidienne de r i−1 r i − 1 par r i r i. Le dernier reste non nul est le pgcd de aa et b
b.
Si aa et bb sont deux entiers relatifs, le ppcm de aa et bb, noté a ∨ ba ∨ b, est le plus petit
multiple commun positif de aa et bb.

Proposition : Pour tout couple d'entiers relatifs (a, b) (a, b), on a

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


Nombres premiers entre eux
On dit que deux entiers relatifs sont premiers entre eux si leur pgcd vaut 1.

Théorème de Bézout : Soient (a, b) ∈ ℤ2 (a, b) ∈ Z 2. On a

a ∧ b = 1 ⟺ ∃(u, v) ∈ ℤ2 , au + bv = 1.

a ∧ b = 1 ⟺ ∃(u, v) ∈ Z 2, au + bv = 1.

Démonstration (vidéo)



Théorème de Gauss : Soient (a, b, c) ∈ ℤ3 (a, b, c) ∈ Z 3. On suppose que a|bca | bc et
a ∧ b = 1 a ∧ b = 1, alors a|c a | c.
Démonstration (vidéo)


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

Nombres premiers
Un entier p ≥ 2 p ≥ 2 est dit premier si ses seuls diviseurs positifs sont 11 et pp.
L'ensemble des nombres premiers est infini.
Démonstration (vidéo)


Théorème fondamental de l'arithmétique : Tout entier n ≥ 2 n ≥ 2 s'écrit de manière
α α
unique n = p1 1 ⋯ pr r n = p α1 1⋯p αr r où p1 < p2 < ⋯ < pr p 1 < p 2 < ⋯ < p r sont des
α α
nombres premiers et α 1 , … , α k α 1, …, α k sont dans ℕ ∗ N ∗ . On dit que n = p1 1 ⋯ pr r
n = p α1 1⋯p αr r est la décomposition en produit de facteurs premiers de nn.
Démonstration (vidéo)


Si n ≥ 2 n ≥ 2 et pp est un nombre premier, on appelle valuation pp-adique de nn, et on note
v p (n) v p(n), le plus grand entier k ≥ 0 k ≥ 0 tel que pk |np k | n. La valuation pp-adique de nn
est l'exposant de pp dans la décomposition en produit de facteurs premiers de nn.
Application au calcul du pgcd et du ppcm : si a, b ≥ 2 a, b ≥ 2 se décomposent sous la forme

a = p1α1 ⋯ pαr r

a = p 1α 1⋯p rα r

β β
b = p 11 ⋯ p r r

b = p 1β 1⋯p rβ r

où les pi p i sont des nombres premiers et α i , βi ∈ ℕ α i, β i ∈ N, alors
 min(α1,β1 ) min(αr ,βr )
a ∧ b = p1 ⋯ pr
max(α1,β1 ) max(αr ,βr )
a ∨ b = p1 ⋯ pr .

a ∧ b = p 1min ( α 1 , β 1 ) ⋯p rmin ( α r , β r )

a ∨ b = p 1max ( α 1 , β 1 ) ⋯p rmax ( α r , β r ) .

Congruences
Soient aa et bb deux entiers relatifs et nn un entier naturel. On dit que aa et bb sont congrus
modulo n s'il existe k ∈ ℤ k ∈ Z tel que a − b = kn a − b = kn. On note

a ≡ b [n].
a ≡ b [n].

La relation "être congrue modulo nn", qui est une relation d'équivalence, est compatible avec
les opérations +, ×+ , × :


{ c ≡ d [n] { a × c ≡ b × d [n]
a ≡ b [n] a + c ≡ b + d [n]
⟹



{ a ≡ b [n]
c ≡ d [n]
⟹
{ a + c ≡ b + d [n]
a × c ≡ b × d [n]

Petit théorème de Fermat : Si pp est un nombre premier et a ∈ ℤ a ∈ Z, alors
ap ≡ a [p]a p ≡ a [p]. De plus, si pp ne divise pas aa, alors ap−1 ≡ 1 [p]a p − 1 ≡ 1 [p].
Démonstration (vidéo)



Arithmétique et sous-groupes de ℤ Z

Théorème : Les sous-groupes de ℤZ sont les nℤ nZ, avec n ∈ ℕn ∈ N.
Démonstration (vidéo)



Théorème : Soit a, ba, b deux entiers tels que (a, b) ≠ (0, 0) (a, b) ≠ (0, 0). Alors
aℤ + bℤaZ + bZ et aℤ ∩ bℤ aZ ∩ bZ sont deux sous-groupes de ℤZ. Soit d, m ∈ ℕ
d, m ∈ N tels que

aℤ + bℤ = dℤ
aℤ ∩ bℤ = mℤ.
aZ + bZ = dZ
aZ ∩ bZ = mZ.

Alors d = a ∧ bd = a ∧ b et m = a ∨ b m = a ∨ b.

Le théorème précédent contient en particulier la moitié du théorème de Bézout : si
a ∧ b = 1 a ∧ b = 1, alors aℤ + bℤ = ℤaZ + bZ = Z, et donc il existe (u, v) ∈ ℤ2 (u, v) ∈ Z 2
avec au + bv = 1au + bv = 1.
Anneaux ℤ/nℤ Z / nZ

Théorème : Les idéaux de ℤZ sont les ensembles nℤ nZ pour n ∈ ℕn ∈ N.

Soit n ≥ 2 n ≥ 2. La relation de congruence modulo nn est une relation d'équivalence sur ℤZ :
a ≡ b [n] ⟺ a − b ∈ nℤ a ≡ b [n] ⟺ a − b ∈ nZ. On note a¯ a¯ la classe d'équivalence de
aa, et ℤ/nℤ Z / nZ l'ensemble des classes d'équivalence pour cette relation. On a en particulier
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ ¯
¯ ¯
ℤ/nℤ = {0, 1, … , n − 1 }. Z / nZ = {0,
¯ 1,
¯ …, n − 1}.

Théorème : On munit ℤ/nℤ Z / nZ d'une structure d'anneaux en posant
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
a¯ + b¯ = a + b
¯
a¯ + b¯ = a + b
⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯
a¯ × b¯ = a × b .
¯
a¯ × b¯ = a × b.


Théorème : k¯ k¯ est inversible dans ℤ/nℤ Z / nZ si et seulement k ∧ n = 1 k ∧ n = 1.

Corollaire : (ℤ/nℤ, +, ×) (Z / nZ, + , × ) est un corps si et seulement si nn est premier.

Théorème chinois : Si n, m ≥ 2n, m ≥ 2 sont premiers entre eux, alors l'anneau produit
ℤ/nℤ × ℤ/mℤ Z / nZ × Z / mZ est isomorphe à l'anneau ℤ/nmℤ Z / nmZ.
Le théorème des restes chinois peut encore se reformuler de la façon suivante en termes de
congruences :

Théorème des restes chinois : Soit mm et nn des entiers premiers entre eux. Alors,
pour tout (a, b) ∈ ℤ2 (a, b) ∈ Z 2, le système


{x
x ≡ a [m]
≡ b [n]


{ x
x
≡
...