Mathématiques et algorithmique

Algorithme 13.2.1. Théorème des restes chinois.

• Entrées :

  • Assigner à \(\text{lesA}\) la liste des \(a_i\text{.}\)

  • Assigner à \(\text{lesM}\) la liste des \(m_i\text{.}\)

• Prérequis : Définir une fonction \(\text{euclideEtendu(a, b)}\) qui renvoie \(\text{(r, u, v)}\) où

  • \(\text{r}\) est le PGCD de \(\text{a}\) et de \(\text{b}\text{;}\)

  • \(\text{u}\) et \(\text{v}\) sont les coefficients de la combinaison linéaire donnée par l'algorithme d'Euclide étendu.

• Instructions :

  • Assigner à \(\text{M}\) la valeur \(1\text{.}\)

  • Pour \(\text{m}\) parcourant la liste \(\text{lesM}\text{,}\)

    • assigner à \(\text{M}\) la valeur \(\text{M}\cdot\text{m}\text{.}\)

  • Assigner à \(\text{x0}\) la valeur \(0\text{.}\)

  • Pour \(\text{i}\) allant de \(0\) au nombre d'élements dans la liste \(\text{lesM}\) moins \(1\text{,}\)

    • assigner à \(\text{ai}\) la \(\text{i}\)-ème valeur de la liste \(\text{lesA}\) ;

    • assigner à \(\text{mi}\) la \(\text{i}\)-ème valeur de la liste \(\text{lesM}\) ;

    • assigner à \(\text{Mi}\) la valeur de \(\text{M}/\text{mi}\) ;

    • assigner à \(\text{ui}\) la deuxième composante de \(\text{euclideEtendu(Mi, mi)}\) ;

    • assigner à \(\text{x0}\) la valeur de \(\text{x0}+\text{ai}\cdot\text{Mi}\cdot\text{ui}\text{.}\)

• Sortie : Afficher \(\text{x0}\) et \(\text{M}\text{.}\)