142 PGCD et PPCM, algorithmes de calcul. Applications.

PGCD et PPCM, algorithmes de calcul. Applications.

algebra

Notion de PGCM/PPCM dans un anneau

Soit un anneau commutatif unitaire.

Définition 1. Soient .

  • On dit que divise (ou que est un multiple de ), noté s’il existe tel que .

  • On dit que et sont associés, noté si et si .

Remarque 2. Soient .

  • .

  • . Ainsi, est une relation d’équivalence sur .

Proposition 3. Soient . Alors,

Définition 4. Soient .

  • est un plus grand commun diviseur PGCD de si satisfait les deux propriétés suivantes :

    1. .

    2. Si tel que , alors .

  • est un plus petit commun multiple PPCM de si satisfait les deux propriétés suivantes :

    1. .

    2. Si tel que , alors .

Remarque 5. Un PGCD (resp. un PPCM), lorsqu’il existe, n’est pas toujours unique. Dans un anneau intègre, deux PGCD (resp. PPCM) sont toujours associés puisqu’ils se divisent l’un l’autre. Dans un anneau intègre, on peut donc noter (resp. ) lorsque est un pgcd (resp. est un ppcm) de et de .

Exemple 6. Soient un corps commutatif. On pose pour . Alors, pour , le PGCD unitaire de et est égal à .

Proposition 7. Soient . Un élément est un PPCM de et si et seulement si . En particulier, et admettent un PPCM si et seulement si est un idéal principal.

Proposition 8. Soient . Soit . Les assertions suivantes sont équivalentes.

  1. , et il existe tels que .

  2. et il existe tels que .

  3. .

Définition 9. Deux éléments et de sont dits premiers entre eux s’ils admettent un PGCD et .

Exemple 10. et sont premiers entre eux dans .

Dans un anneau principal

Dans cette section, désigne toujours un anneau commutatif unitaire. On le suppose de plus principal.

Existence

Théorème 11 (Décomposition de Bézout). Soient . Alors :

  1. Il existe un de . est tel que . En particulier, est de la forme avec .

  2. Il existe un de . est tel que .

Exemple 12. Dans :

Application 13. est inversible dans d’inverse .

Lemme 14 (Gauss). Soient avec et premiers entre eux. Alors, et

Dans les anneaux euclidiens

Principalité des anneaux euclidiens

Proposition 15. Un anneau euclidien est principal.

On a donc existence de PGCD et de PPCM dans un tel anneau, mais la structure euclidienne permet de plus de fournir des algorithmes de calculs.

Théorème 16. Si est un corps commutatif, alors est un anneau euclidien de stathme le degré. De plus, le quotient et le reste sont uniques.

Corollaire 17. Les assertions suivantes sont équivalentes :

  1. est un corps commutatif.

  2. est un anneau euclidien.

  3. est un anneau principal.

Algorithmes de calcul

Lemme 18. On suppose euclidien de stathme . Soient et un reste dans la division euclidienne de par . À inversible près, on a alors :

  • Si : .

  • Sinon : .

Théorème 19 (Algorithme d’Euclide). On suppose euclidien de stathme . Soient tels que . On définit une suite décroissante (au sens du stathme) par :

  • ;

  • est un reste dans la division euclidienne de par , on a donc ou ;

  • pour , si , alors , sinon est un reste dans la division euclidienne de par et on a ou .

est alors le dernier reste non nul dans cette suite de divisions euclidiennes, que l’on note .

Remarque 20. On peut remonter l’algorithme d’Euclide pour obtenir les coefficients de Bézout. On parle alors d’algorithme d’Euclide étendu.

Au lieu de faire les calculs en deux temps (descente, puis remontée), on peut tout faire en même temps via l’algorithme suivant.

Proposition 21 (Algorithme d’Euclide généralisé). En reprenant les notations du Théorème 19 :

  • Étape 0 : On écrit avec .

  • Étape 1 : On écrit avec .

  • Étape 2 : On écrit avec .

  • Étape : On écrit .

  • Étape : On écrit .

  • Étape : On écrit .

À la fin, on obtient .

Exemple 22. Calculons le PGCD et les coefficients de Bézout de et dans .

= +
= +
Il y va fois reste = +
fois reste = +
fois reste = +
fois reste = +

On a .

Proposition 23. En reprenant les notations précédentes, on a

Corollaire 24. En reprenant les notations précédentes, cet algorithme a une complexité en .

Dans un anneau factoriel

Proposition 25. Si vérifie la relation de la Proposition 26, alors les assertions suivantes sont équivalentes :

  1. vérifie le lemme d’Euclide : si est irréductible, alors .

  2. Pour tout , est irréductible si et seulement si premier.

  3. vérifie le lemme de Gauss : si est irréductible, alors pour tout avec et premiers entre eux.

Proposition 26. On suppose factoriel. Tout élément peut s’écrire de manière unique est un système de représentants d’éléments premiers de (pour le relation ), est inversible et tous nuls sauf un nombre fini.

Exemple 27. Dans l’anneau principal (donc factoriel, voir Théorème 29) , un choix standard pour est l’ensemble des nombres premiers positifs.

Proposition 28. On suppose factoriel. Soient . Alors, en reprenant les notations précédentes :

  1. pour tout .

  2. est un PGCD de et de .

  3. est un PPCM de et de .

Théorème 29. Tout anneau principal est factoriel.

Contre-exemple 30. est principal mais n’est pas factoriel.

Lemme 31 (Gauss). On suppose factoriel. Alors :

  1. Le produit de deux polynômes primitifs est primitif (ie. dont le PGCD des coefficients est associé à ).

  2. , (où est le contenu du polynôme ).

Théorème 32 (Critère d’Eisenstein). Soient le corps des fractions de et de degré . On suppose que est factoriel et qu’il existe irréductible tel que :

  1. , .

  2. .

  3. .

Alors est irréductible dans .

Application 33. Soit . Il existe des polynômes irréductibles de degré sur .

Applications

En algèbre linéaire

Soit un espace vectoriel de dimension finie sur un corps . Soit un endomorphisme de .

Proposition 34. Il existe un unique polynôme de unitaire qui engendre l’idéal : c’est le polynôme minimal de , noté . Il s’agit du polynôme unitaire de plus bas degré annulant . Il divise tous les autres polynômes annulateurs de .

Théorème 35 (Lemme des noyaux). Soit où les polynômes sont premiers entre eux deux à deux. Alors,

Application 36. est diagonalisable si et seulement si est scindé à racines simples.

Systèmes de congruences

Proposition 37. Soit un entier non nul. L’équation admet des solutions si et seulement si .

Corollaire 38. Soient un entier non nul et un entier relatif. L’équation a des solutions si et seulement si . Dans ce cas, l’ensemble des solutions est est une solution de l’équation .

Théorème 39 (Chinois). Soient des entiers. On note et la surjection canonique de sur pour tout .

Les entiers sont premiers entre eux si et seulement si les anneaux et sont isomorphes. Dans ce cas, l’isomorphisme est explicité par l’application

Exemple 40. admet pour ensemble de solutions .

Entiers sommes de deux carrés

Notation 41. On note et l’ensemble des entiers qui sont somme de deux carrés.

Remarque 42. .

Théorème 43 (Deux carrés de Fermat). Soit . Alors si et seulement si est pair pour tout premier tel que (où désigne la valuation -adique de ).