Leçon 142 : PGCD et PPCM, algorithmes de calcul. Applications.

(2023) 142
(2025) 142

Dernier rapport du Jury :

(2024 : 142 - PGCD et PPCM, algorithmes de calcul. Applications.) Le candidat doit prendre soin de différencier le cadre théorique des anneaux factoriels ou principaux dans lequel sont définis les PGCD et PPCM et dans lequel s'appliquent les énoncés des théorèmes proposés et le cadre euclidien fournissant les algorithmes. Le champ d'étude de cette leçon ne peut se limiter au cas de Z, mais la leçon peut opportunément s'illustrer d'exemples élémentaires d'anneaux euclidiens, comme Z et $K[X]$. Une part substantielle de la leçon doit être consacrée à la présentation d'algorithmes : algorithme d'Euclide, algorithme binaire, algorithme d'Euclide étendu. Il est possible d'en évaluer le nombre d'étapes dans les pires cas et faire le lien avec les suites de Fibonacci. Des applications élémentaires sont particulièrement bienvenues : calcul de relations de Bezout, ré- solutions d'équations diophantiennes linéaires, inversion modulo un entier ou un polynôme, calculs d'inverses dans les corps de rupture, les corps finis. On peut aussi évoquer le théorème chinois effectif, la résolution d'un système de congruences et faire le lien avec l'interpolation de Lagrange. Pour aller plus loin, on peut évoquer le rôle de algorithme d'Euclide étendu dans de nombreux al- gorithmes classiques en arithmétique (factorisation d'entiers, de polynômes, etc). Décrire l'approche matricielle de l'algorithme d'Euclide et l'action de $SL_2(Z)$ sur $Z^2$ est tout à fait pertinent. On peut aussi établir l'existence d'un supplémentaire d'une droite dans $Z^2$, ou d'un hyperplan de $Z^n$, examiner l'éventuelle possibilité de compléter un vecteur de $Z^n$ en une base. On peut aussi étudier les matrices à coefficients dans un anneau principal ou euclidien, et, de manière plus avancée, la forme normale d'Hermite et son application à la résolution d'un système d'équations diophantiennes linéaires. De même, aborder la forme normale de Smith, et son application au théorème de la base adaptée, permet de faire le lien avec la réduction des endomorphismes via le théorème des invariants de similitude. La leçon invite aussi, pour des candidates et candidats maîtrisant ces notions, à décrire le calcul de PGCD dans $Z[X]$ et $K[X,Y]$, avec des applications à l'élimination de variables. On peut rappeler les relations entre PGCD et résultant et montrer comment obtenir le PGCD en échelonnant la matrice de Sylvester. Sur l'approximation diophantienne, on peut enfin envisager le développement d'un rationnel en fraction continue et l'obtention d'une approximation de Padé-Hermite à l'aide de l'algorithme d'Euclide, la recherche d'une relation de récurrence linéaire dans une suite ou le décodage des codes BCH.

(2022 : 142 - PGCD et PPCM, algorithmes de calcul. Applications.) Le champ d'étude de cette leçon ne peut se limiter au cas de Z ; il s'agit de définir et manipuler les notions de PGCD et PPCM dans un anneau factoriel et comme générateurs de sommes/intersections d'idéaux dans un anneau principal. Le candidat doit prendre soin de différencier le cadre théorique des anneaux factoriels ou principaux dans lequel sont définis les objets et dans lequel s'appliquent les énoncés des théorèmes proposés et le cadre euclidien fournissant les algorithmes. Bien sûr, la leçon peut opportunément s'illustrer d'exemples élémentaires d'anneaux euclidiens, comme Z et $K[x]$. Une part substantielle de la leçon doit être consacrée à la présentation d'algorithmes : algorithme d'Euclide, algorithme binaire, algorithme d'Euclide étendu. Dans le cas des polynômes, il faut étudier l'évolution de la suite des degrés et des restes. On peut évaluer le nombre d'étapes de ces algorithmes dans les pires cas et faire le lien avec les suites de Fibonacci. Des applications élémentaires sont particulièrement bienvenues : calcul de relations de Bezout, ré- solutions d'équations diophantiennes linéaires, inversion modulo un entier ou un polynôme, calculs d'inverses dans les corps de ruptures, les corps finis. On peut aussi évoquer le théorème chinois effectif, la résolution d'un système de congruences et faire le lien avec l'interpolation de Lagrange. Pour aller plus loin, on peut évoquer le rôle de algorithme d'Euclide étendu dans de nombreux algorithmes classiques en arithmétique (factorisation d'entiers, de polynômes, etc). Décrire l'approche matricielle de l'algorithme d'Euclide et l'action de $SL_2(Z)$ sur $Z^2$ est tout à fait pertinent. On peut aussi établir l'existence d'un supplémentaire d'une droite dans $Z^2$, ou d'un hyperplan de Zn, la possibilité de compléter un vecteur de Zn en une base. La leçon peut amener à étudier les matrices à coefficients dans un anneau principal ou euclidien, et, de manière plus avancée, la forme normale d'Hermite et son application à la résolution d'un système d'équations diophantiennes linéaires. De même, aborder la forme normale de Smith, et son application au théorème de la base adaptée, permet de faire le lien avec la réduction des endomorphismes via le théorème des invariants de similitude. La leçon invite aussi, pour des candidats familiers de ces notions, à décrire le calcul de PGCD dans $Z[X]$ et $K[X,Y]$s, avec des applications à l'élimination de variables. On peut rappeler les relations entre PGCD et résultant et montrer comment obtenir le PGCD en échelonnant la matrice de Sylvester. Sur l'approximation diophantienne, on peut enfin envisager le développement d'un rationnel en fraction continue et l'obtention d'une approximation de Padé-Hermite à l'aide de l'algorithme d'Euclide, la recherche d'une relation de récurrence linéaire dans une suite ou le décodage des codes BCH.
(2020 : 142 - PGCD et PPCM, algorithmes de calcul. Applications.) Le champ d’étude de cette leçon ne peut se limiter au cas de Z ; il s’agit de définir et manipuler les notions de PGCD et PPCM dans un anneau factoriel et comme générateurs de sommes/intersections d’idéaux dans un anneau principal. Le candidat doit prendre soin de différencier le cadre théorique des anneaux factoriels ou principaux dans lequel sont définis les objets et dans lequel s’appliquent les énoncés des théorèmes proposés et le cadre euclidien fournissant les algorithmes. Bien sûr, la leçon peut opportunément s’illustrer d’exemples élémentaires d’anneaux euclidiens, comme Z et K[X]. $$$$ Une part substantielle de la leçon doit être consacrée à la présentation d’algorithmes : algorithme d’Euclide, algorithme binaire, algorithme d’Euclide étendu. Dans le cas des polynômes, il faut étudier l’évolution de la suite des degrés et des restes. Il est important de savoir évaluer le nombre d’étapes de ces algorithmes dans les pires cas et on peut faire le lien avec les suites de Fibonacci. $$$$ Des applications élémentaires sont particulièrement bienvenues : calcul de relations de Bezout, résolutions d’équations diophantiennes linéaires, inversion modulo un entier ou un polynôme, calculs d’inverses dans les corps de ruptures, les corps finis. On peut aussi évoquer le théorème chinois effectif, la résolution d’un système de congruences et faire le lien avec l’interpolation de Lagrange. $$$$ Pour aller plus loin, on peut évoquer le rôle de l’algorithme d’Euclide étendu dans de nombreux algorithmes classiques en arithmétique (factorisation d’entiers, de polynômes, etc). Décrire l’approche matricielle de l’algorithme d’Euclide et l’action de $SL_2(Z)$ sur $Z^2$ est tout à fait pertinent. On peut aussi établir l’existence d’un supplémentaire d’une droite dans $Z^2$ , ou d’un hyperplan de $Z^n$ , la possibilité de compléter un vecteur de Z n en une base. $$$$ La leçon peut amener à étudier les matrices à coefficients dans un anneau principal ou euclidien, et, de manière plus avancée, la forme normale d’Hermite et son application à la résolution d’un système d’équations diophantiennes linéaires. De même, aborder la forme normale de Smith, et son application au théorème de la base adaptée, permet de faire le lien avec la réduction des endomorphismes via le théorème des invariants de similitude. La leçon invite aussi, pour des candidats familiers de ces notions, à décrire le calcul de PGCD dans Z[X] et $K[X,Y]$, avec des applications à l’élimination de variables. On peut rappeler les relations entre PGCD et résultant et montrer comment obtenir le PGCD en échelonnant la matrice de Sylvester. Sur l’approximation diophantienne, on peut enfin envisager le développement d’un rationnel en fraction continue et l’obtention d’une approximation de Padé-Hermite à l’aide de l’algorithme d’Euclide, la recherche d’une relation de récurrence linéaire dans une suite ou le décodage des codes BCH.
(2019 : 142 - PGCD et PPCM, algorithmes de calcul. Applications.) Le champ d’étude de cette leçon ne peut se limiter au cas de $\textbf{Z}$ ; il s’agit de définir et manipuler les notions de PGCD et PPCM dans un anneau factoriel et comme générateurs de sommes/intersections d’idéaux dans un anneau principal. Le candidat doit prendre soin de différencier le cadre théorique des anneaux factoriels ou principaux dans lequel sont définis les objets et dans lequel s’appliquent les énoncés des théorèmes proposés et le cadre euclidien fournissant les algorithmes. Bien sûr, la leçon peut opportunément s’illustrer d’exemples élémentaires d’anneaux euclidiens, comme $\textbf{Z}$ et $\textbf{K}[X]$. Une part substantielle de la leçon doit être consacrée à la présentation d’algorithmes : algorithme d’Euclide, algorithme binaire, algorithme d’Euclide étendu. Dans le cas des polynômes, il faut étudier l’évolution de la suite des degrés et des restes. Il est important de savoir évaluer le nombre d’étapes de ces algorithmes dans les pires cas et on peut faire le lien avec les suites de Fibonacci. Des applications élémentaires sont particulièrement bienvenues : calcul de relations de Bezout, résolutions d’équations diophantiennes linéaires, inversion modulo un entier ou un polynôme, calculs d’inverses dans les corps de ruptures, les corps finis. On peut aussi évoquer le théorème chinois effectif, la résolution d’un système de congruences et faire le lien avec l’interpolation de Lagrange. Pour aller plus loin, on peut évoquer le rôle de algorithme d’Euclide étendu dans de nombreux algorithmes classiques en arithmétique (factorisation d’entiers, de polynômes, etc). Décrire l’approche matricielle de l’algorithme d’Euclide et l’action de $SL_2(\textbf{Z})$ sur $\textbf{Z}^2$ est tout à fait pertinent. On peut aussi établir l’existence d’un supplémentaire d’une droite dans $\textbf{Z}^2$, ou d’un hyperplan de $\textbf{Z}^n$, la possibilité de compléter un vecteur de $\textbf{Z}^n$ en une base. La leçon peut amener à étudier les matrices à coefficients dans un anneau principal ou euclidien, et, de manière plus avancée, la forme normale d’Hermite et son application à la résolution d’un système d’équations diophantiennes linéaires. De même, aborder la forme normale de Smith, et son application au théorème de la base adaptée, permet de faire le lien avec la réduction des endomorphismes via le théorème des invariants de similitude. La leçon invite aussi, pour des candidats familiers de ces notions, à décrire le calcul de PGCD dans $\textbf{Z}[X]$ et $\textbf{K}[X,Y]$, avec des applications à l’élimination de variables. On peut rappeler les relations entre PGCD et résultant et montrer comment obtenir le PGCD en échelonnant la matrice de Sylvester. Sur l’approximation diophantienne, on peut enfin envisager le développement d’un rationnel en fraction continue et l’obtention d’une approximation de Padé-Hermite à l’aide de l’algorithme d’Euclide, la recherche d’une relation de récurrence linéaire dans une suite ou le décodage des codes BCH.
(2018 : 142 - PGCD et PPCM, algorithmes de calcul. Applications.) Il est bien clair que le champ d’étude ne peut se limiter au cas de Z; il s’agit de définir et manipuler les notions de PGCD et PPCM dans un anneau factoriel et comme générateurs de sommes/intersections d’idéaux dans un anneau principal. Le candidat devra prendre soin de différencier le cadre théorique des anneaux factoriels ou principaux dans lequel sont définis les objets et dans lequel s’appliquent les énoncés des théorèmes proposés et le cadre euclidien fournissant les algorithmes. Bien sûr, la leçon peut opportunément s’illustrer d’exemples élémentaires d’anneaux euclidiens, comme $Z$ et $K[X]$. La leçon doit accorder une part substantielle à la présentation d’algorithmes : algorithme d’Euclide, algorithme binaire, algorithme d’Euclide étendu. Dans le cas des polynômes, on étudiera l’évolution de la suite des degrés et des restes. Il est important de savoir évaluer le nombre d’étapes de ces algorithmes dans les pires cas et on pourra faire le lien avec les suites de Fibonacci. La leçon abordera des applications élémentaires : calcul de relations de Bézout, résolutions d’équations diophantiennes linéaires, inversion modulo un entier ou un polynôme, calculs d’inverses dans les corps de ruptures, les corps finis. On peut aussi évoquer le théorème chinois effectif, la résolution d’un système de congruences et faire le lien avec l’interpolation de Lagrange. Pour aller plus loin, on pourra évoquer le rôle de algorithme d’Euclide étendu dans de nombreux algorithmes classique en arithmétique (factorisation d’entiers, de polynômes, etc). Décrire l’approche matricielle de l’algorithme d’Euclide et l’action de $SL_2(Z)$ sur $Z^2$ est tout à fait pertinent. On pourra établir l’existence d’un supplémentaire d’une droite dans $Z^2$, ou d’un hyperplan de $Z^n$, la possibilité de compléter un vecteur de $Z^n$ en une base. La leçon peut amener à étudier les matrices à coefficients dans un anneau principal ou euclidien, la forme normale d’Hermite et son application à la résolution d’un système d’équations diophantiennes linéaires. Aborder la forme normale de Smith, et son application au théorème de la base adaptée, permet de faire le lien avec la réduction des endomorphismes via le théorème des invariants de similitude. La leçon invite aussi, pour des candidats familiers de ces notions, à décrire le calcul de PGCD dans $Z[X]$ et $K[X,Y]$, avec des applications à l’élimination de variables. On pourra rappeler les relations entre PGCD et résultant et montrer comment obtenir le PGCD en échelonnant la matrice de Sylvester. Sur l’approximation diophantienne, on peut enfin envisager le développement d’un rationnel en fraction continue et l’obtention d’une approximation de Padé-Hermite à l’aide de l’algorithme d’Euclide, la recherche d’une relation de récurrence linéaire dans une suite ou le décodage des codes BCH.

Développements :

Plans/remarques :

2024 : Leçon 142 - PGCD et PPCM, algorithmes de calcul. Applications.

  • Auteur :
  • Remarque :
    J'aime bien la manière dont j'ai construit cette leçon et j'aime bien mes développements, mais je n'aurais pas été très à l'aise de tomber dessus à l'oral.

    Les références sont indiquées à la fin du plan. N'hésitez pas à me contacter pour me signaler toute erreur ou imprécision.
  • Fichier :
  • Auteur :
  • Remarque :
    La plupart des mes plans sont inspirés de Ewna, Agentb0, Jouaucon, Abarrier et Marvin. Merci à eux. Attention aux coquilles ! Mes plans sont, en général, scannés juste après que j'ai finis de rédiger, bien sur quand je les ai relu j'ai trouvé des erreurs. Les références sont à la fin des plans.

    Je pense qu'il est bien de faire cette leçon juste après celle sur les anneaux principaux. Malgré le titre qui vend pas du rêve je trouve la leçon cool. Pour la partie algorithme coût etc j'aurai bien aimé trouver une autre référence, je ne trouve pas le Demazure top. J'ai finalement remplacé le lemme de noyaux par Dunford.
  • Fichier :

2023 : Leçon 142 - PGCD et PPCM, algorithmes de calcul. Applications.

  • Auteur :
  • Remarque :
    Possibilité d'avoir ma version complète manuscrite en me contactant par mail.
  • Fichier :

2022 : Leçon 142 - PGCD et PPCM, algorithmes de calcul. Applications.


2020 : Leçon 142 - PGCD et PPCM, algorithmes de calcul. Applications.

  • Auteur :
  • Remarque :
    Toutes les références sont à la fin du plan.

    Mes excuses pour l'écriture, et attention aux coquilles...
  • Fichier :

2019 : Leçon 142 - PGCD et PPCM, algorithmes de calcul. Applications.


2018 : Leçon 142 - PGCD et PPCM, algorithmes de calcul. Applications.

  • Auteur :
  • Remarque :
    Retours :
    - Présenter la def du pgcd/ppcm naturelle en premier.
    - Inverser la présentation des anneaux (Euclidien => principal => factoriel), pour mieux montrer les différences dans les propriétés.

    Remarque : la fin du dvp proposé est trop rapide
  • Fichier :

Retours d'oraux :

2023 : Leçon 142 - PGCD et PPCM, algorithmes de calcul. Applications.

  • Leçon choisie :

    142 : PGCD et PPCM, algorithmes de calcul. Applications.

  • Autre leçon :

    161 : Distances dans un espace affine euclidien. Isoméries.

  • Développement choisi : (par le jury)

    Théorème de Sophie-Germain

  • Autre(s) développement(s) proposé(s):

    Pas de réponse fournie.

  • Liste des références utilisées pour le plan :

    Pas de réponse fournie.

  • Résumé de l'échange avec le jury (questions/réponses/remarques) :

    - Concernant le développement :
    * ils m'ont demandé une petite précision sur le début : pourquoi peut-on supposer PGCD(x,y,z)=1 et x,y,z deux à deux premiers entre eux
    * s'il existait des nombres de Sophie-Germain et combien y en a-t-il
    * je connaissais bien ce développement, le jury ne m'a rien demandé de plus.

    - Concernant l'échange :
    * j'ai eu beaucoup de questions sur le plan : le théorème de Gauss, un contre-exemple pour montrer que l'implication principal ->euclidien est fausse, idem pour factoriel->principal, montrer que premier implique irréductible et si la réciproque est vraie dans le cas général
    * on a poursuivi avec un exercice : montrer que SL_2(Z) est engendré par les matrices (écrites ici en ligne) ((1 1) (0 1)) et ((0 -1) (1 0)). J'ai eu du mal avec cet exercice mais le jury m'a aidé pour qu'on puisse avancer.
    * lorsqu'il restait deux minutes d'oral le jury a préféré faire un autre exercice plutôt que de finir le premier (un peu étrange, même si c'était sûrement pour me permettre de me rattraper car je ne comprenais pas très bien les indications données par le jury sur le premier exercice) : calculer PGCD(X^(n)-1,X^(k)-1). J'ai à peine eu le temps de dire qu'on pouvait essayer une division euclidienne en supposant n>=k et de factoriser les polynômes à l'aide des racines n-ièmes de l'unité que l'oral c'est arrêté.

  • Quelle a été l'attitude du jury (muet/aide/cassant) ?

    Le jury était très gentil et patient et n'a pas hésité à m'aider lorsque j'ai bloqué sur l'exercice.

  • L'oral s'est-il passé comme vous l'imaginiez ou avez-vous été surpris par certains points ? Cette question concerne aussi la préparation.

    Tout est très bien organisé, il n'y a rien à signaler.

  • Note obtenue :

    Pas de réponse fournie.


2019 : Leçon 142 - PGCD et PPCM, algorithmes de calcul. Applications.

  • Leçon choisie :

    142 : PGCD et PPCM, algorithmes de calcul. Applications.

  • Autre leçon :

    152 : Déterminant. Exemples et applications.

  • Développement choisi : (par le jury)

    Algorithme d'Euclide étendu et complexité

  • Autre(s) développement(s) proposé(s):

    Pas de réponse fournie.

  • Liste des références utilisées pour le plan :

    Pas de réponse fournie.

  • Résumé de l'échange avec le jury (questions/réponses/remarques) :

    Le jury m'a posé quelques questions pour bien refixer les hypothèses de ma leçons. Puis est passé à une lecture plus approfondie du plan.
    Après quelques questions pour me demander si je pouvais un peu plus généraliser certains résultats de mon plan ou les réécrire pour éviter d'utiliser des termes partant un peu trop loin (comme ensemble réticulé, pour définir pgcd et ppcm), l'un des jury a remarqué (à voix haute) que mon plan manquait d'exemple.
    La fin de l'échange a donc été constitué de recherche de contre-exemples à mon plan (Donner un idéal non-monogène de Z[X], par exemple).

  • Quelle a été l'attitude du jury (muet/aide/cassant) ?

    Le jury était très sympathique, bien que peu souriant. Bien que l'un d'entre eux semblait commencer à se tendre vers la fin, ils m'ont tous les trois encouragés à avancer lorsque je touchais une corde sensible de leurs questions.

  • L'oral s'est-il passé comme vous l'imaginiez ou avez-vous été surpris par certains points ? Cette question concerne aussi la préparation.

    J'ai été beaucoup plus rapide lors de cette préparation qu'au moment de mes oraux blancs. Pour autant, il ne faut pas prendre tout son temps ;).
    Le jury me mettait étrangement en confiance et était très apaisant (moi qui ai eu à résoudre de gros soucis de stress, à côté du travail propre au concours). Cette dernière remarque concerne d'ailleurs l'ensemble de mes épreuves !

  • Note obtenue :

    10


Références utilisées dans les versions de cette leçon :

Algèbre , Gourdon (utilisée dans 333 versions au total)
Mathématiques pour l'agrégation: Algèbre et géométrie, Jean Etienne Rombaldi (utilisée dans 492 versions au total)
Algèbre : le grand combat: Cours et exercices, Grégory Berhuy (utilisée dans 114 versions au total)
Oraux X-ENS Algèbre 1, Francinou, Gianella, Nicolas (utilisée dans 142 versions au total)
Objectif Agrégation, Beck, Malick, Peyré (utilisée dans 292 versions au total)
Cours d'algèbre , Demazure (utilisée dans 15 versions au total)
Cours d'algèbre , Perrin (utilisée dans 432 versions au total)
Algèbre et probabilités, Gourdon (utilisée dans 77 versions au total)
Algorithmes fondamentaux , Saux Picart (utilisée dans 6 versions au total)
Modern Computer Algebra, von zur Gathen, Gerhard (utilisée dans 1 versions au total)
Elements de théorie des anneaux , Calais (utilisée dans 6 versions au total)
L'oral à l'agrégation de mathématiques - Une sélection de développements , Isenmann, Pecatte (utilisée dans 144 versions au total)
131 Développements pour l’oral, D. Lesesvre, P. Montagnon, P. Le Barbenchon, T. Pierron (utilisée dans 75 versions au total)
Algèbre L3 , Szpirglas (utilisée dans 45 versions au total)
Matrices , Serre (utilisée dans 10 versions au total)
Elements d'analyse et d'algèbre , Colmez (utilisée dans 17 versions au total)
Algèbre et géométrie , Combes (utilisée dans 40 versions au total)
Théorie des nombres, Daniel Duverney (utilisée dans 6 versions au total)