Division euclidienne polynôme
Bonsoir,
Soient $n$ et $p$ deux entiers naturels non nuls tels que $n \geq p$.
1) Effectuer la division euclidienne de $X^n-1$ par $X^p-1$.
Fixons $p$ et notons $Q_n(X)$ et $R_n(X)$ respectivement le quotient et le reste de la division euclidienne de $X^n-1$ par $X^p-1$.
On a $X^n-1=(X^p-1)X^{n-p}+X^{n-p}-1$
Je ne comprends pas la suite.
Donc $Q_n(X)=X^{n-p}+Q_{n-p}(X)$ et $R_n(X)=R_{n-p}(X)$
Soient $n$ et $p$ deux entiers naturels non nuls tels que $n \geq p$.
1) Effectuer la division euclidienne de $X^n-1$ par $X^p-1$.
Fixons $p$ et notons $Q_n(X)$ et $R_n(X)$ respectivement le quotient et le reste de la division euclidienne de $X^n-1$ par $X^p-1$.
On a $X^n-1=(X^p-1)X^{n-p}+X^{n-p}-1$
Je ne comprends pas la suite.
Donc $Q_n(X)=X^{n-p}+Q_{n-p}(X)$ et $R_n(X)=R_{n-p}(X)$
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Est-ce qu’à la ligne que tu as écrite juste avant « je ne comprends pas », on a l’égalité de la division euclidienne ?
En gros, a-t-on terminé ?
Par exemple, si $n=6$ et $p=1$ on a $\deg X^{6-1}-1=5 > \deg X^1 -1$ donc non la division euclidienne n'est pas terminée.
On a $\deg X^p-1 =p$ car $p \ne 0$ et $\deg X^{n-p}-1 \leq \max(n-p,0) \leq n-p$
.
Un reste par division euclidienne par $3$ consiste à soustraire autant de fois que possible le nombre $3$ (c'est à dire que la soustraction donne un résultat positif ou nul). Le nombre obtenu à la fin du processus est le reste (s'il ne reste rien cela signifie que le nombre est divisible par $3$).
Par ailleurs,
Si $n-p\geq p$ qu'est-ce qui t'empêche de diviser $x^{n-p}-1$ par $x^p-1$?
PS:
L'action répétée de la formule $X^n-1=(X^p-1)X^{n-p}+X^{n-p}-1$ te garantit que tu vas obtenir à la fin un polynôme qui est soit $0$ soit un polynôme de degré plus petit que $p$.
Car à chaque fois que tu utilises cette formule cela te renvoie un polynôme de degré auquel on a soustrait $p$ par rapport à celui qu'on avait en entrée.
PS2:
Il est aisé d'anticiper avec la formule $X^n-1=(X^p-1)X^{n-p}+X^{n-p}-1$ ce que sera le reste de la division euclidienne de $x^m-1$ par $x^p-1$. A chaque fois qu'on applique cette formule on soustrait $p$ au polynôme en entrée.
Si $n=pk+r$ avec $0\leq r<p$
On a aussi, sauf erreur, l'égalité: $X^n-1=(X^{kp}-1)X^{n-kp}+X^{n-kp}-1=(X^{kp}-1)X^{r}+X^{r}-1$
En fait, je dispose d'un corrigé mais je ne comprends pas un passage.
Pourquoi $Q_n(X)=X^{n-p}+Q_{n-p}(X)$ et $R_n(X)=R_{n-p}(X)$ ?
Ensuite, ils font la division euclidienne de $n$ par $p$ s'écrit $n=pq+r$ où $0 \leq r <p$
Alors $Q_n(X)=X^{n-p}+Q_{n-p}(X)=X^{n-p}+X^{n-2p}+ \cdots + X^r+Q_r(X)$
Et $R_n(X)=R_{n-p}(X)= \cdots = R_r(X)$
Or $Q_r(X)=0$ et $R_r(X)=X^r-1$ donc le quotient recherché est $X^{n-p}+X^{n-2p}+ \cdots + X^r$ et le reste $X^r-1$
Le seule passage que je ne comprends pas c'est $Q_n(X)=X^{n-p}+Q_{n-p}(X)$ et $R_n(X)=R_{n-p}(X)$
@Gai Requin
Je n'ai pas compris la méthode avec les modulos.
Pour la méthode avec les modulos.
Quand on calcule modulo $X^p-1$ c'est comme si on décidait d'une certaine façon que $X^p=1$.
Beaucoup de monde a répondu à côté de la plaque car la question de départ n'était pas claire... parce que tu as eu peur d'avouer que tu lisais encore un corrigé sans le comprendre.
Comment voulais-tu que l'on comprenne avant que tu ne nous dises que pour CHAQUE valeur $n$, on définit les quotient et reste $Q_n$ et $R_n$ de $X^n-1$ par $X^p-1$ ?
Je suppose que le corrigé essaie d'établir une relation de récurrence entre $Q_n$ et $Q_{n-p}$ et entre $R_n$ et $R_{n-p}$.
Cette relation est TRIVIALE en utilisant la définition de la division euclidienne.
Il n'y a plus qu'à travailler.
Si tu ne vois toujours pas, écris la TOTALITÉ de ce que tu as essayé d'écrire et explique pourquoi TU n'arrives pas à avancer. Il ne sert à rien de comprendre comment le corrigé s'en est sorti.
OShine la meilleure méthode c'est celle que tu trouveras toi même en réfléchissant tout seul. Si elle est longue tant pis.
Tout le monde essaie de t'aider, mais tu es toujours mené par les calculs au lieu de réfléchir et ne faire que ce qui est utile.
Sinon pour ta dernière question, la réponse est dans le premier message de Dom.
Cordialement
Si $n=mp+m'$ alors le reste dans la division euclidienne de $n$ par $p$ est le même que le reste de la division de $m'$ par $p$.
@Gai Requin
J'ai finalement compris la méthode modulo (:P)
Soit $n=pq+r$ avec $r<p$
$\boxed{X^{n}-1=(X^{pq}-1)X^{r}+X^{r}-1}$
Or $X^{pq}-1=(X^p)^q-1^q=(X^p-1) \displaystyle\sum_{i=0}^{q-1} X^{pi}$ donc $\boxed{X^n-1 \equiv X^r -1 [X^p-1]}$
Ainsi, le reste est $X^r-1$ et le quotient $\dfrac{X^n-X^r}{X^p-1}$
@Bisam
@Nahar
Si je reviens à la méthode de mon livre :
$X^n-1=(X^p-1)X^{n-p}+X^{n-p}-1$
$X^{n-p}-1=(X^p-1)X^{n-2p}+X^{n-2p}-1$
J'avais déjà essayé ce calcul avant de poser la question sur le forum mais je ne vois pas comment obtenir $Q_n(X)=X^{n-p}+Q_{n-p}(X)$ et $R_n(X)=R_{n-p}(X)$
Le calcul modulo $X^p-1$ est beaucoup plus simple que ce que tu écris.
Pour reprendre tes notations $n=pq+r$
$X^n-1=X^{pq+r}-1=\left(X^{p}\right)^qX^r-1\equiv X^r-1\mod{X^p-1}$
Car $X^p-1\equiv 0\mod{X^p-1}$ est équivalent à $X^p\equiv 1\mod{X^p-1}$
(c'était déjà expliqué par Gai Requin plus haut)
Mais la méthode de mon corrigé je ne vois toujours pas.
Tout est dit dans ce fil.
Encore un essai: si $m$ et $n$ sont tels que $m-n$ est divisible par $p$ alors $m$ et $n$ ont le même reste dans la division euclidienne par $p$
($m,n,p$ appartiennent à un anneau euclidien comme $\mathbb{Z}$,$K[X]$ avec $K$ un corps)
Et sans surprise le quotient est nommé $Q_n(X)$ et le reste $R_n(X)$.
Par ailleurs, ce n'est pas parce qu'on a une relation du type $n=pq+r$ que dans la division euclidienne de $n$ par $p$ le quotient est $q$ et le reste $r$.
Cependant il y a bien une relation (déjà indiquée plus haut) entre le reste dans la division euclidienne de $n$ par $p$ et le reste de la division de $r$ par $p$.
L'unicté du quotient et du reste dans une division euclidienne je connais.
Ce que je t'ai dit permet de montrer la deuxième relation que tu as mise en rouge dans ton premier message.
Il faut prendre en compte la relation que tu donnes:
$\displaystyle X^n-1=\underbrace{(X^p-1)X^{n-p}}_{\text{multiple de }X^p-1} +X^{n-p}-1$
PS:
En réalité, il y a seulement à traduire formellement les définitions données pour $Q_m(X)$ et $R_m(X)$
(c'est à dessein que j'introduis $m$ un entier strictement positif quelconque).
Ces deux quantités sont uniques.
PS2:
$22=5\times 3+7=5\times 3+\left(2\times 3+1\right)=(5+2)\times 3+1=7\times 3+1$
On te dit que $X^n-1=Q_n(X)\left(X^p-1\right)+R_n(X)$ et $X^{n-p}-1=Q_{n-p}(X)\left(X^p-1\right)+R_{n-p}(X)$
On dit un peu plus que cela mais voyons voir ce que tu fais de ces informations.
Il me semblait que l'algorithme de division était encore enseigné dans les "petites classes", pourtant.
Je ne veux pas être grossier mais si on te dit $A=5+B$
et $B=7$.
Tu ne sais pas calculer $A$?
Pour moi ce qu'on te demande est une question qui très proche de ça.
$X^n-1=(X^p-1)X^{n-p}+X^{n-p}-1$ (c'est toi qui l'a mis sur la table)
et l'énoncé introduit des notations, on te dit que $X^{n-p}-1=Q_{n-p}(X)\times (X^p-1)+R_{n-p}(X)$ (*)
Tu ne vois toujours pas le rapport?
*: l'énoncé dit plus mais pour le moment voyons ce que tu vas faire de tout ceci.
En combinant il vient $X^n-1=(X^p-1)(Q_{n-p}(X)+X^{n-p})+R_{n-p}(X) \\
\ \ \ \ \ \ \ \ \ \ \ \ =(X^p-1) Q_n(X)+R_n(X)$ et on conclut par unicité de la division euclidienne.
Mais j'aimerais comprendre avec la méthode de Bisam où on pose la division euclidienne.
Cela demanderait à être précisé selon moi.
Pour la méthode avec la division posée, j'ai relu l'algorithme mais je ne trouve pas.
Pardon mais cela peut être pris pour de l'esbroufe ici.
Pourquoi à la seule vue de:
$X^n-1=(X^p-1)(Q_{n-p}(X)+X^{n-p})+R_{n-p}(X) $ on sait que $R_{n-p}(X)$ est le reste de la division de $X^n-1$ par $X^p-1$ et $Q_{n-p}(X)+X^{n-p}$ le quotient?
NB: $R_{n-p}(X)$ est défini comme étant le reste dans la division euclidienne de $X^{n-p}-1$ par $X^p-1$.
edit: il y avait une erreur d'indice.
Tu vois bien qu'à partir de $X^{n}-1$ on arrive à $X^{n-p}-1$.. Le reste cherché est aussi celui de la division euclidienne de $X^{n-p}-1$ par $X^p-1$. Il n'est pas difficile de voir où cela nous mène*.
*: On peut continuer le processus et on peut anticiper le résultat aisément (au moins pour le reste).
En fait je n'avais jamais réfléchis sérieusement à l'algorithme de la division euclidienne. Je le faisais mécaniquement sans réfléchir. En fait, on prend le premier reste et on refait la division euclidienne du premier reste par le diviseur qui ne change pas.
D'où la remarque de @Bisam qui prend tout son sens.
J'avoue que ça m'a bien fait sourire.
Il est même plus compliqué pour les entiers que pour les polynômes puisque pour les entiers, on ne sait pas à l'avance si on va devoir considérer un paquet de 1, 2, 3, n chiffres au départ, alors que pour les polynômes, il suffit de regarder le monôme non nul de plus haut degré.
Tu viens également d'avouer que tu n'avais pas parfaitement compris l'algorithme jusque là... D'ailleurs, tu l'as mal exprimé puisque tu as dit que l'on redivisait le "premier reste", alors que ce terme n'est pas adéquat puisque ce n'est PAS encore LE reste.
Possible mais j'ai plus de mal avec les polynômes.