Polynomes

On considère ici des polynômes à coefficients entiers ou à coefficients dans ${\mathbb{Z}}/n{\mathbb{Z}}$. Certaines des notions d'arithmétique vues sur les entiers continuent à s'appliquer aux polynômes, en particulier on peut définir une notion de division euclidienne selon les puissances décroissantes.

Soit $A$ un polynôme non nul, $A(X)=a_d X^d + ... + a_0$ avec $a_d\neq 0$. L'entier $d$ est appelé degré de $A$. La division euclidienne de $A$ par $B$ correspond à l'égalité:

$$A= B Q + R$$

où le degré de $R$ est strictement inférieur au degré de $B$. Pour calculer $Q$ et $R$ connaissant $A$ et $B$ on commence par diviser le terme de plus haut degré de $A$ par celui de plus haut degré de $B$ que l'on met comme coefficient de $X^{d(A)-d(B)}$ dans $Q$. On multiplie alors ce terme par $Q$ et on le retranche à $A$, ce qui diminue le degré d'un au moins. On recommence tant qu'on peut (tant que le degré est supérieur ou égal à celui de $B$), losqu'on s'arrête on obtient le reste.
Programmer la division euclidienne et le PGCD de deux polynômes dont les coefficients sont dans ${\mathbb{Z}}/n{\mathbb{Z}}$.