Anneau euclidien

Dans ℤ, on peut diviser 252 par 105 : le quotient vaut 2 et il reste 42. Ce reste est plus petit que 105, ce qui autorise une nouvelle division, puis une autre. Un anneau euclidien est un univers de calcul où cette descente reste possible.

Une règle de taille, appelée stathme, mesure la diminution. Comme ses valeurs sont des entiers naturels, les restes ne peuvent pas décroître indéfiniment : le procédé finit par atteindre zéro.

Un anneau euclidien est un anneau commutatif intègre, selon la convention usuelle, muni d'une fonction appelée stathme euclidien. Cette fonction, notée δ, associe un entier naturel à chaque élément non nul de l'anneau. Elle doit assurer une division avec reste strictement décroissant.

Si A désigne l'anneau, si a est le dividende et si b est un diviseur non nul, il existe un quotient q et un reste r qui vérifient :Le cas r = 0 doit être séparé, car le stathme n'est pas nécessairement défini en zéro.

Dans ℤ, la valeur absolue fournit un stathme ; dans l'anneau K[X] des polynômes à coefficients dans un corps K, le degré joue ce rôle pour les polynômes non nuls. Tout anneau euclidien est un anneau principal : chacun de ses idéaux est engendré par un seul élément.

La structure réunit cinq éléments. L'anneau intègre A fournit l'addition et la multiplication sans diviseurs de zéro. Le stathme δ mesure les éléments non nuls par des entiers naturels. Le dividende a et le diviseur non nul b déterminent un quotient q et un reste r. Enfin, l'inégalité portant sur δ(r) garantit la descente.

Le quotient et le reste dépendent de la division choisie, mais au moins un couple convenable doit exister pour chaque a et chaque b non nul. Le stathme relie les divisions successives : le reste devient le diviseur suivant. Dans ℤ, la chaîne issue de 252 et 105 fait décroître les tailles de 105 à 42, puis à 21 et enfin à 0. Ces données suffisent à exécuter l'algorithme d'Euclide et à obtenir un PGCD.

Dans l'anneau ℤ, prenons les deux entiers 252 et 105. Le stathme choisi est la valeur absolue. À chaque étape, le diviseur est non nul et le reste obtenu a une valeur absolue strictement plus petite que celle du diviseur.

1. Divisons 252 par 105.Le reste 42 est bien compris entre 0 et 104.

2. Le diviseur 105 devient le nouveau dividende, et le reste 42 devient le nouveau diviseur.Le nouveau reste 21 est strictement plus petit que 42.

3. Recommençons avec 42 et 21.Le reste nul arrête l'algorithme.

Le dernier reste non nul est 21 : le PGCD de 252 et 105 vaut donc 21. Le contrôle est direct : 252 = 12 × 21 et 105 = 5 × 21.

Pour calculer un PGCD dans ℤ, on enchaîne les divisions jusqu'au reste nul. Face à de grands entiers, ce procédé remplace la recherche de tous les diviseurs : le dernier reste non nul donne le résultat.

Pour simplifier une fraction, le PGCD obtenu révèle le facteur commun maximal du numérateur et du dénominateur. On divise alors les deux termes par ce même nombre.

Dans K[X], on remplace la valeur absolue par le degré et la division entière par la division des polynômes. Cette option exige que les coefficients appartiennent à un corps ; sur un anneau de coefficients plus général, la division par le coefficient dominant peut être impossible.

Anneau euclidien et anneau principal. Dans un anneau principal, tout idéal possède un générateur unique à multiplication par une unité près. Cela ne fournit pas forcément un stathme permettant des divisions décroissantes. Tout anneau euclidien est principal, mais la réciproque est fausse en général.

Division euclidienne et algorithme d'Euclide. Une division produit un quotient et un reste. L'algorithme répète cette opération en remplaçant le couple courant par le diviseur et le reste ; son arrêt au reste nul permet notamment de calculer un PGCD.

Le quotient et le reste ne sont pas nécessairement uniques. La définition exige l'existence d'un couple qui fait décroître le stathme. Elle n'impose l'unicité que lorsqu'une convention supplémentaire, comme 0 ≤ r < |b| dans ℤ, la garantit.

Le stathme n'est pas une norme canonique. Un même anneau peut admettre plusieurs fonctions euclidiennes. Il faut vérifier la propriété de division, pas seulement constater que la fonction prend des valeurs entières.

L'anneau de polynômes dépend des coefficients. K[X] est euclidien lorsque K est un corps, avec le degré comme stathme. Cette affirmation ne s'étend pas automatiquement à A[X] pour un anneau A quelconque, ni à K[X,Y], qui n'est pas principal.

L'intégrité est indispensable. Un anneau comportant des diviseurs de zéro, comme ℤ/6ℤ puisque 2 × 3 = 0, n'est pas un anneau euclidien au sens retenu ici. Il faut d'abord contrôler le cadre algébrique avant de chercher un stathme.

La division euclidienne détaille l'opération élémentaire qui produit quotient et reste.

Le stathme euclidien précise la mesure qui force les restes successifs à décroître.

L'algorithme d'Euclide montre comment répéter les divisions pour atteindre le PGCD.

L'anneau des entiers de Gauss fournit un exemple où le stathme vient d'une norme dans le plan complexe.