Mathématiques
Précédent
Suivant
Présentation algorithmique de la démonstration de l'existence des polynômes Q et R

Si l'on reprend la division euclidienne de par et l'égalité évidente indiquée plus haut qui n'est pas l'identité de la division euclidienne, on peut transformer cette égalité en remarquant que . On obtient alors :

Comme le polynôme est de degré 1, ce n'est pas le reste de cette division puisque son degré n'est pas strictement inférieur au degré du diviseur .

On peut écrire et par conséquent : .

Le polynôme constant est de degré 0 et donc strictement inférieur à 1. Donc, là on a l'identité de la division euclidienne.

Quels enseignements peut-on tirer de cet exemple ?

On a obtenu par un moyen quelconque (ici du style bricolage) des polynômes et satisfaisant aux conditions de l'identité de la division euclidienne. On a donc, du fait de leur unicité, le reste et le quotient de la division.

Effectivement, en théorie, tous les moyens mathématiquement corrects sont bons. Mais il est clair qu'il est nécessaire d'avoir une méthode de calcul systématique car il ne peut être question de bricolage comme dans l'exemple ci-dessus.

La réponse à cette question est l'algorithme suivant qui répond entièrement à la question posée. Il est basé sur le principe de la démonstration de l'existence et, techniquement, sur le lemme.

Si est un polynôme non nul on note le monôme est le degré de (i.e. ).

  • Algorithme :

    1. Entrer ;

    2. Initialiser : , ;

    3. (quotient par "divisions successives selon les puissances décroissantes")

      Tant que et faire :

      Q partiel ;

      ;

      ;

    4. Fin de l'algorithme

Explication : des notations pour les lecteurs non habitués à ce langage
  1. La notation signifie que ce qui est à gauche prend pour valeur ce qui est à droite autrement dit sur cet exemple que prend pour valeur .

    Il faut bien remarquer qu'une nouvelle affectation écrase la précédente.

  2. Si et sont deux polynômes non nuls, de termes dominants respectivement et , avec supérieur ou égal à , la notation représente le polynôme : .

Preuve
  • primo : on a toujours (i.e à la fin de 2. et à la fin de chaque exécution de 3. ;

  • secundo : l'algorithme se termine en un temps fini puisqu'à chaque exécution de 3. le degré de diminue (en vertu du lemme) ;

  • tertio : lorsque l'algorithme est terminé, on a simultanément : et ou

Légende :
Apprendre
S'évaluer
S'exercer
Observer
Simuler
Réalisé avec Scenari (nouvelle fenêtre)