142 - PGCD et PPCM, algorithmes de calcul. Applications.2025

Rapport du jury 2022

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\rnotions de PGCD et PPCM dans un anneau factoriel et comme générateurs de sommes/intersections\rd'idéaux dans un anneau principal. Le candidat doit prendre soin de différencier le cadre théorique\rdes anneaux factoriels ou principaux dans lequel sont définis les objets et dans lequel s'appliquent les\rénoncés des théorèmes proposés et le cadre euclidien fournissant les algorithmes. Bien sûr, la leçon\rpeut opportunément s'illustrer d'exemples élémentaires d'anneaux euclidiens, comme Z et $K[x]$.\rUne part substantielle de la leçon doit être consacrée à la présentation d'algorithmes : algorithme\rd'Euclide, algorithme binaire, algorithme d'Euclide étendu. Dans le cas des polynômes, il faut\rétudier l'évolution de la suite des degrés et des restes. On peut évaluer le nombre d'étapes de ces\ralgorithmes dans les pires cas et faire le lien avec les suites de Fibonacci.\r\rDes applications élémentaires sont particulièrement bienvenues : calcul de relations de Bezout, ré-\rsolutions d'équations diophantiennes linéaires, inversion modulo un entier ou un polynôme, calculs\rd'inverses dans les corps de ruptures, les corps finis. On peut aussi évoquer le théorème chinois effectif,\rla résolution d'un système de congruences et faire le lien avec l'interpolation de Lagrange.\rPour 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\rmatricielle de l'algorithme d'Euclide et l'action de $SL_2(Z)$ sur $Z^2$ est tout à fait pertinent. On peut\raussi é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.\r\rLa 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\rd'équations diophantiennes linéaires. De même, aborder la forme normale de Smith, et son application\rau théorème de la base adaptée, permet de faire le lien avec la réduction des endomorphismes via le\rthéorème des invariants de similitude.\r\rLa leçon invite aussi, pour des candidats familiers de ces notions, à décrire le calcul de PGCD dans\r$Z[X]$ et $K[X,Y]$s, avec des applications à l'élimination de variables. On peut rappeler les relations entre\rPGCD et résultant et montrer comment obtenir le PGCD en échelonnant la matrice de Sylvester.\rSur l'approximation diophantienne, on peut enfin envisager le développement d'un rationnel en fraction\rcontinue et l'obtention d'une approximation de Padé-Hermite à l'aide de l'algorithme d'Euclide,\rla recherche d'une relation de récurrence linéaire dans une suite ou le décodage des codes BCH.

Rapport du jury 2020

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].\r$$$$\r\rUne 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.\r$$$$\r\rDes 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.\r$$$$\r\rPour 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. \r$$$$\r\rLa 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\rd’é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\rthéorème des invariants de similitude.\r\rLa 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\rPGCD 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.

Rapport du jury 2019

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]$.\r\rUne 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.\r\r\rDes 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.\r\r\rPour 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.\r\r\rLa 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.\r\r\rLa 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.

Rapport du jury 2018

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]$.\r\rLa 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.\r\rLa 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.\r\rPour 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.\r\rLa 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.\r\rLa 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.