Division euclidienne

Dans $\Z$, existence. Soit $q=\lfloor a/b\rfloor$ : $q\le a/b<q+1$. En multipliant par $b>0$, $bq\le a<bq+b$, donc $r=a-bq$ vérifie $0\le r<b$.

Dans $\Z$, unicité. Si $bq+r=bq'+r'$ avec $0\le r,r'<b$, alors $b|q-q'|=|r'-r|<b$, donc $|q-q'|<1$, soit $q=q'$ puis $r=r'$.

Dans $\K[X]$, existence. Soit $m=\deg B$ et $b_m\neq 0$ le coefficient dominant de $B$. On raisonne par récurrence forte sur $\deg A$. Si $\deg A<m$ (y compris $A=0$), le couple $(0,A)$ convient. Sinon, soit $n=\deg A\ge m$ et $a_n$ son coefficient dominant. Le polynôme

est de degré $<n$ (les termes de degré $n$ se compensent). Par hypothèse de récurrence, $A_1=BQ_1+R$ avec $\deg R<m$, d'où $A=B\Big(Q_1+\frac{a_n}{b_m}X^{n-m}\Big)+R$.

Dans $\K[X]$, unicité. Si $BQ+R=BQ'+R'$ avec $\deg R,\deg R'<m$, alors $B(Q-Q')=R'-R$. Si $Q\neq Q'$, le membre de gauche est de degré $\ge m$, alors que celui de droite est de degré $<m$ : contradiction. Donc $Q=Q'$ et $R=R'$.

On a utilisé que $b_m$ est inversible : c'est ici que sert l'hypothèse « $\K$ est un corps ».

Calcul pratique dans $\Z$ (comme une calculatrice). On calcule $a/b$, on prend la partie entière $q=\lfloor a/b\rfloor$ (arrondi vers le bas, y compris pour $a<0$), puis $r=a-bq$. En Python, la fonction divmod renvoie ce couple $(q,r)$ lorsque $b>0$.

Calcul de $A^n$ par un polynôme annulateur. Si $P(A)=0$ avec $\deg P=d$, on écrit $X^n=PQ_n+R_n$ avec $\deg R_n<d$ ; alors $A^n=P(A)Q_n(A)+R_n(A)=R_n(A)$. Pour trouver $R_n$ sans poser la division :

• si $\lambda$ est racine de $P$, alors $R_n(\lambda)=\lambda^n$ ;
• si $\lambda$ est racine double, on dérive aussi : $R_n'(\lambda)=n\lambda^{n-1}$.

On obtient $d$ équations linéaires sur les $d$ coefficients de $R_n$.

Les deux divisions euclidiennes (dans $\Z$ et dans $\K[X]$), avec existence et unicité, sont au cœur du cours de première année. L'application au calcul de $A^n$ par le reste de la division de $X^n$ par un polynôme annulateur est une méthode standard de deuxième année.