L'ensemble des entiers relatifs muni des lois addition et multiplication est un anneau intègre.
Définition :
Soit .
On dit que divise et on note si et seulement s'il existe tel que : .
Au lieu de divise , on dit aussi : est un diviseur de , ou encore est un multiple de .
Remarques : .
.
Proposition :
.
.
.
.
.
.
.
Remarque : La relation de divisibilité n'est pas une relation d'ordre sur .
Pour , on pose et on a : et .
Théorème - Définition : Division Euclidienne
Soit .
Il existe alors un couple unique tel que : .
On dit que (resp. ) est le quotient (resp. reste ) de la division euclidienne de par .
II. Plus grand commun diviseur (pgcd) - Plus petit commun multiple (ppcm)
1. Généralités
Proposition - Définition :
Soient , .
L'ensemble des diviseurs communs à est fini et admet un plus grand élément (pour l'ordre ) appelé plus grand commun diviseur de noté .
L'ensemble des éléments de multiples communs de admet un plus petit élément (pour l'ordre ) appelé plus petit commun multiple de et noté .
Notation : Pour on note : .
Exemples : 1..
2..
Remarque : :
1. 2.
Proposition
Soient .
et .
.
.
Proposition
.
.
.
2. Algorithme d'Euclide
Proposition
Soit avec , d'après la division euclidienne de par il existe tel que : et .
Dans ce cas, on a : .
L'algorithme : Soit avec tel que .
Construisons un algorithme permettant de calculer .
Si alors : .
Si . Par division enclidienne de par , il existe avec tel que : et . Alors : .
1. Si alors : .
2. Si alors on réitère.
Ainsi, on construit les couples tels que :
Comme et que sont non nuls, le procédé s'arrête au bout d'un nombre fini d'étapes. Il existe donc dans tels que :
On a alors : .
Le de et est le denier reste non nul dans la succession des diviseurs euclidiennes de par .
Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !